## Apr 26 The Collatz Conjecture

Start with any natural number (1, 2, 3, 4 etc.) and follow one of two rules:

If it is even then divide it by 2.

If it is odd then multiply by 3 and add 1.

So for example, if we start with the number 3 then it is odd so we follow the second rule and get  10. 10 is even, so we follow the first rule and get 5. Following this sequence we get a chain 3 => 10 => 5 => 16 => 8 => 4 => 2 => 1. However when we get the result 4, so we end up in a loop of 4 => 2 => 1 => 4 => 2 => 1 => 4...

The Collatz Conjecture hypothosises states that all possible starting numbers will end up converging to that same loop. It remains one of the most famous unsolved problems in mathematics. Paul Erdős offered \$500 for anyone who could prove it one way or the other, but stated that "Mathematics may not be ready for such problems."

This has been open for the best part of a century without any progress. Notice that a single loop of numbers which doesn't include 4, 2 or 1 would disprove it, but to prove it was true would require something more subtle. In terms of progress made by people trying to disprove the statement we have shown (in 2009) that any possible cycle would have a smallest term of at least 5x2^60. But these attempts at exhaustion have been fruitless so far. We've also shown that is a loop exists that it must have at least 68 numbers in the loop but, these lower bounds still leave an infinite number of numbers to check.

One thing that is doable is to find the 4 other trivial loops that exist if you allow negative numbers as well. Answers under this relevant XKCD comic:

The trivial loops are:

4 => 2 => 1 => 4

-1 => -2 => -1

0 => 0

-5 => -14 => -7 => -20 => -10 => -5

-17 => -50 => -25 => -74 => -37 => -110 => -55 => -164 => -82 => -41 => -122 => -61 => -182 => -91 => -272 => -136 => -68 => -34 => -17

(For that last one I agree the definition of trivial is pushed.)