## You are here

Hometheorem on Collatz sequences starting with Mersenne numbers

## Primary tabs

# 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.

## Mathematics Subject Classification

11B37*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections