Let's spend some time with the Collatz conjecture

About a week ago I decided to spend some time on the Collatz conjecture. In 1937 a German mathematician, Lothar Collatz, proposed an apparently simple algorithmic idea. Take any natural number N: if even, then divide it by 2, otherwise, multiply it by 3 and add 1 to the result. Repeat this process. The conjecture postulates that 1) this process will converge 2) and it will always converge to 1, no matter the starting N (up to repeated cycles). Ninety years later there is still no actual proof of whether or not this procedure will converge for any N. Why? Nobody is entirely sure, not even Terence Tao, perhaps the greatest mathematician of my generation, who stated "You can get as close as you want to the Collatz conjecture, but it’s still out of reach", after trying to tackle the proof.

Oh well, I'll certainly not be able to find the proof, but nonetheless last week I really wanted to play this game for a couple of days. And it was marvellously entertaining.

Consider for instance the first 9 natural numbers > 1, and their full sequence:

The "length with cycles" indicates the number of steps to reach 1. The "length no cycles" is obtained by removing numbers appearing in any prior sequence, ie the red numbers. Also, the green numbers appear in some previous iteration. Typically, you want to plot the starting number N against its length (with cycles), producing the following graph

for the first 10^5 numbers. However, if you plot unique starting numbers against the length with no cycles, then you will generate a rather different picture

where the bottom chart shows a type of diffusion evolution, with compactification in the smaller region. This shape will be preserved as you will increase N. Interestingly enough, the 10 largest sequences, with only unique entries are

where you may have large prime numbers, like 96703, or multiples of 3. This latter feature is, I believe, the reason why Tao focused his attention on samples mod3, ie whose remainder is either 1 or 2.

The appearance of symmetries is actually what drove my attention in the first place. The most simple one is the recurring pattern of 4,2,1 when ending any sequence. However 2 other slightly larger repeating patterns are "10,5,16,8,4,2,1" or "64,32,16,8,4,2,1", which occur respectively 93.74% and 6.25% at least in the first 10^5 starting numbers.

Anyway, one could literally spend a lifetime on this game...

As usual, have fun!