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

Title | theorem on Collatz sequences starting with Mersenne numbers |
---|---|

Canonical name | TheoremOnCollatzSequencesStartingWithMersenneNumbers |

Date of creation | 2013-03-22 17:34:32 |

Last modified on | 2013-03-22 17:34:32 |

Owner | PrimeFan (13766) |

Last modified by | PrimeFan (13766) |

Numerical id | 12 |

Author | PrimeFan (13766) |

Entry type | Theorem |

Classification | msc 11B37 |