Collatz lattice

Here's a plot of the Collatz stopping times for $1<x<10^5$:

So there's evidence of a sort of lattice arrangement to the points.

Plotting the same data with a logarithmic $x$ axis:

It would seem that the lattice is linear with $\log{x}$. A pair of example lines are shown in red. Adding parallel lines with equal spacing along the two axes:

That lines up pretty well. There is a varying amount of spread horizontally around the intersections that complicates the picture. Here's a detail:

My question would be very general: what would explain such a pattern?

Solution 1:

Consider a number of the form $8n+3$. Its trajectory goes: $8n+3, 24n+10, 12n+5, 36n+16, 18n+8, 9n+4$. Thus, the stopping time for $9n+4$ is $5$ less than the stopping time for $8n+3$. The number $9n+4$ has approximately the ratio $9/8$ to the number $8n+3$, so its logarithm is greater by approximately $\log 9/8$, and its stopping time is less by $5$. That's the regularity along downward sloping lines that you're seeing.

Additionally, $f^5(8n+1)=9n+2$, and $f^5(8n+6)=9n+8$

Next, consider a number of the form $8n+1$. Its trajectory goes: $8n+1, 24n+4, 12n+2, 6n+1$. The ratio of $8n+1$ to $6n+1$ is about $4/3$. Thus, in those cases, when the logarithm decreases by about $\log 4/3$, the stopping time decreases by $3$. That's the regularity along the lines with positive slope.

Additionally, $f^3(8n+2)=6n+2$, $f^3(8n+4)=6n+4$, $f^3(8n+5)=6n+4$, and $f^3(8n+6)=6n+5$.

Note that two of those are the same: thus, $3$ steps upstream of every $6n+4$, we find an $8n+4$ and an $8n+5$.

These two regularities intermesh because of the Chinese Remainder Theorem. In many cases, one of those $6n+k$ numbers is also an $8n+j$ number, so a step down-and-to-the-left is followed by another step down, to the left and/or to the right.

There are still horizontal runs of points to explain, clustered around intersections in the lattice. First, as noted above, $f^3(8n+4)=f^3(8n+5)=6n+4$. Their trajectories converge after $3$ steps, so they have the same stopping time.

Similarly, $16n+8$ and $16n+10$ have the same stopping time, with $f^4(16n+8)=f^4(16n+10)$.

Exploring trajectories modulo various powers of $2$, you can keep finding patterns like these.

Solution 2:

Part of the explanation is that if you have a pattern (a collection of numbers $a_1, a_2, \ldots, a_n$ that happen to attract your attention visually) at some stopping time, then you have the same pattern at that stopping time +1, but with $2a_1, 2a_2, \ldots, 2a_n$, because each of those numbers "stops" after one more step. Clearly the same kind of thing applies to $2^2$, or $2^3$, etc. Hence at least some of the regularity in the log plot.