theorem on Collatz sequences starting with Mersenne numbers


Theorem. Given a Mersenne number m=2n-1 (with n a nonnegative integer), the Collatz sequence starting with m reaches 3n-1 in precisely 2n steps. Also, the parity of such a sequenceMathworldPlanetmath consistenly alternates parity until 3n-1 is reached. For example, given 22-1=3 gives the Collatz sequence 3, 10, 5, 16, 8, 4, 2, 1, in which 32-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)=n2 for even n. If I may, I’d like to introduce the iterated Collatz function notation as a recurrence relationMathworldPlanetmath thus: C0(n)=n and Ci(n)=C(Ci-1(n)) for all i>0. In our example, C0(3)=3, C1(3)=10, C2(3)=5, etc. (We could choose to have C1(n)=n instead with only slight changes to the theorem and its proof).

Proof.

Obviously m=C0(2n-1)=2n-1 is an odd numberMathworldPlanetmathPlanetmath. Therefore C1(m)=2n3-2, an even number, and then C2(m)=2n-13-1, C3(m)=2n-19-2, C4(m)=2n-29-1, C5(m)=2n-227-2, etc. We can now generalize that if i is odd, then Ci(m)=2n-i-123i+12-2 and Ci(m)=2n-i23i2 if i is even. By plugging in i=2n, we get Ci(m)=2n-2n232n2=2n-n3n-1=203n-1=3n-1, proving the theorem. ∎

Of course the generalized formulasMathworldPlanetmathPlanetmath 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 2nth 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