34
$\begingroup$

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

enter image description here

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

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

enter image description here

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:

enter image description here

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

enter image description here

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

$\endgroup$
30
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Nice! I had no idea why the diagonals were there, and it now seems so simple... $\endgroup$ – John Hughes Aug 10 '17 at 14:57
  • 1
    $\begingroup$ Very comprehensive--thanks! One more observation to explain: along the lines sloping up to the right, the number of points at each intersection increases with $x$ (except for perhaps a few cases at low $x$). I suppose that makes sense that more neighboring trajectories would converge with the same length as $x$ goes up? $\endgroup$ – Joe Knapp Aug 10 '17 at 15:15
  • 1
    $\begingroup$ I've added some more detail, including an explanation of the increasing dots as you move northeast. Every $6n+4$ has two neighbors to the immediate northeast. $\endgroup$ – G Tony Jacobs Aug 10 '17 at 17:57
9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ FWIW, the stopping time increases 3 each step along the lines sloping up to the right, and decreases 5 each step along the lines sloping down to the right. The step sizes are unvarying. $\endgroup$ – Joe Knapp Aug 10 '17 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.