Mersenne numbers in the Collatz Conjecture

Question

I've noticed a fun little thing about the Mersenne numbers for the Collatz conjecture$$2^n-1$$is odd$$3*2^n-3+1$$$$3*2^n-2$$is even$$3*2^{n-1}-1$$is odd $$3^22^{n-1}-3+1$$$$3^22^{n-1}-2$$is even$$3^22^{n-2}-1$$$$...$$$$3^n-1$$ Has this been noticed before? It explains why Mersenne numbers have rather high maximums.

Answer 1

Indeed, this has been noticed before (but good job spotting it!). I'm not sure what would qualify as an answer, but you may find the following interpretation interesting.

In general, the numbers $n$ and $2k+n$ behave the same way under the collatz iteration (i.e. one is odd if and only if the other is) and, depending on how many factors of $2$ divide $k$, they 'follow each other' until the factors of $2$ are exhausted. For example:

$2^{4}+1 \to 3*2^{4}+4 \to 3*2^{2}+1 \to 9*2^{2}+4 \to 9*2^{0}+1 \to 27*2^{0}+1 \to ?$

where (?) means we have no way of telling whether the given number is even or odd without evaluating it (well, we certainly know it's even but we have no idea how many factors of $2$ divide it). So we could simplify the above by just noting $1 \to 4 \to 2 \to 1$ under the collatz iteration. Cute!

This is actually an attractive route to trying to prove the conjecture, by considering $2^{a}+k$ for various $k$, and showing that any number of this form converges to a smaller number under the iteration (for instance, every integer of the form $4n+1$ tends to $1$ by this argument).

However, if you try to do this then you rapidly get an out of control branching. But could it be made to work if only you're persistent enough? The answer is no, and the reason is every integer of the form $2^{a}-1$ will increase for at least $a$ steps in a row, as you have noticed (and in particular doesn't decrease fast enough for our proof). Just as $4n+1$ was linked to the loop $1 \to 4 \to 2 \to 1$, we can view this problem as being due to the loop $-1 \to -2 \to -1$ if we perform the iteration on negative integers.

You get similar behaviour for integers of the form $2^{a}-5$ and $2^{a}-17$, for similar reasons (try it out!)