Number of Collatz steps for Mersenne numbers I noticed that for all $k \in \mathbb{N} \geq 1$ the following is true (I tested up to $2^{5000}$):

$\text{Collatz_Steps}(2^{2k+1} - 1) + 1 = \text{Collatz_Steps}(2^{2k+2} - 1)$

Where $\text{Collatz_Steps}$ is the number of steps required to reach $1$.
Is there a proof for this?
 A: Proof sketch:
For a number $2^n-1,$ the first $2n$ steps are the $3x+1$ step and the $x/2$ step in alternating order, until you reach $3^n-1.$
$3^n-1$ is even, so the next step is the $x/2$ step again. We have
$$
\frac{3^n-1}{2} = \sum_{j=0}^{n-1} 3^j
$$
which is odd if $n$ is odd and even if $n$ is even. So for odd $n,$ you get 
$$
3\,\cdot \,\frac{3^n-1}{2} +1 = \frac{3^{n+1}-1}{2}
$$
after $2n+2$ steps, while for even $n,$ you get 
$$
\frac{3^n-1}{2}
$$
after $2n+1$ steps.
For $n=2k+1,$ you get $\frac{3^{2k+2}-1}{2}$ after $2(2k+1)+2 = 4k+4$ steps.
For $n=2k+2,$ you get $\frac{3^{2k+2}-1}{2}$ after $2(2k+2)+1 = 4k+5$ steps.
A: More generally when we know the last k bits of the number we can compute directly the kth iteration (with the alternative Collatz function $T$).
It is easy to demonstrate that by induction. And, with a few habit of the mixed bases representation these results are really obvious.
You can see a little more explanation here:
Applying Collatz function iterations to large integers.
$T(n) = \left\{
  \begin{array}{ll}
    \frac{n}{2} & \text{if }n\text{ even}\\
    \frac{3n + 1}{2} & \text{if }n\text{ odd}\\
  \end{array}\right.$
$\forall k, \forall \alpha \in \mathbb{N}:$


*

*$T\big(\alpha:(0)_2\big) = \alpha$

*$T\big(\alpha:(1)_2\big) = \alpha:(2)_3$

*$T^k\big(\alpha:(\underbrace{0\dots00}_{k\text{ times}})_2\big) = \alpha$

*$T^k\big(\alpha:(\underbrace{1\dots11}_{k\text{ times}})_2\big) = \alpha:(\underbrace{2\dots22}_{k\text{ times}})_3\quad\equiv \alpha\ (\text{mod } 2)$
Where $(\dots)_2$ is a binary representation and $(\dots)_3$ a representation in base $3$.
