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!
Best Answer
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.