Some details about 'Collatz Conjecture'?

Yes, there is no one who doesn't know this problem.My question is only about curiosity.

$$C(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ 3n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases}$$

On this problem, I caught something like this.I'm sure, We all realized that.

For example, $n=19$, we have $6$ odd steps.

We know that, even steps are not important, because each even number is converted to an odd number.

$19\Longrightarrow 29 \Longrightarrow 11\Longrightarrow 17 \Longrightarrow13 \Longrightarrow 5 \Longrightarrow 1$

Then, for $n=77$, We have also $6$ odd steps.

$77\Longrightarrow 29 \Longrightarrow 11\Longrightarrow 17 \Longrightarrow13 \Longrightarrow 5 \Longrightarrow 1$

For $n=9$

$9\Longrightarrow 7 \Longrightarrow 11 \Longrightarrow 17 \Longrightarrow 13\Longrightarrow 5 \Longrightarrow 1$

Again we have $k=6$ odd steps.

I want to know / learn / ask, for $k=6$, (Generalized: for any number $k$ ) can we produce a formula(s) to catch all such numbers, which gives the result $1$?

Thank you!

Solution 1:

Hint:

You can invert the sequence of odd steps as follows:

$$1\leftarrow\frac{2^k-1}3$$ for any $k$ such that the division is exact, i.e. all even $k$. In other words,

$$1\leftarrow\frac{4^k-1}3.$$

Now

$$\frac{4^k-1}3\leftarrow\frac{2^j(4^k-1)-3}9$$ for $j$ such that the division is exact, i.e. even $j$ when $k\bmod3=1$ and odd $j$ when $k\bmod3=2$.

Hence

$$\frac{4^k-1}3\leftarrow\frac{4^j2^{k\bmod3-1}(4^k-1)-3}9\text{ with }k\bmod3\ne0.$$

More generally, you will get a sum of powers of $4$ with small coefficients and restrictions on the exponents, over a power of $3$. Doesn't seem simple.

Solution 2:

If you search a single formula for any $k$, here it is:

$$n_k=\frac{2^{l_1+l_2+...+l_k}}{3^k}-\frac{2^{l_2+l_3+...+l_k}}{3^k}-\frac{2^{l_3+l_4+...+l_k}}{3^{k-1}}-\frac{2^{l_4+l_5+...+l_k}}{3^{k-2}}-...-\frac{2^{l_{k-1}+l_k}}{3^3}-\frac{2^{l_k}}{3^2}-\frac{2^0}{3^1}$$

e.g.

$$19=\frac{2^{4+3+2+1+3+1}}{3^6}-\frac{2^{3+2+1+3+1}}{3^6}-\frac{2^{2+1+3+1}}{3^5}-\frac{2^{1+3+1}}{3^4}-\frac{2^{3+1}}{3^3}-\frac{2^{1}}{3^2}-\frac{2^0}{3^1}$$

The dificulty is to find the $l_k$ for which $n_k$ is an integer.

The $l_k$ are the number of times you divide by 2 to jump from an odd to another odd.

e.g. for $19$, $l_6=1$ because you divide $3*19+1$ only once to get the next odd $29$. $l_5=3$ because you divide $3*29+1$ three times by 2 to get the next odd $11$...

When an $l_k$ is known, any $l_k$ of the same parity will work (e.g. for $19$, $l_6=1$ is odd, so any odd value of $l_6$ will work).

Solution 3:

Use linear combinations of the Lucas sequences $U_n(5,4)$ and $V_n(5,4)$ to quickly generate infinitely many odd numbers the same number of steps from $1$.

These can alternatively be generated by iterating the function $f(x)=4x+1$ on your starting integer so taking $19$ as your example the following numbers share the same immediate successor and therefore the same number of steps:

$19,77,309,1237,4949,19797,\ldots$

The closed form for these is $4^n\cdot 19+\frac{4^n-1}{3}$

Or you could lift $19$'s successor $29$ (which is $5$ steps away) to infinitely many numbers the same distance away from $1$ and take their immediate predecessors. This gets a bit messy as some of those are multiples of $3$ and have no predecessor, others are $\equiv1\mod 3$ and therefore their predecessor is at $\frac{4x-1}{3}$ and others still are $\equiv2\mod 3$ and therefore their predecessor is at $\frac{2x-1}{3}$.

But you can avoid that problem by taking every third "lift" to give you predecessors which are all equivalent mod $3$. The function $4x+1$ composed three times is $64x+21$, and $29\equiv2\mod 3$ so its smallest immediate predecessor is found at $\frac{2x-1}{3}$, so all of the numbers of the form:

$\dfrac{2(4^{3n}\cdot19+21)-1}{3}$

are also $6$ steps from $1$.

I mentioned there are two classes of immediate predecessors - those found at $\frac{2x-1}{3}$ and those found at $\frac{4x-1}{3}$. We can find the numbers having this second type of immediate predecessor two compositions of $4x+1$ above $29$. That's $16x+5$; i.e. at $469$ and we can then find infinitely many predecessors to that which are again 6 steps away. The smallest of them is given by $\frac{4x-1}{3}$, i.e.:

$\dfrac{4\cdot469-1}{3}=625$

And again there are infinitely many immediate predecessors of $469$, all of them $6$ steps from $1$. These are again given by:

$4^n\cdot625+\dfrac{4^n-1}{3}$

I could go on but you're probably bored by now...

P.S. What you ask for; a general form to generate all the numbers $6$ steps from $1$ would probably solve the problem, and this is a famous unsolved problem.