I noticed a peculiar relation while briefly thinking about the Collatz conjecture, which occurs when the iteration is specifically applied to numbers of the form $2^n-1$. I am wondering whether this pattern is known (my expectation is that it is known since long ago…), and whether a proof of this particular pattern exists.
Let me define the function $f(n)$ to be the number of Collatz iterations needed to reach $1$ if starting from $n$. So, for example, $f(2^k) = k$ and $f(27) = 111$ and $f(1)=0$.
The observation is that for $k\geq 2$:
$$f(2^{2k}-1) -1 = f(2^{2k-1}-1)$$
The simplest instance corresponds to $k=2$, when $2^{2k}-1 = 15$ (with $f(15) = 17$) and $2^{2k-1}-1=7$ (with $f(7) = 16$). Although the relation superficially looks very simple, with the "$-1$" just being swapped between two positions, the actual Collatz sequences for these two numbers are of course rather different,
$$7\mapsto 22 \mapsto 11 \mapsto 34 \mapsto 17 \mapsto 52 \mapsto 26 \mapsto 13 \mapsto 40 \mapsto \ldots$$
$$15\mapsto 46 \mapsto 23 \mapsto 70 \mapsto 35 \mapsto 106 \mapsto 53 \mapsto 160 \mapsto 80 \mapsto 40 \mapsto \ldots$$
(while agreeing in the remaining steps $\ldots \mapsto 20 \mapsto 10 \mapsto 5 \mapsto 16 \mapsto 8 \mapsto 4 \mapsto 2 \mapsto 1$.)
Similar pair of sequences for $k=3$ are already rather long, with $f(31) = 106$ and $f(63) = 107$. Quite generally, it seems that the Collatz sequences of $2^{2k}-1$ and $2^{2k-1}-1$ become identical after $4n+2$ steps (for the larger number) resp. after $4n+1$ steps (for the smaller number), which perhaps could be a clue for proving this pattern.
(I numerically checked the above relations for the first ~100 numbers $2^{n}-1$.)
Do you know if this feature has been further investigated somewhere?
Best Answer
Starting with the odd number $3^m2^n - 1$ (where $n \geq 1, m \geq 0$), one iteration of Collatz gives $3^{m+1}2^n - 2$, and the next iteration gives $3^{m+1}2^{n-1} - 1$. This process repeats for $2n$ iterations until the number reaches $3^{m+n} - 1$. In particular, after $4k$ respectively $4k-2$ steps, your numbers reach $3^{2k} - 1$ and $3^{2k-1} - 1$ respectively.
Let us look at $3^{2k-1} - 1$. We can see that modulo 4, it is equal to 2, so that the next two steps will be an "even step" followed by an "odd step", which results in the number $$ 3 \frac{3^{2k-1} -1}{2} + 1 = \frac{3^{2k} - 3 + 2}{2}, $$ but this is precisely the result of doing one more Collatz iteration on the even number $3^{2k} - 1$. Thus after $4k + 1$ respectively $4k$ steps, the numbers agree, and the remainder of their Collatz sequence is identical.