theorem on Collatz sequences starting with Mersenne numbers

Theorem. Given a Mersenne number $m=2^n-1$ (with $n$ a nonnegative integer), the Collatz sequence starting with $m$ reaches $3^n-1$ in precisely $2n$ steps. Also, the parity of such a sequence consistenly alternates parity until $3^n-1$ is reached. For example, given $2^2-1=3$ gives the Collatz sequence 3, 10, 5, 16, 8, 4, 2, 1, in which $3^2-1=8$ is reached at the fourth step. Also, the least significant bits of this particular sequence are 1, 0, 1, 0, 0, 0, 0, 1.

As you might already know, a Collatz sequence results from the repeated application of the Collatz function $C(n)=3n+1$ for odd $n$ and $C(n)=\frac{n}{2}$ for even $n$. If I may, I’d like to introduce the iterated Collatz function notation as a recurrence relation thus: $C_0(n)=n$ and $C_i(n)=C(C_{i-1}(n))$ for all $i>0$. In our example, $C_0(3)=3$, $C_1(3)=10$, $C_2(3)=5$, etc. (We could choose to have $C_1(n)=n$ instead with only slight changes to the theorem and its proof).

Proof.

Obviously $m=C_0(2^n-1)=2^n-1$ is an odd number. Therefore $C_1(m)=2^{n}3-2$, an even number, and then $C_2(m)=2^{n-1}3-1$, $C_3(m)=2^{n-1}9-2$, $C_4(m)=2^{n-2}9-1$, $C_5(m)=2^{n-2}27-2$, etc. We can now generalize that if $i$ is odd, then $C_i(m)=2^{n-\frac{i-1}{2}}{3}^{\frac{i+1}{2}}-2$ and $C_i(m)=2^{n-\frac{i}{2}}{3}^{\frac{i}{2}}$ if $i$ is even. By plugging in $i=2n$, we get $C_i(m)=2^{n-\frac{2n}{2}}{3}^{\frac{2n}{2}}=2^{n-n}{3}^n-1=2^0{3}^n-1=3^n-1$, proving the theorem.∎

Of course the generalized formulas do not work when $i>2n$, nor does any of this give any insight into when a Collatz sequence starting with a Mersenne number reaches a power of 2. Likewise, the pattern of consistently alternating parity usually breaks down on or right after the $2n$th step.