How many numbers between 1 and M might a Collatz integer cycle hit?

[mathkook]

If there were an integer Collatz cycle with all members \leq M, how many of the numbers 1..M could it hit? Most of them? Almost all of them? Almost all of them except odds divisible by 3? Almost none of them? Is this another imponderable Collatz question? Almost for sure?

Call c(M) the length of the longest integer cycle with all members under M.

For M=11, we have c(M)=2, because the longest (and only) cycle is 1 \rightarrow 2 \rightarrow 1.

Actually, for any M < 10^{20}, we’ll always get c(M)=2.

For this post’s question to make sense, imagine that we’re talking about galactic-ocean-sized values of M, where the numbers between 1 and 10^{20} form a drop in the bucket.

For such a vast M, can we place an upper-bound on c(M)?

Since Collatz is hard to model, what about relaxing the Collatz rule in some way that might be more tractable?

An example rule T' might be:

• Even n \rightarrow n/2
• Odd n \equiv 3 (mod 4) \rightarrow (3n+1)/2
• Odd n \equiv 1 (mod 4) \rightarrow e

where e is any even number between n and (3n+1)/2. So some numbers have multiple possible successors.

For M=10, the longest integer cycle we can make is 3 \rightarrow 5 \rightarrow 6 \rightarrow 3, meaning we can now hit 3 numbers between 1 and 10, instead of just 2.

For M=18, the longest cycle is 7-11-17-18-9-14-7, so let’s say c'(M)=6.

Since the relaxed rule includes the original Collatz trajectories, c'(M) \geq c(M).

Given the extra freedom of rule T', maybe it’s possible to hit most of the numbers between 1 and M … but who knows. It’s doubtful that T' is more tractable to analyze than the regular Collatz rule, but it does generate data

For small M, here’s what c'(M) looks like:

[oros]

Some trivial (untight) upper bounds:

• c(M) \leq \left( 1 - \frac13 \right) \left( 1 - \frac{1}{6} \right) M + O(1) = \frac{5}{9} M + O(1) by discarding multiples of 3 below M and odd integers in the range \left[\frac23 M , M \right];
• c'(M) \leq \left( 1 - \frac{1}{12} \right) M + O(1) = \frac{11}{12} M + O(1) by discarding integers of the form 3+4k in the range \left[\frac23 M , M \right].

[mathkook]

Yup! Running c’(M) out to very high M might be revealing. Finding the longest cycle in a general directed graph is computationally hard, don’t know about this special case.

[oros]

This looks like a game…

Some puzzling questions:

• Is it always possible to build a divergent T'-sequence when starting from any odd number above a given threshold? If yes, find the smallest threshold.
• Is there a lower bound of the form c'(n) \geq a\,n with a>0.

It reminds of a two-player game which combines Collatz with its 3n-1 variant, named 3n\pm1 game. And there is prize to win
Collatz Prizes offered by Ingo Althofer

[mathkook]

Here’s c'(M) for higher M … not very conclusive … guessing that in general, at least 1/3 of numbers less than M can be hit by a T' cycle, probably a lot more

[oros]

To quickly improve the upper bound of c(M), observe that the number x of odd terms is close to k/\rho where k is the length and \rho = \log_2 3.

As previously, I discard the multiples of 3 and the odd numbers above 2*M/3, so that x \leq (1−\frac13)(1−\frac13)\frac{M}{2}+O(1).

We obtain c(M) \lesssim \frac{\rho}{2}(1−\frac13)(1−\frac13)M = \frac{2\rho}{9}M \simeq 0.35 \times M.

More rigorously, we have k \leq x \log_2 (3+m^{-1}) where m is the smallest term (cf. Eliahou’s paper). We can safely assume that m > 10^3 (for a nontrivial cycle), which gives
c(M) \leq \frac{2\log (3+10^{-3})}{9 \log 2}M + O(1) < 0.353 \times M + O(1).

Moreover, the constant O(1) can also be removed when M>2 as it is much smaller than m.

If we apply the same reasoning to the 3x-1 variant, the coefficient 0.35 is not far from the density 3/10 associated to the cycle (5,7,10).

[mathkook]

Already a tighter bound than might be expected from T'

That’s true, 3n-1 also provides “data” … the c^{3n-1}(M) graph would go up to 3 at M=10, then up to 11 at M=136.

[oros]

A similar reasoning can be applied to T':

Since T'(n) \leq (3n+1)/2 for any odd n, the proportion of odd terms x/k has to be even larger than for T-cycles and the upper bound k \leq x \log_2 (3+m^{-1}) also holds.

As previously shown, we have x \leq (1−\frac16)\frac{M}{2} + O(1).

It follows that c'(M) \leq \frac56 M + O(1) from the obvious inequality \log_2 (3+m^{-1}) \leq 2.

In fact, Eliahou proved the stronger constraint k \leq x\log_2 (3+h^{-1}) where h is the harmonic mean of the odd terms, which also holds for T'. Since h is lower bounded by the harmonic mean of \{ 1,3,5,\ldots,2x-1\}, it is not difficult to show that h \geq \frac{ax}{\log x} with a>0. As a consequence:
k \leq \rho x +\frac{1}{3a\log2} \cdot \log x
with \rho = \log_2 3.

As x \rightarrow +\infty, we find that c'(M) \leq \frac{5\rho}{12} M + o(M)
with \frac{5\rho}{12} \simeq 0.66.

But in practice, the ratio x/k is probably larger than 1/\rho, so that c'(M) is even smaller than 0.66\times M. Hopefully, @mathkook can confirm this…

[mathkook]

M=161

c’(M)= 45

cycle=[15, 23, 35, 53, 78, 39, 59, 89, 134, 67, 101, 146, 73, 110, 55, 83, 125, 150, 75, 113, 138, 69, 102, 51, 77, 114, 57, 86, 43, 65, 98, 49, 74, 37, 54, 27, 41, 50, 25, 38, 19, 29, 42, 21, 30, 15]

that one has about 64% odds

and c'(M) \approx 0.28\,M

[oros]

Thanks , so the ratio is tight for this one!

And this confirms also that no large T'-cycles can descend below 15, since 15 is the smallest integer from which a divergent sequence can start. And some of the odd integers above 15 are also forbidden for the same reason, which implies that the upper bound of c'(M) cannot be reached.