In the Collatz function, why does $2^k-1$ reach $3^k-1$ after $2k$ steps, and could it be used to find divergent trajectories?

Question

If you start calculating the Collatz function from an integer of the form $2^k-1$, you will reach $3^k-1$ after $2k$ steps. So, it is possible to pick a starting value that continuously zig-zags upwards for a period of time that can be easily defined. Has this property been used in trying to find divergent trajectories?

One could say something like that when the starting value grows exponentially, the longest possible continuously growing sub-sequence expands linearly. Well.. you get the point

Answer 1

Note that $2^k-1$ is odd for each $k\in\mathbb N$, and the Collatz function applied to this gives $\frac{3(2^k-1)+1}{2}=\frac{3\cdot 2^k-2}{2}=3\cdot 2^{k-1}-1$. This is again odd, and a similar calculation shows that the next step is $3^2\cdot 2^{k-2}-1$. Continuing this process leads to $3^n\cdot 2^{k-n}-1$ after $n$ steps which will end up in $3^k-1$ after $n=k$ steps.

Answer 2

This observation can be used in the $2$-adic numbers. If you start at $-1$ in the $2$-adic numbers, you get an infinite cycle (actaully, it even works in $\mathbb Z$ itself, but then it is not clear that your $2^n-1$ is an approximation to $-1$).

Start at $-1$: $$ -1 \mapsto -3 \mapsto -7 \mapsto -15 \mapsto \dots \mapsto 1-2^n \mapsto \dots $$

Answer 3

The even values adjacent to the odds you normally work with, can be found as rows of Nicomachus's Triangle. With $k=3$ (say) the rows are structured: $$2^3 \cdot 3^0, 2^2 \cdot 3^1, 2^1\cdot 3^2, 2^0\cdot 3^3$$ $$8,12,18,27$$ Subtract one to get your values.

Answer 4

Did you also observe, that all numbers of the form $$2 \cdot 4^k +1 \to 2 \cdot 3^k+1$$ transfer in a analoguous way?

Examples
$ \displaystyle \small{ 9 = 2 \cdot 4^1 +1 \to 7 = 2 \cdot 3^1 +1 \\ 33 = 2 \cdot 4^2 +1 \to 25 \to 19 = 2 \cdot 3^2 +1 \\ 129 = 2 \cdot 4^3 +1 \to 97 \to 73 \to 55 = 2 \cdot 3^3 +1 \\ \cdots } $

and also of the form

$$ 2 \cdot 4^k \cdot x +1 \to 2 \cdot 3^k \cdot x+1$$ The key here is, that with some number $a = 2^A \cdot 2x + r_a $ (with $ r \lt 2^A$ ) the transformation can be looked at as separated in the two parts $ (2^A \cdot 2x) \cdot 3$ and $r\cdot 3+1$ and because in our examples $r=-1$ in your example and $r=+1$ in my additional example form the "trivial" loops $ -1 \to -1 $ (by $((-1) \cdot 3+1)/2$ and$ +1 \to +1 $ (by $((+1) \cdot 3+1)/4$

And whenever the residuum $r_a$ is the same before and after the transformation, that transformation is repeatable as long as enough powers of $2$ resp of $4$ are present as cofactors of the $2x$ and that powers are converted it the equivalent powers of $3$.

---

This idea can also be extended; one might look at numbers whose residues after decomposition into $2^A \cdot 2 \cdot x +r $ are $-5,-7$ or members of the other cycle in the negative numbers then we can formulate similar observations (though cyclic with longer period than only 1).