38
$\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$

3 Answers 3

33
$\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$
3
  • 2
    $\begingroup$ Nice! I had no idea why the diagonals were there, and it now seems so simple... $\endgroup$ Aug 10, 2017 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, 2017 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$ Aug 10, 2017 at 17:57
10
$\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
  • 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, 2017 at 14:39
1
$\begingroup$

There are two injective functions and one bijective function that map all sequences, without exception - and that explains the lattice pattern:

The injective functions are:

For every $4n+3: f(n+1)\frac{3}{2}-1$

3→5, 7→11, 11→17, 15→23, 19→29, 23→35, 27→41, 31→47

For every $8n+1: f(n−1)\frac{3}{4}+1$

1→1, 9→7, 17→13, 25→19, 33→25, 41→31, 49→37, 57→43

The input numbers are disjoint. But the output numbers of the two injective functions must be convergent with the output numbers of the bijective function (unless a multiple of $3$).

The bijective function is for every $8n+5: f(n−1)\frac{1}{4}$

5→1, 13→3, 21→5, 29→7, 37→9, 45→11, 53→13, 61→15

While it's obvious that if you multiply $4n+1$ by $3n+1$ – that is, $(((n*4)+1)3)+1$ – you add two factors of $2$, it's less than obvious that this is occurring in even-odd sequences, as you do not see the repetition of the first odd $n$ in such related sequences. For example:

31 → 94 → 47

125 → 376 → 188 → 94 → 47

501 → 1504 →752 → 376 → 188 → 94 → 47

Nevertheless, it is true - the convergence occurs on an even number.

If you put these three functions together, they must account for the odd-numbered proper superset of even-odd sequences. That is, all sequences can be projected to converge, using these functions, beginning with the basis case: 1 --> 1, 5 --> 1. It should be possible by induction to show there can be no "infinite" sequence excepting a nontrivial loop - and the logic to support this possibility is scant given the interrelatedness of the aforementioned functions. I don't see an alternative conclusion. Set representation

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .