Number of Collatz steps for Mersenne numbers

Question

I noticed that for all $k \in \mathbb{N} \geq 1$ the following is true (I tested up to $2^{5000}$):

$\text{Collatz_Steps}(2^{2k+1} - 1) + 1 = \text{Collatz_Steps}(2^{2k+2} - 1)$

Where $\text{Collatz_Steps}$ is the number of steps required to reach $1$.

Is there a proof for this?

Answer 1

Proof sketch:

For a number $2^n-1,$ the first $2n$ steps are the $3x+1$ step and the $x/2$ step in alternating order, until you reach $3^n-1.$

$3^n-1$ is even, so the next step is the $x/2$ step again. We have $$ \frac{3^n-1}{2} = \sum_{j=0}^{n-1} 3^j $$ which is odd if $n$ is odd and even if $n$ is even. So for odd $n,$ you get $$ 3\,\cdot \,\frac{3^n-1}{2} +1 = \frac{3^{n+1}-1}{2} $$ after $2n+2$ steps, while for even $n,$ you get $$ \frac{3^n-1}{2} $$ after $2n+1$ steps.

For $n=2k+1,$ you get $\frac{3^{2k+2}-1}{2}$ after $2(2k+1)+2 = 4k+4$ steps.

For $n=2k+2,$ you get $\frac{3^{2k+2}-1}{2}$ after $2(2k+2)+1 = 4k+5$ steps.

Answer 2

More generally when we know the last k bits of the number we can compute directly the kth iteration (with the alternative Collatz function $T$).

It is easy to demonstrate that by induction. And, with a few habit of the mixed bases representation these results are really obvious. You can see a little more explanation here: Applying Collatz function iterations to large integers.

$T(n) = \left\{ \begin{array}{ll} \frac{n}{2} & \text{if }n\text{ even}\\ \frac{3n + 1}{2} & \text{if }n\text{ odd}\\ \end{array}\right.$

$\forall k, \forall \alpha \in \mathbb{N}:$

• $T\big(\alpha:(0)_2\big) = \alpha$
• $T\big(\alpha:(1)_2\big) = \alpha:(2)_3$
• $T^k\big(\alpha:(\underbrace{0\dots00}_{k\text{ times}})_2\big) = \alpha$
• $T^k\big(\alpha:(\underbrace{1\dots11}_{k\text{ times}})_2\big) = \alpha:(\underbrace{2\dots22}_{k\text{ times}})_3\quad\equiv \alpha\ (\text{mod } 2)$

Where $(\dots)_2$ is a binary representation and $(\dots)_3$ a representation in base $3$.

Answer 3

See update with generalization at end

---

I find it a very nice observation. If I translate this in my style of notation, where I give the vector of exponents-of-$2$ to be divided in the "Syracuse"-style transformation $$ a_2 = { 3a_1+1\over 2^{A_1}} \qquad \text{ on odd $a_1$, and $A$ such that $a_2$ is odd too }$$ or more general $$ a_{k+1} = { 3a_k+1\over 2^{A_k}} $$ then I document the vector of $A_1,A_2,...$ occuring by iteration of $a_1$ downto $1$.
Some examples of your observation give then the vectors

                               ******
Ev1=TFind_T(2^5-1) [1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 4, 2, 2, 4, 3, 1, 1, 5, 4]
Ev2=TFind_T(2^6-1) [1, 1, 1, 1, 1, 4, 1, 2, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 4, 2, 2, 4, 3, 1, 1, 5, 4]
                               ******

Here the vectors of exponents for $a_1=2^5-1$ and for $a_1=2^6-1$ are nearly perfectly equal, only on two positions they differ (which are marked by the stars) and remarkably complementaring them out with leaving one unit difference in the whole vector-sum

Here are a couple more examples:

                                                  *****
Ev1=TFind_T(2^11-1) [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 1, 2, 1, 1, 3, 2, 2, 2, 1, 2, 3, 2, 1, 2, 1, 5, 1, 2, 2, 3, 1, 2, 2, 4, 2, 1, 1, 1, 1, 1, 1, 2, 4, 3, 3, 3, 1, 2, 3, 4]
Ev2=TFind_T(2^12-1) [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 2, 1, 1, 3, 2, 2, 2, 1, 2, 3, 2, 1, 2, 1, 5, 1, 2, 2, 3, 1, 2, 2, 4, 2, 1, 1, 1, 1, 1, 1, 2, 4, 3, 3, 3, 1, 2, 3, 4]
                                                  *****

                                                       ******
Ev1=TFind_T(2^13-1) [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 3, 1, 4, 1, 2, 1, 5, 5, 1, 1, 1, 1, 3, 1, 1, 4, 3, 1, 2, 2, 4, 2, 1, 1, 1, 1, 1, 1, 2, 4, 3, 3, 3, 1, 2, 3, 4]
Ev2=TFind_T(2^14-1) [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 2, 1, 3, 1, 4, 1, 2, 1, 5, 5, 1, 1, 1, 1, 3, 1, 1, 4, 3, 1, 2, 2, 4, 2, 1, 1, 1, 1, 1, 1, 2, 4, 3, 3, 3, 1, 2, 3, 4]
                                                       ******

                                                              *****
Ev1=TFind_T(2^15-1) [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 3, 1, 4, 1, 2, 1, 1, 1, 1, 1, 2, 1, 4, 3, 1, 4, 1, 2, 2, 2, 10, 2, 1, 3, 1, 2, 3, 4]
Ev2=TFind_T(2^16-1) [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 3, 1, 4, 1, 2, 1, 1, 1, 1, 1, 2, 1, 4, 3, 1, 4, 1, 2, 2, 2, 10, 2, 1, 3, 1, 2, 3, 4]
                                                              *****

---

Update Generalization to more cases (heuristic, not yet proven)

Let $j,A \in \mathbb N$ then

1. let $k = 4j+1$ then with $$a_1=k \cdot 2^{2A+1} -1 \qquad \qquad b_1=k \cdot 2^{2A+2} -1 \\ \text{Collatz_length}(a_1) = \text{Collatz_length}(b_1)-1 $$

2. let $k = 4j-1$ then with $$a_1=k \cdot 2^{2A+1} -1 \qquad \qquad b_1=k \cdot 2^{2A} -1 \\ \text{Collatz_length}(a_1) = \text{Collatz_length}(b_1)+1 $$

and the vector of exponents have the same near-identical relation as seen in my examples above