# Transform Collatz sequence to a strictly decreasing sequence

While playing with numbers, I found that every Collatz sequence $$n, T(n), T^2(n), \ldots, 1$$ can be associated with a strictly decreasing sequence of integers.

The Collatz conjecture asserts that a sequence defined by repeatedly applying the Collatz function \begin{align*} T(n) = \begin{cases} (3n+1)/2 &\text{ if n \equiv 1 \pmod{2}, or}\\ n/2 &\text{ if n \equiv 0 \pmod{2}} \end{cases} \end{align*} will always converge to the cycle passing through the number 1 for arbitrary positive integer $$n$$.

Note that multiplying the $$n$$ by positive odd integer $$a$$ does not affect the result of the modulo 2 operation. By multiplying the Collatz function by an odd integer $$a$$, and tracking the $$m = an$$ rather than $$n$$, we get \begin{align*} S(m) = \begin{cases} (3m+a)/2 &\text{ if m \equiv 1 \pmod{2}, or}\\ m/2 &\text{ if m \equiv 0 \pmod{2},} \end{cases} \end{align*} where each iterate $$S^i(m) = a \, T^i(n)$$.

Now we can choose a sufficiently large positive integer $$A$$ and track $$m = 3^A n$$. But we do a little trick. Instead of multiplying the $$m$$ by 3 in the "odd" branch, we just replace $$3^A$$ with $$3^{A-1}$$, and track the $$3^{A-1}$$ from that moment on (the effect is the same). We get the following algorithm:

It can be shown that every next $$m$$ is strictly less than the previous $$m$$. Since every next $$m$$ is smaller than its predecessor, we must hit $$m = 1$$ at the end. Since we track $$m = 3^A n$$, once the $$m = 1$$, then the $$A = 0$$ and $$n = 1$$. This implies that for arbitrary positive integer $$n$$, the sequence $$n, T(n), T^2(n), \ldots$$ leads to one. Note that once the $$m = 3^A$$, then the $$n = 1$$.

I am however stuck to show that there is always the sufficiently large $$A$$ for a given $$n$$. Is it possible to show this? I found out that the sufficiently large $$A$$ does not always exist for the $$3x-1$$ problem.

## Example

The trajectory starting at $$n=19$$ with $$A=9$$ (termination at $$m = 1$$): $$\begin{matrix} n & m & A \\ \hline 19 & 373977 & 9 \\ 29 & 190269 & 8 \\ 44 & 96228 & 7 \\ 22 & 48114 & 7 \\ 11 & 24057 & 7 \\ 17 & 12393 & 6 \\ 26 & 6318 & 5 \\ 13 & 3159 & 5 \\ 20 & 1620 & 4 \\ 10 & 810 & 4 \\ 5 & 405 & 4 \\ 8 & 216 & 3 \\ 4 & 108 & 3 \\ 2 & 54 & 3 \\ 1 & 27 & 3 \\ 2 & 18 & 2 \\ 1 & 9 & 2 \\ 2 & 6 & 1 \\ 1 & 3 & 1 \\ 2 & 2 & 0 \\ 1 & 1 & 0 \\ \end{matrix}$$

• This is a trick, but it won't work in case of cycles or divergent sequences, where $A$ will run out at some point Apr 23, 2020 at 8:43
• @Collag3n So it seems like another hopeless attempt :) Apr 23, 2020 at 9:25
• Nice try anyway :) Apr 23, 2020 at 12:43
• @Collag3n I'm still thinking about it... This attempt clearly does not work in the case of a cycle. But is this really also the case of a divergent trajectory? Since the product $n \, 3^A$ has to shrink at every step... Apr 23, 2020 at 14:12
• The $3^A$ you add just hide the $n$ behind. If $n$ is part of a divergent trajectory, the $3^A$ you add to it will shrink down and at some point will disappear, but your original trajectory won't and will continue....with "naked" $n_i$'s. Apr 23, 2020 at 17:29

$$7 = \frac{2^5}{3^5}\cdot 2^{(3+2+1+0+0)} - \frac{2^4}{3^5}\cdot 2^{(2+1+0+0)} - \frac{2^3}{3^4}\cdot 2^{(1+0+0)} - \frac{2^2}{3^3}\cdot 2^{(0+0)} - \frac{2^1}{3^2}\cdot 2^{(0)} - \frac{2^0}{3^1}\\ 11 = \frac{2^4}{3^4}\cdot 2^{(3+2+1+0)} - \frac{2^3}{3^4}\cdot 2^{(2+1+0)} - \frac{2^2}{3^3}\cdot 2^{(1+0)} - \frac{2^1}{3^2}\cdot 2^{(0)} - \frac{2^0}{3^1}\\ 17 = \frac{2^3}{3^3}\cdot 2^{(3+2+1)} - \frac{2^2}{3^3}\cdot 2^{(2+1)} - \frac{2^1}{3^2}\cdot 2^{(1)} - \frac{2^0}{3^1}\\ 13 = \frac{2^2}{3^2}\cdot 2^{(3+2)} - \frac{2^1}{3^2}\cdot 2^{(2)} - \frac{2^0}{3^1}\\ 5 = \frac{2^1}{3^1}\cdot 2^{(3)} - \frac{2^0}{3^1}\\ 1 = \frac{2^0}{3^0}$$