0
$\begingroup$

I assume knowledge of the Collatz conjecture. Here I'm looking only at total stopping times $t(n)$, and mostly will drop the word "total."

Just looking at relatively simple graphs of stopping times on Wikipedia shows many patterns in stopping times, sets of overlapping discontinuous "curves". In addition, if one zooms in closely, one finds pairs, triplets, or longer sequences of integers all with the same stopping time. This paper shows every pair of consecutive integers $(n, n+1) \equiv (4,5) \pmod 8$ have equal values of $t(n)$, other than the pair $(4,5)$.

But this clustering extends over larger swaths of integers. Consider the integers in $[1000000,1100000]$. These $10^5$ integers have among them a total of just $69$ different stopping times, ranging from $20$ to $501$. Among those times, just $8$ of them account for over $50\%$ of the integers: $t = (72, 90, 103, 121, 134, 152, 165, 196)$. By contrast, $16$ of those $t$ values occur $10$ or fewer times, accounting for just $71$ of the integers in this range.

Within the range of values of $t$ taken, just $14\%$ are found, and just $1.66\%$ account for more than half the integers in the range. And as one looks at the same range sizes in larger integers, the clustering becomes more pronounced:

$$\begin{array}{c|c|c|c|c} \text{Range Start} & \text{Range of } t(n) & t \text{ values} & t \text{ values for 50%} \\ \hline 10^5 & [17, 382] & 167 & \sim40 \\ \hline 10^6 & [20, 501] & 69 & 8 \\ \hline 10^7 & [39, 618] & 48 & 5 \\ \hline 10^8 & [50, 686] & 40 & 4 \\ \hline 10^9 & [48, 803] & 34 & 4 \\ \end{array}$$

Now, obviously we shouldn't expect homogeneity of any sort. But this sort of clustering seems to be out of the realm of what we might expect. Over $20 \%$ of the integers $10^7 \leq n \leq 10^7 + 10^5$ all have the same total stopping time: $114$. They're not sequential, but that's a crazy statistic.

Does anyone know of an explanation--heuristic or otherwise--for this heavy clustering of the total stopping times?


The image below is a histogram of $t(n)$ values for $1000000 \leq n \leq 1100000$

$\endgroup$
5
  • $\begingroup$ math.stackexchange.com/questions/470782/… $\endgroup$
    – Collag3n
    Apr 1, 2022 at 4:54
  • $\begingroup$ @Collag3n Interesting, but that's looking specifically at long spans with the same $t(n)$. What's I'm wondering about is the continued clustering of lengths without respect to how the range of $n$ is divided. For instance, at $n = 10^6$, you have two runs of $6$ integers with $t(n) = 113$. But then as you go farther out, runs of $113$ keep popping up, interspersed with runs of $90, 139$, and others. Why does $113$ show up a ton, but never $112$? (Edit/side note: $112$ does appear for lower $n$. Perhaps finding the range of $n$ across which a given $t(n)$ is found is interesting?) $\endgroup$ Apr 1, 2022 at 6:27
  • 1
    $\begingroup$ Oops! That is of course the single pair that does not have this property. Specifically, all pairs $(8k+4, 8k+5), k \geq 1$ have the same total stopping time. I'll edit to correct that. $\endgroup$ Apr 1, 2022 at 11:24
  • $\begingroup$ @EricSnyder How did you manage to check the range upto $10^9$ ? Do you have a trick to accelerate the determination of the stopping times ? Brute force would take forever on my computer. $\endgroup$
    – Peter
    Apr 1, 2022 at 11:37
  • $\begingroup$ @Peter No, just typical brute force. I wasn't looking at entire ranges from $10^9$ to $10^10$, though--just up to $10^9 + 10^5$. Sagemath/Python took a bit under 90 seconds to process them. Consider that stopping times don't increase a ton with increasing $n$, and those stopping times are equivalent-ish to the number of integer ops needed to find the stopping time for each $n$. $\endgroup$ Apr 2, 2022 at 4:32

2 Answers 2

2
$\begingroup$

All right, I have found at least a partial answer. Specifically, a heuristic explanation for the clustering. It comes from looking at the pattern of curves in the plots you can see on Wikipedia, and thinking, "Wait, those curves look kinda logarithmic, don't they?" Here's a plot of $t(n)$ against $n$, on a log scale, for $1 < n \leq 10^6$:

enter image description here

Look at that pretty grid! And as a bonus, it's Fibonacci-based. The shallowest upward "lines" are increases of the stopping time by $3$; the most obvious downward lines are decreases by $5$; and you can further draw lines differing by $8$ and $13$.

What, then, is the heuristic argument? Well, let's imagine, for a moment, that this grid were composed of a single point at each node. As $n$ gets larger, a single point "covers" more and more integers. A single pixel near the left--say, the one at $(27, 111)$, has a "width" of one integer. OTOH, if we pick a single pixel somewhere on the right--one of the many points in the general range of $(10^5, 200)$--has a "width" of around $3000$ integers. Which of those integers would the line actually cross? Well, perhaps all or most of them!

Hence, we expect larger and larger clusters as $n$ increases, because of the empirical patterns we can see in the plot above. And every value of $t(n)$ will repeat periodically (on a log scale), until $n > 2^{t(n)}$ (after which that value can no longer be a stopping time).

$\endgroup$
0
$\begingroup$

There is a bijection $8n+5 \rightarrow 2n-1$ using the operation $(n-1) \frac {1}{4}$.

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

It’s a one-to-one mapping.

Consider $3x+1$ sequences at intervals of $4n+1$. Each time you multiply $4n+1$ by $3n+1$, $(((n*4)+1)3)+1$, you add two factors of $2$ – and remove the original $n$.

The $(n-1) \frac {1}{4}$ property/operation is not immediately obvious since $n$ is absent from the next greater sequence in the series. Each greater sequence in the series has two additional even steps.

For example:

31 → 94 → 47

125376 → 188 → 94 → 47

5011504 → 752 → 376 → 188 → 94 → 47

20056016 → 3008 → 1504 → 752 → 376 → 188 → 94 → 47

You can see the convergence always begins with $(((n*4)+1)3)+1$ - so that $94$, $376$, $1504$, $6016$) are divisible by $2$ to the same odd number $47$.

(Note why the relatedness of the sequences is obscured: Sequence $125$ does not have the step $31$. Sequence $501$ does not have the steps $125$ or $31$. Sequence $2005$ does not have the steps $501$, $125$, or $31$.)

The property can be generalized as an nth-term formula.

$a{_n} = \frac {(4^n - 1)}{3} + (4 ^ n * S)$

such that $S$ is an odd sequence's first number.

$\endgroup$
2
  • $\begingroup$ Interesting, but I'm uncertain how this affects or describes clustering of stopping times. $\endgroup$ Apr 11, 2022 at 5:54
  • $\begingroup$ @EricSnyder Thanks. I'm thinking about stopping times incrementing by 2 even steps with each multiplication by 4n+1 as a cluster or set of like sequences. The smallest sequence in the set must be $n-1 \not\equiv 0 \mbox{ (mod } 4)$. The "base case" is 1, 5, 21, 85, 341. There is another progression beginning 3, 13, 53, and another beginning 7, 29, 117. (Since the sets accumulate and overlap, the clustering is not evident without sorting.) $\endgroup$ Apr 12, 2022 at 3:13

You must log in to answer this question.

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