# theorem on Collatz sequences starting with Mersenne numbers

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.

Title theorem on Collatz sequences starting with Mersenne numbers TheoremOnCollatzSequencesStartingWithMersenneNumbers 2013-03-22 17:34:32 2013-03-22 17:34:32 PrimeFan (13766) PrimeFan (13766) 12 PrimeFan (13766) Theorem msc 11B37