Closed formula for distances relating to Collatz conjecture?

Question

I've been messing with the collatz conjecture for a while now, and I've found that another way to prove it is through proving that for any number $n$ there is at least one $k$ ($n$ is any odd input and $k$ is the total stopping time of $n$) where the output of the function $$2^{\lceil log_2{(n3^k)} \rceil}-n3^k$$can be written in the form of $$3^{k-1}(2^{a_1}) + 3^{k-2}(2^{a_2}) + ... + 3^{k-k}(2^{a_{k}})$$ where there are $k$ terms and $a_1 < a_2 < a_3 $ and so on. Additionally, $a_1$ must be zero. For example, when $k = 2$, the numbers which can be written in this form are 5, 7, 11, 19, 35,... which are $3^{2-1}(2^0) + 3^{2-2}(2^{1,2,3,4,5})$. A number with total stopping time 2 should be one of these numbers away from the nearest larger power of 2 when multiplied by $3^2$. ex: $2^{\lceil log_2{((3)3^2)}\rceil}-(3)3^2 = 5$, which is included on the list for $k = 2$. I'd like to know if there is a closed formula for numbers that can be written this way. I doubt it, because each value of $k$ adds another variable which can be tweaked, but my knowledge is severely limited.

Answer 1

For odd integer $n_i$, $n_{i+1} = \dfrac{3n_{i} + 1}{2^{a_1}}$. Define ${A_i = \sum\limits_{j=1}^{i}a_j}$ for $i \gt 0$ and $A_0=0$, then $$n_{k+1} = \dfrac{3^kn_1 + \sum\limits_{i=0}^{k-1}3^{k-1-i}2^{A_i}}{2^{A_k}}$$ If $n_{k+1} = 1$ then $$n_1 = \dfrac{2^{A_k} - \sum\limits_{i=0}^{k-1}3^{k-1-i}2^{A_i}}{3^k}$$ This is your equation except that the exponent for $2$ should be $A_k$ which is the total number of divide by $2$'s to get to 1. So $n_1$ reaches $1$ if for some $k$ if there are integer $a_i \gt 0$ and hence $A_i$ that satisfy this equation. Note that if there is a solution for a given $k$ and $a_i$, then there is also a solution for $k+1$ by appending $a_{k+1} = 2$. This corresponds to looping once the sequence reaches $1$. So there is always a trivial solution for any $k$ which is $n_i = 1$ with $a_i = 2$ which corresponds to the sequence $1,1,1,1,...$ with $a_i = 2$ and the sum = $2^{2k} - 3^k$ and $A_k = 2k$. Similarly, $a_i = 4,2,2$ is a solution for $k = 3$ corresponding to the sequence $5,1,1$ These probably aren't the solutions you're interested in though. There apparently isn't a known closed form solution to finding the $k$ and $a_i$ given an $n_1$ otherwise the Collatz conjecture would have been proven since this equation (that you rediscovered) is known (a bit of a flip answer I know).

Answer 2

For odd integer $\quad n \quad$ fixed $ \quad n_0=n \quad$ and for $\quad i>0 \quad$ fixed

$n_i=\frac{3 \cdot n_{i-1} +1}{2^{a_i}} \quad$ with $\quad n_i \quad$ odd integer

then

$n_1=\frac{3 \cdot n_0 +1}{2^{a_1}}=\frac{3 \cdot n +1}{2^{a_1}}$

$n_2=\frac{3 \cdot n_1 +1}{2^{a_2}}=\frac{3 \cdot \frac{3 \cdot n +1}{2^{a_1}} +1}{2^{a_2}}$

$\cdots$

$n_k=\frac{3^k\cdot n +3^{k-1} +\sum\limits_{i=0}^{k-2}{3^{i}\cdot2^{\sum_{j=1}^{k-1-i} {a_j}}} }{2^{\sum_{j=1}^{k}{a_j}}}$

then define $ \quad k_{e}=\sum_{j=1}^{k}{a_j} \quad$ number of times the sequence has been divided by $\quad 2 \quad$

if $ \quad n_k=1$ we have

$$3^k\cdot n=2^{k_{e}} -3^{k-1}-\sum\limits_{i=0}^{k-2}{3^{i}\cdot2^{\sum_{j=1}^{k-1-i} {a_j}}} $$

then

$$3^k\cdot n<2^{k_{e}}$$

from which

$$k_{e}>\log_2{(n\cdot 3^k)}$$

or

$$\quad k_{e} \geq \left\lceil \log_2{(n\cdot 3^k)} \right\rceil$$

It's probably also possible to come up with an upper bound for $\quad k_{e}$.