About the Collatz conjecture

Question

I worked on the Collatz conjecture extensively for fun and practise about a year ago (I'm a CS student, not mathematician). Today, I was browsing the Project Euler webpage, which has a question related to the conjecture (longest Collatz sequence). This reminded me of my earlier work, so I went to Wikipedia to see if there's any big updates. I found this claim

The longest progression for any initial starting number less than 100 million is 63,728,127, which has 949 steps. For starting numbers less than 1 billion it is 670,617,279, with 986 steps, and for numbers less than 10 billion it is 9,780,657,630, with 1132 steps.[11][12]

Now, do I get this correctly: there is no known way to pick a starting number $N$, so that the progression will last at least $K$ steps? Or, at least I don't see the point of the statement otherwise. I know how this can be done (and can prove that it works). It does not prove the conjecture either true/false, since it is only a lower bound for the number of steps. Anyway, I could publish the result if you think it's worth that? When I was previously working on the problem, I thought it was not.

Answer 1

The answer to your question is yes; one can work the Collatz relation backwards to build numbers that last arbitrarily long (for a simple example, just take powers of 2). However the purpose of the wikipedia records is to see if we can find SMALL numbers that last a long time.

Answer 2

To add on Vadim's answer. With a bit different notation it is perhaps better readable to express the following:

instead of the sequence of steps $ a_1=3a_0+1 ; a_2 = a_1/2; a_3 = a_2/2 ; ... a_k=a_{k-1}/2 $ which means we count k steps and obviously is only allowed until $a_k$ becomes an odd number, let us write $ a_k = T(a_0; K) $ so this is only one step in the new formulation but counts as $1 + k$ steps in the usual convention because it means one step $3a_0+1$ and then $k$ steps dividing by $2$ which simply means one step dividing by $2^K$.

Then further iterations become an expression like $ a_x = T(a_0;A_1,A_2,A_3,...,A_x) $ where the number-of-exponents $N$ (="3x+1" steps) plus the sum $S$ of all exponents $A_k$ give the number of steps $k$ in the conventional way of counting.

Now we can, for any given sequence of exponents $ a_x = T(a_0; A_1,...,A_x)$ find an initial pair of $a_0$ and $a_k$ which solves the transformation equation (and then infinitely many others which only are in the same resdiue class "modulo $2^S$") where, again, $S$ is the sum of the exponents (or: the overall number of divsion-by-2 steps).

To make the same sum of some number of given steps $k$ in the conventional counting, say we want $k =60000$ we can first define any number of $N \lt k/2$ steps for the $3x+1$ transformations and then $N$ exponents $A_1,A_2,...A_n$, whose sum $S$ must then fill the gap $S= k - N"$.

But we have many options to first choose some $N$ - and after that we have another (but finite, fortunately!) number of variations of the exponents $A_k$ to sum up to $S$ and each such variation defines its own smallest pair $a_0 \to a_k$ (and the other solutions in the same modular class).

But which is now the smallest $a_0$ in all that possible settings? It can be determined in a finite amount of time/calculations -which is in its own an interesting observation- , but this is the essence of the discussion/the search of the "records-in-step-numbers"