# Structure of the 3n+1 stopping time

Returning to the stopping time of the ${3n+1}$ process (first part here):

Here is the plot of the stopping time embellished with a few logarithmic functions.

This structure is explained by looking at the number of ${3x+1}$ operations that a number experiences before reaching ${1}$.

No ${3x+1}$ operations. Such number are obviously of the form ${2^m}$, with stopping time ${m}$. These creates the points ${(2^m,m)}$ which lie on the curve ${y=\log_2 x}$.

One ${3x+1}$ operation. To find such numbers, follow their orbit backward: a series of multiplication by ${2}$, then ${(x-1)/3}$ operation, then more multiplications by ${2}$. This leads to numbers of the form ${2^n \dfrac{2^{m}-1}{3}}$ where ${m}$ must be even in order for ${2^m-1}$ to be divisible by ${3}$. The stopping time is ${n+m+1}$. Since ${2^n \dfrac{2^{m}-1}{3} \approx \dfrac{2^{n+m}}{3}}$, the corresponding points lie close to the curve ${y=1+\log_2(3x)}$. Also notice that unlike the preceding case, clusters appear: there may be multiple pairs ${(n,m)}$ with even ${m}$ and the same ${n+m}$. The larger the sum ${n+2m}$ is, the more such pairs occur.

Two ${3x+1}$ operations. Tracing the orbit backwards again, we find that these are numbers of the form

${2^p\dfrac{2^n \dfrac{2^{m}-1}{3} -1}{3}}$

It is straightforward to work out the conditions on ${(m,n)}$ which allow both divisions by ${3}$ to proceed. They are: either ${n}$ is odd and ${m \equiv 4 \mod 6}$, or ${n}$ is even and ${m\equiv 2 \mod 6}$. In any event, the stopping time is ${m+n+p+2}$ and the number itself is approximately ${2^{m+n+p}/9}$. On the above chart, these points lie near the curve ${y=2+\log_2(9x)}$. Clustering will be more prominent than in the previous case, because we now deal with triples ${(n,m,p)}$ that will be nearby each other if ${n+m+p}$ is the same.

k) ${k}$ operations of ${3x+1}$ kind. These yield the points near the curve ${y=k+\log_2(3^k x)}$, or, to put it another way, ${y=k\log_2 6+\log_2(x)}$. The plot above shows such curves for ${k=0,1,\dots,11}$.