The $k^{th}$ iteration of $2^k-1$,$2^k-3$ ,and $2^{k}-11$ and others

Question

With the short cut version of the $3x+1$ conjecture, $$f(x)=\frac {3x+1}{2},\text {if $x$ is odd }$$ and $$f(x)=\frac {x}{2},\text {if $x$ is even }$$ numerical experiments show that $$ f^k(2^k-1)=3^{k}-1$$ is true for $k\ge 1$ $$ f^k(2^k-3)=3^{k-2}-1$$ is true for $k>3$ $$ f^k(2^k-11)=3^{k-4}-1$$ is true for $k>5$

For eample for $k=10$ we have$2^{10}-11=1013$

Thus $$f^{10}(1013)=3^6-1=728$$ Which is verified by the iterations $$1013\to 1520\to 760\to 380\to190\to $$

$$95\to143\to 215\to323\to485\to728$$ I also have similar formulas for $2^k+1$, $2^k+3$, and $2^k+5$

My question is

" Are these formulas well known ? "

Answer 1

Here I give a way to manipulate that easily, with a representation in base 2 and 3: Applying Collatz function iterations to large integers

With $(\dots)_2$ the binary representation and $(\dots)_3$ the representation in base $3$, something like $\alpha:(0101)_2:(2)_3$ represents $\alpha \times 2^4 \times 3 + (0101)_2 \times 3 + (2)_3 = \alpha \times 2^4 \times 3 + 5 \times 3 + 2 = \alpha \times 2^4 \times 3 + 17$. And it is possible to mix figures in base 2 and figures in base 3.

(A little online tool to manipulate this kind of mixed radix.)

With this representation the problem 3x+1 can be formulate like that. Forall $\alpha \in \mathbb{N}$ :

• $\alpha:(0)_2 \longrightarrow \alpha$, for the even case
• $\alpha:(1)_2 \longrightarrow \alpha:(2)_3$, for the odd case

So the trivial case:

$\alpha:(\underbrace{0\dots00}_{k\text{ times}})_2 \stackrel{k}{\longrightarrow} \alpha$

A well known generalization of the first statement of the question, with $2^k - 1$:

$\alpha:(\underbrace{1\dots11}_{k\text{ times}})_2 \stackrel{k}{\longrightarrow} \alpha:(\underbrace{2\dots22}_{k\text{ times}})_3$

For the second statement, $2^k - 3 = 2^k - 1 - (10)_2$ so:

$\alpha:(\underbrace{1\dots101}_{k\text{ times}})_2 \longrightarrow \alpha:(\underbrace{1\dots10}_{k-1\text{ times}})_2:(2)_3 \longrightarrow \alpha:(\underbrace{1\dots1}_{k-2\text{ times}})_2:(1)_3 = \alpha:(\underbrace{1\dots1}_{k-3\text{ times}})_2:(2)_3:(0)_2 \longrightarrow \alpha:(\underbrace{1\dots1}_{k-3\text{ times}})_2:(2)_3 \stackrel{k-3}{\longrightarrow} \alpha:(\underbrace{2\dots22}_{k-2\text{ times}})_3$

For the third statement, $2^k - 11 = 2^k - 1 - (1010)_2$ so:

$\alpha:(\underbrace{1\dots10101}_{k\text{ times}})_2 \longrightarrow \alpha:(\underbrace{1\dots1010}_{k-1\text{ times}})_2:(2)_3 \longrightarrow \alpha:(\underbrace{1\dots101}_{k-2\text{ times}})_2:(1)_3 = \alpha:(\underbrace{1\dots10}_{k-3\text{ times}})_2:(2)_3:(0)_2 \longrightarrow \alpha:(\underbrace{1\dots10}_{k-3\text{ times}})_2:(2)_3 \longrightarrow \alpha:(\underbrace{1\dots1}_{k-4\text{ times}})_2:(1)_3 = \alpha:(\underbrace{1\dots1}_{k-5\text{ times}})_2:(2)_3:(0)_2 \longrightarrow \alpha:(\underbrace{1\dots1}_{k-5\text{ times}})_2:(2)_3 \stackrel{k-5}{\longrightarrow} \alpha:(\underbrace{2\dots22}_{k-4\text{ times}})_3$

Answer 2

It is well known and proven that any odd number can be written as $a\cdot2^k-1$ and reaches $a\cdot3^k-1$ (which is even) in exactly $k$ steps of $f(x)=\frac {3x+1}{2}$.

It is also known and proven/provable for other "base" trajectories (see How to prove this inequality: $f(2h-1)≤\frac{3h-1}{2}$ + comments)

From there you can combine and find some other paths: e.g. set $a=2^{k-1}-1$, we know that $2^k-3=a\cdot 2-1$ goes to $a\cdot3-1=3\cdot 2^{k-1}-4$ which goes to $3\cdot 2^{k-3}-1$ which himself goes to $3\cdot 3^{k-3}-1=3^{k-2}-1$

Now, the number of possible combination is growing fast with $k$, so I am not sure we can do something with all of them, but some of them are interesting to study (e.g one particular case of $a2^k-1$: inverse V-shape reaching the stopping point Showing $3^iq-2^{i-p}\neq2^pq-1$, with $p:=\lceil i\,\log_23\rceil$, $q:=\left\{\frac{2^{i}\,3^{2^{p-i-2}}}{2^p3^i}\right\}$, $i>6$)

Answer 3

Let's for compactness assume our transformation is $ a_{k+1} = {3a_k+1\over2^{A_k}} $ where $A_k$ is chosen that $a_{k+1}$ is odd.

Then simply write $a_1 = 2^k+r_1$ where $r_1$ is known to converge to $1$ in $\tau(r_1)$ steps ("total stopping time"). Then let $S$ be the sum of all $A_k$ in the exponents (meaning all even steps in the original Collatz-definition).
Then if $k \gt S $ then we have $$ \begin{array} {} a_2 &= 3{2^k\over 2^{A_1}} + {3r_1+1 \over 2^{A_1}} &= 3{2^k\over 2^{A_1}} + r_2 \\ a_3 &= 3^2{2^k\over 2^{A_1+A_2}} + r_3 \\ \vdots && (\tau() \text{-steps giving $S$ as sum of all $A_k$}) \\ a_\tau &= 3^\tau 2^{k-S}+ r_\tau &= 3^\tau 2^{k-S} + 1 \end{array}$$

Of course if still $k>S$ we can iterate this further $u$ times, because $1 \to 1$ by division through $2^2$ as long as $k>S-2u$ getting $3^{\tau + u}2^{k-S-2u}+1$

Similarly this can be done with numbers of the form $a_1=2^k + r_1$ where $r_1$ is $-1$ or in general is known to converge to the trivial cycle in the negative numbers or to one of the other known cycles in the negative numbers.