Structure of the 3n+1 stopping time

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

3n+1 flow chart
3n+1 flow chart

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

Order in chaos
Order in chaos

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}.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s