Did I find a counterexample to the Collatz conjecture?

Question

I think I found a number that breaks the Collatz conjecture.

Start with 27:

27 \to 82 \to 41 \to 124 \to 62 \to 31 \to 94 \to 47 \to 142 \to 71 \to 214 \to 107 \to 322 \to 161 \to 484 \to 242 \to 121 \to 364 \to 182 \to 91 \to 274 \to 137 \to 412 \to 206 \to 103 \to 310 \to 155 \to 466 \to 233 \to 700 \to 350 \to 175 \to 526 \to 263 \to 790 \to 395 \to 1186 \to 593 \to 1780 \to 890 \to 445 \to 1336 \to 668 \to 334 \to 167 \to 502 \to 251 \to 754 \to 377 \to 1132 \to 566 \to 283 \to 850 \to 425 \to 1276 \to 638 \to 319 \to 958 \to 479 \to 1438 \to 719 \to 2158 \to 1079 \to 3238 \to 1619 \to 4858 \to 2429 \to 7288 \to 3644 \to 1822 \to 911 \to 2734 \to 1367 \to 4102 \to 2051 \to 6154 \to 3077 \to 9232 \to 4616 \to 2308 \to 1154 \to 577 \to 1732 \to 866 \to 433 \to 1300 \to 650 \to 325 \to 976 \to 488 \to 244 \to 122 \to 61 \to 184 \to 92 \to 46 \to 23 \to 70 \to 35 \to 106 \to 53 \to 160 \to 80 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1

Thats 111 steps! But the loop at the end (4,2,1,4,2,1,...) shows it converges. So this isnt a counterexample.

My actual observation: The number $2^n - 1$ (all 1s in binary) seems to take a long time. Is there a formula for how many steps $2^n - 1$ takes to reach 1?

Robert Fischer · Accepted Answer

A claimed Collatz counterexample has to survive a very strict check: every step must follow exactly one rule. For a positive integer n: - if n is even, replace it with n / 2, - if n is odd, replace it with 3 n + 1. Most false counterexamples come from one of three mistakes: 1. applying 3 n + 1 to an even number, 2. dividing an odd number by 2 too early, 3. stopping at a large number and assuming it will never come down. A real counterexample would need to either enter a cycle that does not include 1, or grow forever without ever reaching 1. Just finding a long or messy path is not enough. So the right way to check your example is to list every value in order and mark which rule was used. If one transition breaks the rule, the counterexample fails.

Did I find a counterexample to the Collatz conjecture?

1 Answer

Did I find a counterexample to the Collatz conjecture?

1 Answer