# Collatz stopping times

The maximum stopping times for the Collatz $3x+1$ function have been computed up to about $x = 10^{18}$, given at $3x+1$ delay records. Plotting those results gives this:

A more interesting presentation is given on a semi-log plot:

It can be seen that the stopping time tends to a line as $x$ increases, and is confined to relatively narrow bounds. If anything, it seems to be tending to slightly narrower bounds as $x$ increases. Using a best fit of the upper part of the curve gives this equation:

$S=147.8\log_{10}x-366.9$

where $S$ is the maximum stopping time.

My question is, is there a (perhaps statistical) argument for why the maximum stopping time would tend to follow this line?

A further question is what is the likelihood that the relation could hold at higher powers of 10. For example, $x_0=10^{200}$ gives a predicted maximum stopping time for $x<x_0$ of about 29,194.

Suppose $x$ is a number whose Collatz iteration reaches the familiar cycle $4 \to 2 \to 1 \to 4 \to \dots$ Then there is a number $S_x$, the number of iterates before reaching $1$, and a number $p_x$, which is the fraction of its iterates that are even (again counting only until the first time that the sequence reaches 1). For example, $S_5=5,p_5=4/5$. An even Collatz iterate gives a division by 2 and an odd Collatz iterate roughly gives a multiplication by 3, so the Collatz sequence should be just a little bit bigger than $x_n=x 2^{-np_x} 3^{n(1-p_x)}=x 3^n 6^{-np_x}=x (3 \cdot 6^{-p_x})^n$ (bigger because I've dropped the $+1$s). If $p_x>\log(3)/\log(6)$ which is between $0.61$ and $0.62$ then this goes exponentially to zero.
The statement $S_x \sim k \log(x)$ for a constant $k$ amounts to saying that $p_x$ is asymptotically independent of $x$. If this holds then $S$ has the same asymptotic. Of course $p_x$ is actually a rather erratic function of $x$ in reality, but this is the main idea. Most likely this heuristic as stated is false but one could hope that something similar (for example, a relation involving aggregate statistics like your $S$) might hold.
• Thanks, Ian. Empirically, $p_x$ does seem to clock in very near 0.5 for large $x$, so your conclusion would hold. For example, for $x=10^{200}$ $p_x$ is 0.5032, with a median stopping time of 3275. – Joe Knapp Jul 31 '17 at 15:17
• @JoeKnapp $p_x$ should actually clock in above $0.6$ for any Collatz sequence that reaches the 4,2,1 cycle. – Ian Jul 31 '17 at 15:22
• Lagarias in "The 3x+1" problem notes: "probabilistic models for the $3x+1$ function iteration predict that even and odd iterates will initially occur with equal frequency.." That seems to be borne out by just trying numbers, such as $x^{200}$ above. – Joe Knapp Jul 31 '17 at 15:29
• @JoeKnapp I'm not sure I follow. I'm talking about the usual Collatz iteration: even numbers are divided by $2$, odd numbers are multiplied by $3$ and then $1$ is added. To reach $1$ under this iteration you must necessarily encounter more even iterates than odd iterates because the effect of each division is smaller than the effect of each multiplication. I think you may be referring to some simpler system, such as just measuring the parity of a pure 3x+1 iteration. – Ian Jul 31 '17 at 15:30
• PS One thing though: your heuristic applies to stopping time of a given starting value, but the statistic $S$ as defined above applies to the maximum stopping time observed for all values less than a given value. Maybe the same reasoning applies? There is a big difference in general between $S$ and the median or expected stopping time in a given region. – Joe Knapp Jul 31 '17 at 15:33