What is the record for Collatz Conjecture Steps

Question

Does anyone know the record for the number of steps a Collatz Conjecture run has taken to get to 1?

I have written a small program in Python to do the Collatz Conjecture on the Mersenne prime where n=5000 and produced a text file of ~88MB with a total step of 67378.

Answer 1

A small caveat first: what counts as an 'iteration' of the Collatz process varies a bit from source to source. Because what happens at even numbers is 'boring', the most standard convention seems to be looking at the process as it relates to odd numbers specifically, taking $n\mapsto \dfrac{3n+1}{2^i}$, where $2^i$ is the largest power of $2$ that divides $3n+1$.

Now, we can think about how the Mersenne numbers map under this process. Suppose we start with $n_0=2^k-1$. Then we look at $3n_0+1$ and see that this is $3\cdot2^k-2$; dividing by $2$ once gives $n_1=3\cdot 2^{k-1}-1$. Unless $k=1$, this is also odd, so we have no more factors of $2$ to strip out.

And this repeats: $3n_1+1$ is $3^2\cdot2^{k-1}-2$, dividing by $2$ once gives $n_2=3^2\cdot 2^{k-2}-1$, and unless $k=2$ this will also be odd.

It should be clear how this process iterates; after $i$ steps we'll have $n_i=3^i\cdot2^{k-i}-1$, and this continues until $i=k-1$ and we get $n_{k-1}=3^{k-1}\cdot 2-1$. Then $3n_{k-1}+1=3^k\cdot2-2$, and dividing by $2$ gives $3^k-1$ — but note that now we can do at least one more division by $2$, so the expression for $n_k$ isn't quite so neat.

In general the iteration will get much messier from here, and there generally won't be any more 'clean' expressions for the results. But we can explicitly describe the first $k-1$ steps of the process this way, so producing a long chain of iterations is just a question of how much computing power you want to throw at it.