# Deriving a better approximation for the sum of steps in the Collatz conjecture

Let $$S(n)$$ be the number of steps required for $$n$$ to reach $$1$$ in the 3n+1 problem (A006577). As showed in other posts, $$S(n)$$ is locally random, but a local average/estimate $$s(n)$$ can be calculated (this can also be seen 'empirically'), such that $$s(n)=b\ln(n)$$ Where $$b=\frac{3}{\ln(4/3)}\approx10.43$$. This can be derived by noting that $$s(n)=\frac{1}{2}\left(1+s\left(\frac{n}{2}\right)\right)+\frac{1}{2}\left(2+s\left(\frac{3n}{2}\right)\right)$$ However, the value of the constant $$b$$ does not change if $$s(n)=b\ln(n)+c$$, for any constant $$c$$, that is, when substituting the expression in the above equation, all $$c$$ terms get cancelled out. Therefore, the problem is to derive the 'correct' value for $$c$$ with another approach.

Due to the random behavior of $$S(n)$$, I figured that considering the sum $$f(N)=\sum_{k=1}^{N}S(k)$$ would provide a better behavior, as the fluctuations in $$S(n)$$ would be negligible for big $$N$$. In this sense, $$f(N)=\sum_{k=1}^{N}S(k)\sim\sum_{k=1}^{N}s(k)=b\ln(N!)+cN$$ By calculating the value of $$f(N)$$ at every power of two from $$2^0$$ to $$2^{32}$$ and doing a least squares regression, I get that $$f(N)\approx\frac{3}{\ln(4/3)}\ln(N!)-2.4544N$$ Has an $$R^2$$ of $$0.9999999999611$$. Just to demonstrate, $$f(2^{32})=938,111,615,297$$, while the approximation gives $$\approx938,114,543,463$$, an error of only 0.0003%.

Is there a way to derive a value for $$c$$ other than empirically?

Edit

It seems that a heuristic or probabilistic argument is not sufficient. Consider the following probabilistic procedure on a given number $$n$$: return $$n/2$$ with probability $$50$$% or return $$\frac{3n+1}{2}$$ with probability $$50$$%. Repeat with the result until it gets $$\leq1$$ while counting the number of steps (incrementing by 1 when $$n/2$$ and by 2 when $$(3n+1)/2$$). If you use this probabilistic version of the Collatz conjecture, the value of $$b$$ remains unchanged, as expected, but, by doing a Python simulation, the value of $$c$$ changes to $$11.19\pm0.01$$, which is extremely different to the value of $$-2.4544$$ found in the original problem, suggesting that something else is going on.

• What is the question ? You have apparently derived a function with great accuracy. What else do you want ? Oct 20, 2022 at 9:29
• @Peter it is at the end of the question. I want to derive the value of $c$ in a way other than empirically, in the same way it was done for the value of $b$. Oct 20, 2022 at 13:25
• Even after averaging, the right constant $c$ (if there is one) retains a very sensitive dependence on the behavior at small values of $n$. For example, if you were to redefine $S(n)$ to be the number of steps to reach $2$ instead of $1$, all of its values except $S(1)$ would decrease by $1$, so the averages would decrease by nearly $1$. So I suspect that any method to compute $c$ with increasing precision will need to examine an increasing portion of the actual Collatz tree rather than making an approximation. Oct 25, 2022 at 1:10
• @AndersKaseorg - here is my observation, given as a comment to my answer in the previous version of the question: "yes, I've already seen this; but I've so far no real idea for the consturction of the constant c. When I change the set of points-to-regress-on I only observed that it comes out much variable and my guess is it would tend to zero for larger and larger n - but I've no idea of its true structure. I'm not going deeper in this, but am curious as to what you'll find..." Oct 30, 2022 at 7:50

Maybe we can use the following series, which is just the generalization of the original one (it means: half of the numbers are odd, $$\frac{1}{4}$$ of the numbers are divisible by 2 and not by 4, $$\frac{1}{8}$$ of the numbers are divisible by 4 and not by 8, etc.)

$$s(n) = \frac{1}{2}\left(2+s(\frac{3n}{2})\right) + \sum_{k = 0}^{\infty}\frac{1}{2^{2+k}}\left(1+k+s(\frac{n}{2^{1+k}})\right)$$

in order to approximate c, we slightly modify the above infinite series to a finite one:

$$s(n) = \frac{1}{2}\left(2+s(\frac{3n}{2})\right) + \sum_{k = 0}^{N-1}\frac{1}{2^{2+k}}\left(1+k+s(\frac{n}{2^{1+k}})\right) + \frac{1}{2^{2+N}}\left(1+N+S(1)\right)$$

then, try plugging the equation $$s(n) = b\ln n+c$$. It should give you the value of c depending on N.

Now I'll explain the assumption of the modification. Assume $$2^N\leq n< 2^{N+1}$$, then, the infinite series must stop when $$k$$ goes to $$N$$ (there is no number divisible by $$2^{N+1}$$).

• Interesting idea. I will try to see if I can derive $c$ from it. But, shouldn't there be an $N$ in the $\frac{1}{2^{2+N}}(1+S(1))$ term? that is, $\frac{1}{2^{2+N}}(1+N+S(1))$ Oct 29, 2022 at 14:49
• I've tested it, and it really doesn't seem to give correct results, apparently the value of $c$ goes to infinity as $n\rightarrow\infty$. I believe it has to do with the fact that your finite sum is essentially the infinite one for large $n$, and note that the $c$ terms are cancelled in it, that is, we get a $c\cdot0$. In the case of the finite sum, it is $c$ times a really small number, and when isolating $c$ it will, consequently, result in a really large number. Oct 29, 2022 at 15:17
• I edited the question to include an observation I've made that also adds to my previous comment. Oct 29, 2022 at 17:32