The Simplest Open Problem In Mathematics

The Collatz Conjecture was posed in 1937 by Lothar Collatz, two years after he received his Ph.D. It remains open to this day.

“Mathematics may not be ready for such problems.” — Paul Erdős.

“This is an extraordinarily difficult problem, completely out of reach of present day mathematics.” — Jeffrey Lagarias

What’s the conjecture about?

The Collatz Conjecture states that any natural number will resolve into 1 after applying these conditions iteratively:

If the number is even, divide it by 2.
If the number is odd, multiply it by 3 and add 1.

Sounds simple enough right? Let’s go through some examples, assuming we picked n = 5:

5 is odd so we multiply it by 3 and add 1: 5*3 + 1 = 16
16 is even so we divide it by 2: 16/2 = 8
8 is even so we divide it by 2: 8/2 = 4
4 is even so we divide it by 2: 4/2 = 2
2 is even so we divide it by 2: 2/1 = 1
We have reached the number 1 after 5 iterations.
Also note that in order for us to get to 1 with n=5 we had to climb up to 16.

Some numbers require a lot more iterations, for example if we have picked n=3331 we would have to perform 180 iterations before getting to 1 and while doing so, we would climb up to 250504.

Visualizing the problem

In case you’ve pondered how is the number of iterations is distributed or how is the max value of each number is distributed, I got you covered.

The maximum number of iterations on the above graph is 350 and we get that value for n=77031.

These graphs were created by the following code, feel free to tweak it

Lastly, here’s a tree of all numbers that require less than 20 iterations before getting to 1.