There are no Collatz m-Cycles with m ≤ 91

Christian Hercher Abteilung für Mathematik und ihre Didaktik Europa-Universität Flensburg Auf dem Campius 1b 24944 Flensburg Germany

           christian.hercher@uni-flensburg.de

Abstract

The Collatz conjecture (or “Syracuse problem”) considers recursively-defined sequences of positive integers where n is succeeded by \frac{n}{2}, if n is even, or \frac{3n+1}{2}, if n is odd. The conjecture states that for all starting values n the sequence eventually reaches the trivial cycle 1, 2, 1, 2, …. We are interested in the existence of nontrivial cycles.

Let m be the number of local minima in such a nontrivial cycle. Simons and de Weger proved that m ≥ 76. With newer bounds on the range of starting values for which the Collatz conjecture has been checked, one gets m ≥ 83. In this paper, we prove m ≥ 92.

The last part of this paper considers what must be proven in order to raise the number of odd members a nontrivial cycle has to have to the next bound—that is, to at least K ≥ 1.375 · 10^{11}. We prove that it suffices to show that, for every integer smaller than or equal to 1536 · 2^{60} = 3 · 2^{69}, the respective Collatz sequence enters the trivial cycle. This reduces the range of numbers to be checked by nearly 60%.

1 Introduction

The Collatz conjecture^{1} (or Syracuse problem) considers recursively-defined sequences of positive integers.

1Named after German mathematician Lothar Collatz, 1910–1990.

Definition 1. Let n be a positive integer. The Collatz operator C : ℤ_{>0} → ℤ_{>0} is defined as follows:

C(n) := \begin{cases}\frac{n}{2}, & if n is even; \\ \frac{3n+1}{2}, & if n is odd. \end{cases}

We define an e-step to be of type n ↦ \frac{n}{2}, since it occurs after an even number n, and an o-step to be of type n ↦ \frac{3n+1}{2}, since it follows after an odd number n.

Conjecture 2 (Collatz). For all n ∈ ℤ_{>0}, the sequence n, C(n), C^{2}(n) := C(C(n)), C^{3}(n), … eventually reaches the trivial cycle 1, 2, 1, 2, ….

Remark 3. While the Collatz conjecture is currently unproven, there are good reasons to believe it holds. In [14], for example, Terras showed that the respective Collatz sequence enters the trivial cycle for almost all integers. More recently, Tao also proved in [13] that, for every function f : ℤ_{>0} → ℝ with lim_{n→∞} f(n) = ∞ and almost every positive integer n, the Collatz sequence starting with n reaches a number less than or equal to f(n):

lim inf_{k→∞} C^{k}(n) ≤ f(n).

Nevertheless, the conjecture could be wrong in two possible ways:

• There could be an unbounded sequence n, C(n), … with lim sup_{i→∞} C^{i}(n) = ∞.

• There could be a nontrivial cycle n, C(n), … with C^{i}(n) = n for some positive integer i.

This paper concerns itself with the second case. Specifically, we consider the properties a nontrivial cycle would need to have.

Over time, different projects, [6, 10, 7, 8, 4, 5, 1], have taken various approaches to prove or disprove the Collatz conjecture by checking whether the respective sequences of increasing numbers converge to the trivial cycle. The best known bound is from Barina [2]:

Definition 4. We define X_{0} as the largest number for which it is known that for all positive integers n ≤ X_{0} their Collatz sequences reach the trivial cycle. As of the date of writing this paper, we have

X_{0} = 695 · 2^{60}.

Since the Collatz sequences converge to the trivial cycle for all numbers less than or equal to X_{0}, we can derive estimates of properties of hypothetically existing nontrivial cycles. On the basis of the value of X_{0} known at the time, Eliahou [3] used methods derived from diophantine approximation and continued fractions to prove that such a nontrivial cycle must include at least K > 10^{7} o-steps. This bound was subsequently improved by Hercher and Puchert [4, 5, 9] to the current K > 7.2 · 10^{10} .

Another property of such a nontrivial cycle was investigated by Simons and de Weger [11]. As \frac{3n+1}{2} > n > \frac{n}{2}, such a nontrivial cycle has strictly increasing and strictly decreasing passages:

Definition 5. Let n, C(n), …, C^{i}(n) = n be a nontrivial cycle. (That is, n > 2.) Let us call it an m-cycle if it has exactly m local minima (and therefore also exactly m local maxima).

Simons and de Weger [11] proved that m ≥ 68 for every nontrivial cycle. Based on the rate of growth of X_{0} in the year 2005, when [11] appeared, they estimated that bounds on m like m ≥ 77 were unlikely to be obtained before the year 2419. In an updated version of the paper [12] in 2010, the same authors used what was then a new bound X_{0} to prove that m ≥ 76. Regarding future bounds, estimates suggested that m ≥ 83 could not be reached before the year 2429 if progress on X_{0} maintained the then-current pace and no new insights into the topic emerged. In 2018, Hercher [4, 5]—using his newly derived bound on X_{0}—proved that m ≥ 77.

With the current best bound on X_{0}, Simons and de Weger [11, 12] suggested that with methods of their paper m ≥ 83 could be proven.^{2} In this paper, we prove that m ≥ 92.

1.1 Outline

In Section 2, we consider sums of the form T (n_{i}) = ∑_{k=0}^{k_{i}} \frac{1}{C^{k}(n_{i})}. This is the sum of the reciprocals of the odd numbers starting with and following a local minimum n_{i} in an mcycle. In Remark 7, Lemma 11, and Corollary 13, we give subsequently improving upper bounds on the average of these T (n_{i}) in sets of up to three consecutive such terms. This leads to Lemma 12 and Theorem 14, where we give bounds on sums of an arbitrary number of consecutive T (n_{i}).

This is motivated and used in Section 3. At the start of this section, some results on nontrivial cycles in Collatz sequences are listed and proved in a way similar to that in [3, 11, 4]. In particular, Theorem 16 gives bounds on the fraction \frac{K+L}{K} in terms of ∑_{i=1}^{m} T (n_{i}). Here, K is the number of odd and L the number of even entries in the cycle and therefore the number of o-steps and e-steps, respectively. Together with the bounds on such sums over T (n_{i}) and further refinements, this leads to better bounds on \frac{K+L}{K}. These bounds are given in Corollary 17 and Theorem 21. (Corollary 19 is a version of Corollary 17 which gives an absolute bound independently of X_{0}, where we used a computer program to derive it.)

The proof of Theorem 21 is based on the idea that k_{i} cannot grow at an unlimited rate: There is a constant 1 < δ < 2 such that k_{i+j} ≤ δ^{j} · \frac{log(n_{i}+1)}{log(2)} for all i, j; see Lemma 20. Then we split the sum ∑_{i=1}^{m} T (n_{i}) into two parts. The first one, with “small” n_{i}, is bounded using Theorem 14 from Section 2, and the second one with “large” and “growing” k_{i} (and therefore “large” n_{i}, too). The second partial sum is estimated in the proof of Theorem 21 itself.

The results for the bounds on \frac{K+L}{K} can then be used together with Lemma 22. This lemma states how to obtain the smallest possible denominator of all fractions in a given nonempty open interval. We use this lemma in our main theorem, Theorem 23, to show that there is no m-cycle with m ≤ 91. To do so, we assume m ≤ 91 and give a new lower bound on K, which then can be used in the same way to get an even better lower bound, and so on.

2Private e-mail conversation in September 2021.

Finally, we arrive at a proven lower bound on K which is larger than the upper bound for this value of m given by Simons and de Weger [12]. This result shows that no such m-cycle with m ≤ 91 can exist.

In the same way, we can give new lower bounds on K for m-cycles with m ≥ 92. A selection of them is given in Corollary 24. The computations for Theorem 23 and Corollary 24 were done using a Sagemath worksheet, with the total computing time lasting a few minutes.

Finally, in Section 4 the methods of the previous sections are used to consider the case of nontrivial Collatz cycles independent of m. The result on the average value of the T (n_{i}) yielded Lemma 26 is analogous to the ones given by Lemma 11 and Corollary 13. However there the values T (n_{i}) are weighted by the numbers k_{i}. This is used to get Theorem 27, which yields a result analogous to that of Corollary 17, but independent of m. As stated in Remark 28, this lowers the value X_{0} has to have for proving K > 1.375·10^{11} (which is the next threshold reachable) from 3781·2^{60} to 2836·2^{60}. To get this result with an even smaller known value of X_{0}, we implemented the methods in a computer program which—after extensive computations—proved Corollary 29, which states that already X_{0} ≥ 1536 · 2^{60} = 3 · 2^{69} is sufficient.

2 Upper bounds on T (n_{i})

Definition 6. For a given m-cycle, we call the local minima in order of appearance in the cycle n_{1}, n_{2}, …, n_{m}. To keep the notation simple, we further set n_{m+1} := n_{1}, n_{m+2} := n_{2} and so on. Note that we do not need n_{1} to be the smallest of these minima, as every cyclic permutation of these minima yields to the same results. All we need is that, for all i, the next local minimum after n_{i} in this Collatz trajectory is n_{i+1}.

Further let k_{i} be the exact number of consecutive o-steps directly following the local minimum n_{i}, and let ℓ_{i} be the exact number of e-steps directly following them. Thus, the numbers n_{i}, C(n_{i}), …, and C^{k_{i}−1}(n_{i}) are all odd (as they are followed by an o-step) and C^{k_{i}}(n_{i}) is even. Therefore, C^{k_{i}}(n_{i}) is the local maximum following n_{i}. From that point on, the numbers C^{k_{i}}(n_{i}), C^{k_{i}+1}(n_{i}), … and C^{k_{i}+ℓ_{i}−1}(n_{i}) are all even (since they are followed by an e-step) and C^{k_{i}+ℓ_{i}}(n_{i}) is odd. Therefore, C^{k_{i}+ℓ_{i}}(n_{i}) = n_{i+1} is the next local minimum after n_{i}.

For positive integers i, let

T (n_{i}) := ∑_{t=0}^{k_{i}−1} \frac{1}{C^{t}(n_{i})}.

Remark 7. We have T (n_{i}) < \frac{3}{n_{i}} < \frac{3}{X_{0}} for all 1 ≤ i.

Proof. As C(n) > \frac{3}{2}n for odd n, we have C^{t}(n_{i}) ≥ (\frac{3}{2})^{t} · n_{i}, and therefore

T (n_{i}) = ∑_{t=0}^{k_{i}−1} \frac{1}{C^{t}(n_{i})} < ∑_{t=0}^{∞} \frac{1}{n_{i} · (\frac{3}{2})^{t}} = \frac{1}{n_{i}} · ∑_{t=0}^{∞} (\frac{2}{3})^{t} = \frac{3}{n_{i}} < \frac{3}{X_{0}} .

The last inequality follows from n_{i} > X_{0}.

Lemma 8. Let n and k be positive integers, where n, C(n), …, C^{k−1}(n) are all odd. Then n ≡ −1 (mod 2^{k}). In particular, n ≥ 2^{k} − 1.

Proof. We proceed by induction on k to show that not only n ≡ −1 (mod 2^{k}), but also C^{k}(n) = a · 3^{k} − 1, if n = a · 2^{k} − 1. If k = 1, then the statement is obvious: We have n = a · 2^{1} − 1 for some positive integer a and C^{1}(n) = a · 3^{1} − 1.

Now let k be at least 2 and n, C(n), …, C^{k−2}(n) all odd. Then there is a positive integer a with n = a · 2^{k−1} − 1 and C^{k−1}(n) = a · 3^{k−1} − 1. Since in order for C^{k−1}(n) to be odd, a must be even, a = 2a′, n = a′ · 2^{k} − 1 and C^{k}(n) = a′ · 3^{k} − 1. Thus, n ≡ −1 (mod 2^{k}) and n ≥ 2^{k} − 1.

Note that this well-known statement has been used before and proven in many publications on this subject, e.g., [14].

Lemma 9. Let n_{i} be an odd positive integer. Let k_{i} be the exact number of o-steps directly following n_{i} in its Collatz sequence and ℓ_{i} the exact number of e-steps following them.

If ℓ_{i} ≥ 2, then the Collatz sequences of n_{i} and n′_{i} := \frac{n_{i}−1}{2} merge since C^{k_{i}+2}(n_{i}) = C^{k_{i}+1}(n′_{i}).

Proof. Let n_{i}, k_{i} and ℓ_{i} be as in the lemma. Then, there is a positive integer a with n_{i} = a · 2^{k_{i}+2} + 2^{k_{i}} − 1 if k_{i} is even, or n_{i} = a · 2^{k_{i}+2} + 3 · 2^{k_{i}} − 1 if k_{i} is odd. To see this, we recall with Lemma 8 that n_{i} is congruent to −1 modulo 2^{k_{i}}, but not modulo 2^{k_{i}+1}. Therefore, there is a positive integer b with n_{i} = b · 2^{k_{i}+1} + 2^{k_{i}} − 1. With this, according to the proof of Lemma 8 we get

C^{k_{i}+1}(n_{i}) = b · 3^{k_{i}} + \frac{3^{k_{i}} − 1}{2} = \frac{(2b + 1) · 3^{k_{i}} − 1}{2}.

Since we want another e-step to follow this number, it has to be even. Hence, we get (2b + 1) · 3^{k_{i}} ≡ 1 (mod 4). For even k_{i} we have 3^{k_{i}} ≡ 1 (mod 4), thus, b = 2a has to be even. For odd k_{i} we have 3^{k_{i}} ≡ 3 (mod 4), such that b = 2a + 1 has to be odd.

If k_{i} is even, this leads to the equality C^{k_{i}+2}(n_{i}) = a·3^{k_{i}} + \frac{3^{k_{i}}−1}{4}. But this number is also a Collatz successor of the number n′_{i} := \frac{n_{i}−1}{2} = a·2^{k_{i}+1} +2^{k_{i}−1} −1, since through n′_{i} ≡ 2^{k_{i}−1} −1 (mod 2^{k_{i}}) we get C^{k_{i}}(n′_{i}) = a · 2 · 3^{k_{i}−1} + \frac{3^{k_{i}−1}−1}{2}. But when k_{i} is even we know that \frac{3^{k_{i}−1}−1}{2} is odd and that, therefore, C^{k_{i}}(n′_{i}) is odd, too. As a result, we get

C^{k_{i}+1}(n′_{i}) = a · 3^{k_{i}} + \frac{3^{k_{i}} − 1}{4} = C^{k_{i}+2}(n_{i}).

Similarly, for odd k_{i} we get

C^{k_{i}+1}(n_{i}) = \frac{(2(2a + 1) + 1) · 3^{k_{i}} − 1}{2} = \frac{4a · 3^{k_{i}} + 3 · 3^{k_{i}} − 1}{2}

= 2a · 3^{k_{i}} + \frac{3^{k_{i}+1} − 1}{2}

and therefore C^{k_{i}+2}(n_{i}) = a · 3^{k_{i}} + \frac{3^{k_{i}+1}−1}{4}. Now this is C^{k_{i}+1}(n′_{i}) with n′_{i} = \frac{n_{i}−1}{2} = a · 2^{k_{i}+1} + 3 · 2^{k_{i}−1} − 1, too: By n′_{i} ≡ 2^{k_{i}−1} − 1 (mod 2^{k_{i}}), we know C^{k_{i}}(n′_{i}) = a · 2 · 3^{k_{i}−1} + \frac{3^{k_{i}−1}−1}{2}. As k_{i} is odd, C^{k_{i}}(n′_{i}) is odd, too, and we get

C^{k_{i}+1}(n′_{i}) = a · 3^{k_{i}} + \frac{3^{k_{i}} − 1}{4} = C^{k_{i}+2}(n_{i}).

Remark 10. From this lemma we also get a small result for unbounded Collatz sequences:

Let n_{1} be the smallest positive integer, if any, for which the Collatz sequence is unbounded. Let k_{1} and ℓ_{1} be as above. Then ℓ_{1} = 1 and k_{1} ≥ 2. (If ℓ_{1} were greater, then there would be a smaller number n′_{1} which would also have an unbounded Collatz sequence, and this would contradict the minimality of n_{1}. The same would hold, if k_{1} = ℓ_{1} = 1, since in that case we would have C^{2}(n_{1}) = \frac{3n_{1}+1}{4} < n_{1}, which also has an unbounded sequence.)

Lemma 11. For all 1 ≤ i, we have

T (n_{i}) < \frac{35}{18} · \frac{1}{X_{0}} or
T (n_{i}) + T (n_{i+1}) < 2 · \frac{35}{18} · \frac{1}{X_{0}} .

Proof. Let k_{i} be as in Definition 6. For k_{i} ≤ 2 we have

T (n_{i}) < \frac{1}{n_{i}} · (1 + \frac{2}{3}) = \frac{5}{3} · \frac{1}{n_{i}} < \frac{35}{18} · \frac{1}{n_{i}} < \frac{35}{18} · \frac{1}{X_{0}} .

Now let k_{i} ≥ 3. Then

T (n_{i}) = ∑_{t=0}^{k_{i}−1} \frac{1}{C^{t}(n_{i})} < ∑_{t=0}^{k_{i}−1} \frac{1}{n_{i} · (\frac{3}{2})^{t}}

= \frac{1}{n_{i}} · \frac{1 − (\frac{2}{3})^{k_{i}}}{1 − \frac{2}{3}}

= \frac{1}{n_{i}} · (3 − 3 · (\frac{2}{3})^{k_{i}})

and C^{k_{i}}(n_{i}) > (\frac{3}{2})^{k_{i}} · n_{i}. As an e-step follows, we get

C^{k_{i}+1}(n_{i}) > \frac{1}{2} · (\frac{3}{2})^{k_{i}} · n_{i}.

If C^{k_{i}+1}(n_{i}) is already the next local minimum, that is n_{i+1} = C^{k_{i}+1}(n_{i}), we get

T (n_{i+1}) < \frac{3}{n_{i+1}} < 6 · (\frac{2}{3})^{k_{i}} · \frac{1}{n_{i}} ,

T (n_{i}) + T (n_{i+1}) < \frac{1}{n_{i}} · (3 − 3 · (\frac{2}{3})^{k_{i}} + 6 · (\frac{2}{3})^{k_{i}})

= \frac{1}{n_{i}} · (3 + 3 · (\frac{2}{3})^{k_{i}})

≤ \frac{1}{n_{i}} · \frac{35}{9} < 2 · \frac{35}{18} · \frac{1}{X_{0}} .

The second-to-last inequality follows from (\frac{2}{3})^{k_{i}} ≤ \frac{8}{27} for k_{i} ≥ 3.

Finally, we must consider the case when there are at least two e-steps after the k_{i} o-steps following n_{i}. Then from Lemma 9 we know that there exists an integer n′_{i} = \frac{n_{i}−1}{2} for which the Collatz sequence merges with that of n_{i}, and thus with the considered cycle.

But n′_{i} > X_{0} since for every positive integer less than or equal to X_{0} the Collatz sequence enters the trivial cycle. Hence, we have n_{i} > 2·n′_{i} > 2X_{0} and thus T (n_{i}) < \frac{3}{n_{i}} < \frac{3}{2}·\frac{1}{X_{0}} < \frac{35}{18}·\frac{1}{X_{0}} , which concludes the proof.

Lemma 12. Let 0 ≤ m_{1} be an integer. Then

∑_{i=1}^{m_{1}} T (n_{i}) < \frac{35m_{1} + 19}{18} · \frac{1}{X_{0}} .

Proof. We split the sum into single summands or sums of two consecutive summands, to each of which we apply the previous lemma. From Lemma 11, we know that T (n_{1}) < \frac{35}{18} · \frac{1}{X_{0}} or T (n_{1}) + T (n_{2}) < 2 · \frac{35}{18} · \frac{1}{X_{0}} . In the first case, our first part consists solely of T (n_{1}). In the second case, it is the partial sum T (n_{1}) + T (n_{2}). The second partial sum is defined in a similar way, and so on. We say such a partial sum is complete if from Lemma 11 we know that it is smaller than \frac{35}{18} · \frac{1}{X_{0}} for one summand or 2 · \frac{35}{18} · \frac{1}{X_{0}} for two summands. Since all such partial sums until the one with T (n_{m_{1}−1}) are complete, they therefore have an average value of less than \frac{35}{18} · \frac{1}{X_{0}} per summand. Thus, if T (n_{m_{1}}) is in a complete partial sum we get ∑_{i=1}^{m_{1}} T (n_{i}) < \frac{35}{18} · m_{1} · \frac{1}{X_{0}} , and if T (n_{m_{1}}) is not part of a complete partial sum, it cannot be in a partial sum together with T (n_{m_{1}−1}). Thus, we have

∑_{i=1}^{m_{1}} T (n_{i}) = T (n_{m_{1}}) + ∑_{i=1}^{m_{1}−1} T (n_{i}) < T (n_{m_{1}}) + (m_{1} − 1) · \frac{35}{18} · \frac{1}{X_{0}}

< \frac{3}{X_{0}} + (m_{1} − 1) · \frac{35}{18} · \frac{1}{X_{0}} = \frac{35m_{1} + 19}{18} · \frac{1}{X_{0}} ,

where we used the trivial bound T (n_{m_{1}}) < \frac{3}{X_{0}} from Remark 7.

Note that this bound holds for all sums with m_{1} consecutive local minima.

A more detailed analysis in the proof of Lemma 11 yields a slightly better result:

Corollary 13. For all 1 ≤ i ≤ m we have

T (n_{i}) < \frac{97}{54} · \frac{1}{X_{0}} ,
T (n_{i}) + T (n_{i+1}) < 2 · \frac{97}{54} · \frac{1}{X_{0}} ,
or T (n_{i}) + T (n_{i+1}) + T (n_{i+2}) < 3 · \frac{97}{54} · \frac{1}{X_{0}} .

Proof. As in the proof of Lemma 11 let k_{i} be the exact number of consecutive o-steps after n_{i}, and let ℓ_{i} be the exact number of consecutive e-steps thereafter. Then we have C^{k_{i}+ℓ_{i}}(n_{i}) = n_{i+1}.

In the case of k_{i} ≤ 2, we get T (n_{i}) < \frac{5}{3} · \frac{1}{n_{i}} < \frac{97}{54} · \frac{1}{X_{0}} , as with the proof of Lemma 11. Similarly, in the case that ℓ_{i} ≥ 2, we get T (n_{i}) < \frac{3}{2} · \frac{1}{X_{0}} < \frac{97}{54} · \frac{1}{X_{0}} . If ℓ_{i} = 1 and k_{i} ≥ 4, we have

T (n_{i}) + T (n_{i+1}) < \frac{1}{n_{i}} · (3 + 3 · (\frac{2}{3})^{k_{i}}) ≤ \frac{1}{n_{i}} · \frac{97}{27} < 2 · \frac{97}{54} · \frac{1}{X_{0}} ,

where the second-to-last inequality follows from 3 + 3 · (\frac{2}{3})^{k_{i}} ≤ 3 + 3 · \frac{16}{81} = \frac{97}{27} as k_{i} ≥ 4.

Thus, the only case that requires closer analysis is k_{i} = 3 and ℓ_{i} = 1. Then there exists a nonnegative integer a with n_{i} = a · 16 + 7 and n_{i+1} = 27 · a + 13. If ℓ_{i+1} ≥ 2, then—as in the proof of Lemma 11—there exists a nonnegative integer n′_{i+1} = \frac{n_{i+1}−1}{2} for which the Collatz sequence merges with the one of n_{i+1} and therefore with the considered m-cycle. Thus, we have n′_{i+1} ≥ X_{0} + 1 and subsequently a ≥ \frac{2X_{0}−10}{27} and n_{i} ≥ \frac{32X_{0}−160+189}{27} > \frac{32}{27} · X_{0}. That leads to the following bounds:

T (n_{i}) < \frac{1}{n_{i}} · (1 + \frac{2}{3} + \frac{4}{9}) = \frac{1}{n_{i}} · \frac{19}{9}

< \frac{1}{\frac{32}{27} · X_{0}} · \frac{19}{9} = \frac{57}{32} · \frac{1}{X_{0}} < \frac{97}{54} · \frac{1}{X_{0}} .

Hence, the only remaining case is k_{i} = 3 and ℓ_{i} = ℓ_{i+1} = 1. As k_{i} = 3 and ℓ_{i} = 1, we know that T (n_{i}) < \frac{19}{9} · \frac{1}{n_{i}} and n_{i+1} > \frac{27}{16} · n_{i} and that therefore \frac{1}{n_{i+1}} < \frac{16}{27} · \frac{1}{n_{i}}.

If k_{i+1} ≤ 2 we have

T (n_{i+1}) < \frac{5}{3} · \frac{1}{n_{i+1}} < \frac{80}{81} · \frac{1}{n_{i}} < \frac{1}{n_{i}} ,
T (n_{i}) + T (n_{i+1}) < \frac{28}{9} · \frac{1}{n_{i}} < 2 · \frac{97}{54} · \frac{1}{X_{0}} .

If k_{i+1} ≥ 3, from the proof of Lemma 11 we know

T (n_{i+1}) + T (n_{i+2}) < \frac{1}{n_{i+1}} · \frac{35}{9} < \frac{35}{9} · \frac{16}{27} · \frac{1}{n_{i}}

= \frac{560}{243} · \frac{1}{n_{i}} ,

T (n_{i}) + T (n_{i+1}) + T (n_{i+2}) < (\frac{19}{9} + \frac{560}{243}) · \frac{1}{n_{i}} = \frac{1073}{243} · \frac{1}{n_{i}}

< 3 · \frac{97}{54} · \frac{1}{X_{0}} .

With this, we also get a similar but slightly better result than with Lemma 12:

Theorem 14. Let 0 ≤ m_{1} be an integer. Then

∑_{i=1}^{m_{1}} T (n_{i}) < \frac{97m_{1} + 73}{54} · \frac{1}{X_{0}} .

Proof. As in the proof of Lemma 12, we break the sum into parts of length one, two, or three consecutive summands in the sense from Corollary 13. With exception of the last one (in some cases), all of these partial sums are complete. So we know that these partial sums are smaller than \frac{97}{54} · \frac{1}{X_{0}} times the number of their respective summands.

If T (n_{m_{1}}) is part of such a complete partial sum, we have

∑_{i=1}^{m_{1}} T (n_{i}) < \frac{97m_{1}}{54} · \frac{1}{X_{0}} .

If T (n_{m_{1}}) is not part of such a complete partial sum but T (n_{m_{1}−1}) is, we have

∑_{i=1}^{m_{1}} T (n_{i}) < \frac{97(m_{1} − 1)}{54} · \frac{1}{X_{0}} + \frac{3}{X_{0}} = \frac{97m_{1} + 65}{54} · \frac{1}{X_{0}} .

Here, we used the trivial bound T (n_{m_{1}}) < \frac{3}{X_{0}} , as noted in Remark 7.

If neither T (n_{m_{1}}) nor T (n_{m_{1}−1}) are part of such a complete partial sum, we know that the last complete partial sum ended with T (n_{m_{1}−2}). With this, and by applying Lemma 12 to the sum T (n_{m_{1}−1}) + T (n_{m_{1}}), we get

∑_{i=1}^{m_{1}} T (n_{i}) < \frac{97(m_{1} − 2)}{54} · \frac{1}{X_{0}} + \frac{89}{18} · \frac{1}{X_{0}} = \frac{97m_{1} + 73}{54} · \frac{1}{X_{0}} .

3 On Collatz m-cycles

Definition 15. From now on, let δ := \frac{log(3)}{log(2)} > 1.

The following theorem and its proof are similar to the work done by Eliahou in [3].

Theorem 16. Let K be the number of odd numbers in a given m-cycle and L be the number of even numbers in it. Further let k_{i}, n_{i} and T (n_{i}) be as in Definition 6. Then,

δ < \frac{K + L}{K} < δ + \frac{1}{K · 3 · log(2)} · ∑_{i=1}^{m} T (n_{i}).

Proof. Let Ω be the set of numbers in the m-cycle, Ω_{o} the subset of odd numbers and Ω_{e} the subset of even numbers. Then we have |Ω_{o}| = K, |Ω_{e}| = L, and (due to cyclicity)

∏_{n∈Ω} n = ∏_{n∈Ω} C(n) = ∏_{n∈Ω_{e}} C(n) · ∏_{n∈Ω_{o}} C(n) = ∏_{n∈Ω_{e}} \frac{n}{2} · ∏_{n∈Ω_{o}} \frac{3n + 1}{2}

= ∏_{n∈Ω_{e}} (n · \frac{1}{2}) · ∏_{n∈Ω_{o}} (n · \frac{1}{2} · (3 + \frac{1}{n}))

= 2^{−(L+K)} · ∏_{n∈Ω} n · ∏_{n∈Ω_{o}} (3 + \frac{1}{n}) ,

2^{K+L} = ∏_{n∈Ω_{o}} (3 + \frac{1}{n}) .

The right-hand side is obviously larger than ∏_{n∈Ω_{o}} 3 = 3^{K}; however, because of the inequality between arithmetic and geometric mean, it is also smaller than

∏_{n∈Ω_{o}} (3 + \frac{1}{n}) = ( \sqrt[K]{∏_{n∈Ω_{o}} (3 + \frac{1}{n})})^{K} ≤ (\frac{1}{K} · ∑_{n∈Ω_{o}} (3 + \frac{1}{n}))^{K}
= (3 + μ)^{K},

where μ is μ := \frac{1}{K} · ∑_{n∈Ω_{o}} \frac{1}{n}. Putting things together, we get

3^{K} < 2^{K+L} ≤ (3 + μ)^{K},
K · log(3) < (K + L) · log(2) ≤ K · log(3 + μ)

= K · (log(3) + log (1 + \frac{μ}{3}))

< K · (log(3) + \frac{μ}{3}) ,

δ = \frac{log(3)}{log(2)} < \frac{K + L}{K} < \frac{log(3)}{log(2)} + \frac{μ}{3 · log(2)}.

Now let us rewrite μ:

μ = \frac{1}{K} · ∑_{n∈Ω_{o}} \frac{1}{n} = \frac{1}{K} · ∑_{i=1}^{m} ∑_{t=0}^{k_{i}−1} \frac{1}{C^{t}(n_{i})},

where k_{i} is the exact number of consecutive o-steps after n_{i} to the next local maximum on the cycle. Thus, we have ∑_{i=1}^{m} k_{i} = K, as every such step follows an odd number on the cycle. The inner sum is T (n_{i}) as defined in the theorem. Hence, we get

μ = \frac{1}{K} · ∑_{i=1}^{m} T (n_{i}),

δ < \frac{K + L}{K} < δ + \frac{1}{K · 3 · log(2)} · ∑_{i=1}^{m} T (n_{i}).

This leads to the following result:

Corollary 17. With K, L as in Theorem 16, we have

δ < \frac{K + L}{K} < δ + \frac{1}{K · 3 log(2)} · \frac{97}{54} · m · \frac{1}{X_{0}} .

Proof. From Theorem 16 we know

δ < \frac{K + L}{K} < δ + \frac{1}{K · 3 · log(2)} · ∑_{i=1}^{m} T (n_{i}).

Thus, we need to prove ∑_{i=1}^{m} T (n_{i}) < \frac{97}{54} · m · \frac{1}{X_{0}} . To do so, let t be an arbitrarily large integer and remember that we set n_{m+1} := n_{1}, n_{m+2} := n_{2}, and so on. With m_{1} := t · m and using Theorem 14, we get

t · ∑_{i=1}^{m} T (n_{i}) = ∑_{i=1}^{t·m} T (n_{i}) < \frac{97(t · m) + 73}{54} · \frac{1}{X_{0}} ,

∑_{i=1}^{m} T (n_{i}) < \frac{97}{54} · m · \frac{1}{X_{0}} + \frac{1}{t} · \frac{73}{54} · \frac{1}{X_{0}} .

As one can choose t as large as needed, the second summand can be lessened to ε for every ε > 0. Thus, we have

∑_{i=1}^{m} T (n_{i}) < \frac{97}{54} · m · \frac{1}{X_{0}} + ε for every ε > 0 and, therefore,

∑_{i=1}^{m} T (n_{i}) ≤ \frac{97}{54} · m · \frac{1}{X_{0}} ,

which proves the claim.

Remark 18. Since \frac{1}{3} · \frac{97}{54} ≈ 0.599, this is an improvement of more than 40% over Corollary 5 of Simons and de Weger in [12].

Using a computer program and the known results for X_{0}, we get a stronger result: Corollary 19. Provided that X_{0} ≥ 695 · 2^{60}, we have

δ < \frac{K + L}{K} < δ + \frac{1}{K · 3 log(2)} · \frac{7}{5} · m · \frac{1}{695 · 2^{60}} .

Proof. In Lemma 11 and Corollary 13, we proved that the average summand in a complete partial sum ∑_{i} T (n_{i}) is smaller than a constant times \frac{1}{X_{0}} . We obtained the best value for this constant in Corollary 13 with \frac{97}{54}. To achieve this result, we had to consider partial sums of up to three consecutive summands in this sum.

If we want to get even lower bounds for this constant, we have two possible options: First, we can increase the number of considered consecutive summands T (n_{i}) in a partial sum. But this increases also the amount of work necessary in the case-by-case analysis. A second possibility is to use the exact known value of X_{0} instead of using it as a parameter. This significantly reduces the number of cases to be considered.

Providing that X_{0} > 695 · 2^{60} we want to prove that the average T (n_{i}) is smaller than \frac{7}{5} · \frac{1}{695·2^{60}} . To do so, we apply the same methods as above to get upper bounds of the form c · \frac{1}{n_{i}} for sums of T (n_{i}) for consecutive local minima n_{i}. But if r is the smallest positive integer with r ≡ n_{i} (mod 2^{k}) for some value of k (the number of, for this case, “fixed” steps in the Collatz sequence after n_{i}), we clearly have n_{i} ≥ r. If r is large enough, the calculated bound falls below the value of \frac{7}{5} · \frac{1}{695·2^{60}} . Then we can mark this case as proven.

Since this kind of proof gets very lengthy, we automated this process by writing a small program in C++. It considers partial sums with up to 36 consecutive summands T (n_{i}).

Having used the program to prove this property, we can proceed as we did in the proof of Corollary 17 and obtain the desired result.

The following lemma also can be found in [12]. Lemma 20. Let n_{i}, n_{i+1} be two successive local minima in an m-cycle. Then we have n_{i+1} < n_{i}^{δ}. Proof. Let k_{i} be the exact number of consecutive o-steps after n_{i} until the next local maximum in the cycle. By Lemma 8 and its proof, we know that there is a positive integer a with n_{i} = a · 2^{k_{i}} − 1 and C^{k_{i}}(n_{i}) = a · 3^{k_{i}} − 1. Since k_{i} is the exact number of consecutive such steps after n_{i}, we know that C^{k_{i}}(n_{i}) has to be even. Therefore, we know that n_{i+1}, the next odd number, fulfills the inequality n_{i+1} ≤ \frac{1}{2} · C^{k_{i}}(n_{i}). Thus, we get

n_{i+1} ≤ \frac{1}{2} · C^{k_{i}}(n_{i}) = \frac{1}{2} · (a · 3^{k_{i}} − 1) < \frac{3^{k_{i}}}{2} · a = \frac{3^{k_{i}}}{2} · \frac{n_{i} + 1}{2^{k_{i}}}

= (2^{k_{i}})^{δ−1} · \frac{1}{2} · (n_{i} + 1) ≤ (a · 2^{k_{i}})^{δ−1} · \frac{1}{2} · (n_{i} + 1) = \frac{1}{2} · (n_{i} + 1)^{δ}

= \frac{1}{2} · (\frac{n + 1}{n})^{δ} · n_{i}^{δ} < \frac{1}{2} · (1 + \frac{1}{n})^{2} · n_{i}^{δ} < n_{i}^{δ}, as n_{i} > X_{0} > 3.

Note that the statement is also true for i = m and n_{m+1} := n_{1}.

Theorem 21. Let K be the number of odd numbers in a given m-cycle, and let L be the number of even numbers in it. Further, assume there exists a positive integer m_{2} with

m_{2} ≤ m and \frac{δ^{m_{2}} − 1}{δ − 1} · \frac{log (\frac{162}{97} · X_{0})}{log(2)} ≤ \frac{m_{2}}{m} · K.

Let v = \frac{m_{2}}{m} · K · \frac{δ−1}{δ^{m_{2}}−1}. Then we get

δ < \frac{K + L}{K} < δ + \frac{1}{K · 3 log(2)} · (\frac{97(m − m_{2}) + 73}{54 · X_{0}} + \frac{3}{2^{v} − 1} + \frac{3 · (m_{2} − 1)}{(2^{v} − 1)^{δ}}) .

If m_{2} = m − 1 we get the better estimate

δ < \frac{K + L}{K} < δ + \frac{1}{K · 3 log(2)} · (\frac{3}{X_{0}} + \frac{3}{2^{v} − 1} + \frac{3 · (m − 2)}{(2^{v} − 1)^{δ}})

and for m_{2} = m

δ < \frac{K + L}{K} < δ + \frac{1}{K · 3 log(2)} · (\frac{3}{2^{v} − 1} + \frac{3 · (m − 1)}{(2^{v} − 1)^{δ}}) .

Proof. First, let m_{2} be as given in this theorem. If the only nonnegative integer fulfilling the given inequality is m_{2} = 0, Corollary 17 and Corollary 19 give good upper bounds for \frac{K+L}{K}. Now let the inequality be true for some integer m_{2} > 0.

From Theorem 16, we know

δ < \frac{K + L}{K} < δ + \frac{1}{K · 3 · log(2)} · ∑_{i=1}^{m} T (n_{i}).

Therefore, we have to give upper bounds on ∑_{i=1}^{m} T (n_{i}) in the different cases. To do so, we use Theorem 14 and Lemma 20:

There are m_{2} consecutive local minima which are directly followed by at least \frac{m_{2}}{m} · K osteps in total. (If this would not be the case, all of the sums k_{1}+⋯+k_{m_{2}}, k_{2}+⋯+k_{m_{2}+1}, … and k_{m}+k_{1}+⋯+k_{m_{2}−1} would be smaller than \frac{m_{2}}{m} ·K. But adding these m sums together gives m_{2} · K, as every k_{i} occurs in exactly m_{2} such sums and ∑_{i=1}^{m} k_{i} = K, which contradicts the assumption.) W.l.o.g., let these m_{2} consecutive local minima be n_{m−m_{2}+1}, n_{m−m_{2}+2}, …, n_{m}.

From Lemma 8 we know that k_{i} ≤ \frac{log(n_{i}+1)}{log(2)}. Now Lemma 20 gives n_{i+1} < n_{i}^{δ} and,

therefore, n_{i+1} + 1 < n_{i}^{δ} + 1 < (n_{i} + 1)^{δ} which leads to the inequality k_{i+1} < δ · \frac{log(n_{i}+1)}{log(2)}.

Subsequently, in an analogous way we get k_{i+ℓ} < δ^{ℓ} · \frac{log(n_{i}+1)}{log(2)}.

Now we can sum up these estimates for i = m − m_{2} + 1, …, m:

\frac{m_{2}}{m} · K ≤ ∑_{i=m−m_{2}+1}^{m} k_{i} = ∑_{ℓ=0}^{m_{2}−1} k_{(m−m_{2}+1)+ℓ}

≤ \frac{log(n_{m−m_{2}+1} + 1)}{log(2)} · ∑_{ℓ=0}^{m_{2}−1} δ^{ℓ}

= \frac{log(n_{m−m_{2}+1} + 1)}{log(2)} · \frac{δ^{m_{2}} − 1}{δ − 1}.

From the premise on m_{2}, we know that this is larger than

\frac{δ^{m_{2}} − 1}{δ − 1} · \frac{log (\frac{162}{97} · X_{0})}{log(2)}.

Thus, we get

n_{m−m_{2}+1} + 1 > \frac{162}{97} · X_{0} and, therefore, n_{m−m_{2}+1} ≥ \frac{162}{97} · X_{0}.

Now with Remark 7 we conclude T (n_{m−m_{2}+1}) < \frac{3}{n_{m−m_{2}+1}} < \frac{97}{54} · \frac{1}{X_{0}} . Thus, this estimate on T (n_{m−m_{2}+1}) is at least as good as the one we get from Theorem 14. But we can get a better one:

From the definition of v, we get v · \frac{δ^{m_{2}}−1}{δ−1} = \frac{m_{2}}{m} · K. Thus, we have

v ≤ \frac{log(n_{m−m_{2}+1} + 1)}{log(2)} or, equivalently, 2^{v} − 1 ≤ n_{m−m_{2}+1}.

Now this gives T (n_{m−m_{2}+1}) < \frac{3}{2^{v}−1} and, since

n_{m−m_{2}+1+ℓ} < n_{m−m_{2}+1}^{(δ^{ℓ})} ≤ n_{m−m_{2}+1}^{δ},

we get the inequality T (n_{m−m_{2}+1+ℓ}) < \frac{3}{(2^{v}−1)^{δ}}. Using this together with Theorem 14 and m_{1} := m − m_{2}, we get

∑_{i=1}^{m} T (n_{i}) = ∑_{i=1}^{m−m_{2}} T (n_{i}) + T (n_{m−m_{2}+1}) + ∑_{i=m−m_{2}+1+1}^{m} T (n_{i})

< \frac{97(m − m_{2}) + 1}{54 · X_{0}} + \frac{3}{2^{v} − 1} + \frac{3 · (m_{2} − 1)}{(2^{v} − 1)^{δ}},

which proves the general statement for 1 ≤ m_{2} ≤ m. For m_{2} = m − 1, the first sum ∑_{i=1}^{m−m_{2}} T (n_{i}) = T (n_{1}) can be better bounded above by \frac{3}{X_{0}} , as seen in Remark 7. For m_{2} = m, this first sum is empty and therefore zero.

We now give a well known lemma for diophantine approximation:

Lemma 22. Let 0 < α < β be two real numbers with continued fraction expansions α = [a_{0}; a_{1}, …, a_{k−1}, a_{k}, …] and β = [a_{0}; a_{1}, …, a_{k−1}, b_{k}, …]. Then every fraction in the open interval (α, β) has a denominator which is not smaller than the one of γ = [a_{0}; a_{1}, …, a_{k−1}, c_{k}] with c_{k} = min(a_{k}, b_{k}) + 1.

Proof. First, let γ be some real number with α < γ < β. Since ⌊α⌋ = a_{0} = ⌊β⌋, we also have ⌊γ⌋ = a_{0}. Thus, 0 < α − a_{0} < γ − a_{0} < β − a_{0} < 1 and, therefore, 1 < \frac{1}{β−a_{0}} < \frac{1}{γ−a_{0}} < \frac{1}{α−a_{0}} .

Since ⌊\frac{1}{β−a_{0}} ⌋ = a_{1} = ⌊\frac{1}{α−a_{0}} ⌋, we also get ⌊\frac{1}{γ−a_{0}} ⌋ = a_{1}, and so on.

Thus, for every real number γ within the interval (α, β), we get the same beginning in the continued fraction expansion of γ: γ = [a_{0}; a_{1}, …, a_{k−1}, …].

If k is even, increasing the partial denominator increases the fraction. Thus, we have a_{k} < b_{k} and

[a_{0}; a_{1}, …, a_{k−1}, a_{k}] < α < [a_{0}; a_{1}, …, a_{k−1}, a_{k} + 1] < β.

If we choose c_{k} := a_{k} + 1 = min(a_{k} + b_{k}) + 1, we get the fraction with smallest denominator in this interval.

If k is odd, decreasing the partial denominator increases the fraction. Thus, we have a_{k} > b_{k} and

α < [a_{0}; a_{1}, …, a_{k−1}, b_{k} + 1] < β < [a_{0}; a_{1}, …, a_{k−1}, b_{k}].

If we choose c_{k} := b_{k} + 1 = min(a_{k} + b_{k}) + 1, we get the fraction with smallest denominator in this interval.

Theorem 23 (Main Theorem). There is no m-cycle with m ≤ 91.

Proof. Let m ≤ 91. From Theorem 3 in [12] we know that K > 7 · 10^{11}.

With X_{0} = 695 · 2^{60} ≈ 8 · 10^{20}, as given in Definition 4, we get m_{2} ≥ 47. Now, from Theorem 21 we have

δ < \frac{K + L}{K} < δ + 6.9 · 10^{−32}.

By using continued fractions as in Lemma 22, we can now get a better lower bound for K with

K > 5.2 · 10^{15}.

And now we can reiterate this process!

In the next run, we get m_{2} ≥ 67, δ < \frac{K+L}{K} < δ +5.1·10^{−36} and, therefore, K > 3.97·10^{17}. Applying this newer bound on K once more, we get m_{2} ≥ 77,

δ < \frac{K+L}{K} < δ + 4.1 · 10^{−38} and, hence, K > 4.64 · 10^{18}.

In the forth run we get m_{2} ≥ 82, δ < \frac{K+L}{K} < δ + 2.3 · 10^{−39} and with this K > 2.74 · 10^{19}. From there we get m_{2} ≥ 86, δ < \frac{K+L}{K} < δ + 2.3 · 10^{−40} and K > 7.76 · 10^{19}. And from this we get m_{2} ≥ 88, δ < \frac{K+L}{K} < δ + 5.3 · 10^{−41} and K > 2.05 · 10^{20}.

Applying this lower bounnd a last time we get m_{2} ≥ 91, δ < \frac{K+L}{K} < δ + 1.11 · 10^{−43} and K > 7.94 · 10^{21}.

But this last lower bound on K is larger than the upper bound of K < 1.4784mδ^{m} < 2.2 · 10^{20} given by Simons and de Weger [12]. Thus, no such m-cycle can exist.

Using the same technique as above and Corollaries 17 and 19, we also get new lower bounds on K for m-cycles with m ≥ 92:

Corollary 24. In Table 1 different pairs of values m und K are listed. If there is a m-cycle with m equal or smaller than the given value, this cycle consists of at least the corresponding number of K odd members.

\begin{matrix}m & K \\ 98 & 7.76 · 10^{19} \\ 117 & 2.74 · 10^{19} \\ 276 & 4.68 · 10^{18} \\ 3079 & 3.97 · 10^{17} \\ 12055 & 1.30 · 10^{17} \\ ⋮ & ⋮ \\ 948987 & 4.30 · 10^{15} \\ 1.14 · 10^{6} & 3.81 · 10^{15} \\ ⋮ & ⋮ \\ 1.33 · 10^{9} & 1.64 · 10^{12} \\ 1.54 · 10^{9} & 8.90 · 10^{11} \\ 9.46 · 10^{9} & 1.37 · 10^{11} \\ For all m ∈ ℕ & 7.20 · 10^{10} \end{matrix}

Table 1: Corollary 24: If m ≤ ⋯, then K > · · ·.

Proof. The first three lines follow from Theorem 21, all others except the last one from Corollary 19, and the last one from the statement independent of m in [4, 9] or [3], using the known value of X_{0} as in Definition 4 and given in [2].

Remark 25. Over time, with better known lower limits on X_{0}, one gets slightly better results in Corollary 24. The results in this corollary are in some cases significant improvements on the bounds given by Theorem 3 in [12].

4 Cycles without knowing m

In a manner similar to that in Lemma 11 and Corollary 13, we want to give an upper bound on another weighted average of the T (n_{i}):

Lemma 26. For all 1 ≤ i, we have

T (n_{i}) < k_{i} · \frac{3}{4} · \frac{1}{X_{0}} ,
T (n_{i}) + T (n_{i+1}) < (k_{i} + k_{i+1}) · \frac{3}{4} · \frac{1}{X_{0}} ,
or T (n_{i}) + T (n_{i+1}) + T (n_{i+2}) < (k_{i} + k_{i+1} + k_{i+2}) · \frac{3}{4} · \frac{1}{X_{0}} .

Proof. As in the proofs of Lemma 11 and Corollary 13, let k_{i} be the exact number of osteps following n_{i} and ℓ_{i} the exact number of e-steps following them, such that we have n_{i+1} = C^{k_{i}+ℓ_{i}}(n_{i}).

If k_{i} = 1, there exists a nonnegative integer a with n_{i} = 4·a+1 such that C^{2}(n_{i}) = 3·a+1. Since C^{2}(n_{i}) ≥ X_{0} + 1, we have n_{i} ≥ \frac{4}{3} · X_{0} + 1 > \frac{4}{3} · X_{0} and, therefore, T (n_{i}) < \frac{3}{4} · \frac{1}{X_{0}} .

If k_{i} = 3 ,we know T (n_{i}) < \frac{19}{9} · \frac{1}{X_{0}} < 3 · \frac{3}{4} · \frac{1}{X_{0}} .

If k_{i} ≥ 4, we have T (n_{i}) < 3 · \frac{1}{X_{0}} ≤ k_{i} · \frac{3}{4} · \frac{1}{X_{0}} .

This only leaves the case k_{i} = 2 for further investigation. There we have T (n_{i}) = \frac{5}{3} · \frac{1}{n_{i}}. If ℓ_{i} ≥ 2, we know from the cited proofs that n_{i} > 2X_{0} and, therefore, T (n_{i}) < \frac{5}{6} · \frac{1}{X_{0}} < 2· \frac{3}{4} · \frac{1}{X_{0}} .

Thus, let k_{i} = 2 and ℓ_{i} = 1. Then there exists a nonnegative integer a with n_{i} = 8 · a + 3 and n_{i+1} = 9 · a + 4. If k_{i+1} = 1, we have n_{i+1} ≥ \frac{4}{3} · X_{0} + 1 and n_{i} ≥ \frac{32}{27} · X_{0} + \frac{1}{3} > \frac{32}{27} · X_{0}. With this, we get

T (n_{i}) < \frac{5}{3} · \frac{27}{32} · \frac{1}{X_{0}} = \frac{45}{32} · \frac{1}{X_{0}} < 2 · \frac{3}{4} · \frac{1}{X_{0}} .

In the case k_{i} = 2 and ℓ_{i} = 1 we generally have n_{i+1} > \frac{9}{8} · n_{i}. Thus, if k_{i+1} ≥ 5, we get

T (n_{i}) + T (n_{i+1}) < (\frac{5}{3} + 3 · \frac{9}{8}) · \frac{1}{X_{0}} = \frac{121}{24} · \frac{1}{X_{0}}

< 7 · \frac{3}{4} · \frac{1}{X_{0}} ≤ (k_{i} + k_{i+1}) · \frac{3}{4} · \frac{1}{X_{0}} .

If k_{i} = 2, ℓ_{i} = 1 and k_{i+1} = 4, with the better estimate T (n_{i+1}) < \frac{65}{27} · \frac{1}{n_{i+1}} the following inequality holds:

T (n_{i}) + T (n_{i+1}) < (\frac{5}{3} + \frac{65}{27} · \frac{9}{8}) · \frac{1}{X_{0}} = \frac{105}{24} · \frac{1}{X_{0}}

< 6 · \frac{3}{4} · \frac{1}{X_{0}} = (k_{i} + k_{i+1}) · \frac{3}{4} · \frac{1}{X_{0}} .

This leaves k_{i} = 2, ℓ_{i} = 2 and k_{i+1} ∈ {2, 3}. If ℓ_{i+1} ≥ 2, we have n_{i+1} > 2X_{0} as above and, therefore, n_{i+1} ≥ 2X_{0} + 1 and, hence, n_{i} = \frac{8}{9} · n_{i+1} − \frac{5}{9} > \frac{16}{9} · X_{0}. With this, we get

T (n_{i}) < \frac{5}{3} · \frac{9}{16} · \frac{1}{X_{0}} < 2 · \frac{3}{4} · \frac{1}{X_{0}} .

Therefore, from now on we can assume ℓ_{i+1} = 1. Let k_{i} = 2, ℓ_{i} = 1 and in this case k_{i+1} = 2. Then there exists a nonnegative integer a with n_{i} = 2^{6} · a + 59 and C^{2+1+2+1}(n_{i}) = n_{i+2} = 3^{4} · a + 76. Moreover, we have

T (n_{i}) + T (n_{i+1}) < \frac{5}{3} · \frac{1}{n_{i}} + \frac{5}{3} · \frac{1}{n_{i+1}} < \frac{5}{3} · \frac{1}{n_{i}} + \frac{5}{3} · \frac{8}{9} · \frac{1}{n_{i}} = \frac{85}{27} · \frac{1}{n_{i}} .

If k_{i} = 2, ℓ_{i} = 1, k_{i+1} = 2, ℓ_{i+1} = 1 and k_{i+2} = 1, we get n_{i+2} ≥ \frac{4}{3} · X_{0} + 1 and, therefore, n_{i} > \frac{256}{243} · X_{0} − 1. Hence,

T (n_{i}) + T (n_{i+1}) < \frac{85}{27} · \frac{n_{i} + 1}{n_{i}} · \frac{1}{n_{i} + 1}

< \frac{85}{27} · \frac{243}{256} · \frac{n_{i} + 1}{n_{i}} · \frac{1}{X_{0}}

= \frac{765}{256} · \frac{n_{i} + 1}{n_{i}} · \frac{1}{X_{0}}

< \frac{765}{256} · \frac{766}{765} · \frac{1}{X_{0}} (as n_{i} > X_{0} > 765)

< \frac{766}{256} · \frac{1}{X_{0}} < 4 · \frac{3}{4} · \frac{1}{X_{0}} .

If k_{i+2} = 2, we get

T (n_{i+2}) = \frac{5}{3} · \frac{1}{n_{i+2}} < \frac{5}{3} · \frac{64}{81} · \frac{1}{X_{0}} = \frac{320}{243} · \frac{1}{X_{0}}

and, thus,

T (n_{i}) + T (n_{i+1}) + T (n_{i+2}) < (\frac{85}{27} + \frac{320}{243}) · \frac{1}{X_{0}} = \frac{1085}{243} · \frac{1}{X_{0}}

< 6 · \frac{3}{4} · \frac{1}{X_{0}} = (k_{i} + k_{i+1} + k_{i+2}) · \frac{3}{4} · \frac{1}{X_{0}} .

In the same way, for k_{i+2} = 3 we get T (n_{i+2}) < \frac{19}{9} · \frac{64}{81} · \frac{1}{X_{0}} = \frac{1216}{729} · \frac{1}{X_{0}} and

T (n_{i}) + T (n_{i+1}) + T (n_{i+2}) < (\frac{85}{27} + \frac{1216}{729}) · \frac{1}{X_{0}} = \frac{3511}{729} · \frac{1}{X_{0}}

< 7 · \frac{3}{4} · \frac{1}{X_{0}} = (k_{i} + k_{i+1} + k_{i+2}) · \frac{3}{4} · \frac{1}{X_{0}} .

For k_{i+2} ≥ 4 we have T (n_{i+2}) < 3 · \frac{64}{81} · \frac{1}{X_{0}} = \frac{64}{27} · \frac{1}{X_{0}} . Thus,

T (n_{i}) + T (n_{i+1}) + T (n_{i+2}) < (\frac{85}{27} + \frac{64}{27}) · \frac{1}{X_{0}} = \frac{149}{27} · \frac{1}{X_{0}}

< 8 · \frac{3}{4} · \frac{1}{X_{0}} = (k_{i} + k_{i+1} + k_{i+2}) · \frac{3}{4} · \frac{1}{X_{0}} ,

which concludes the proof in the case k_{i} = 2, ℓ_{i} = 1, k_{i+1} = 2 and ℓ_{i+1} = 1.

Now we only need to consider the case k_{i} = 2, ℓ_{i} = 1, k_{i+1} = 3 and ℓ_{i+1} = 1. Here, there exists a nonnegative integer a with n_{i} = 2^{7} · a + 91 and C^{2+1+3+1}(n_{i}) = n_{i+2} = 3^{5} · a + 175. We also have

T (n_{i}) + T (n_{i+1}) < \frac{5}{3} · \frac{1}{n_{i}} + \frac{19}{9} · \frac{1}{n_{i+1}} < \frac{5}{3} · \frac{1}{n_{i}} + \frac{19}{9} · \frac{8}{9} · \frac{1}{n_{i}} = \frac{297}{81} · \frac{1}{n_{i}} .

If k_{i+2} = 1, we have T (n_{i+2}) = \frac{1}{n_{i+2}} < \frac{128}{243} · \frac{1}{n_{i}} and, therefore,

T (n_{i}) + T (n_{i+1}) + T (n_{i+1}) < (\frac{297}{81} + \frac{128}{243}) · \frac{1}{X_{0}}

= \frac{1019}{243} · \frac{1}{X_{0}} < 6 · \frac{3}{4} · \frac{1}{X_{0}}

= (k_{i} + k_{i+1} + k_{i+2}) · \frac{3}{4} · \frac{1}{X_{0}} .

At last, if k_{i+2} ≥ 2 we have T (n_{i+2}) < \frac{3}{n_{i+2}} < \frac{128}{81} · \frac{1}{n_{i}}, and with this, we get

T (n_{i}) + T (n_{i+1}) + T (n_{i+1}) < (\frac{297}{81} + \frac{128}{81}) · \frac{1}{X_{0}}

= \frac{425}{81} · \frac{1}{X_{0}} < 7 · \frac{3}{4} · \frac{1}{X_{0}}

≤ (k_{i} + k_{i+1} + k_{i+2}) · \frac{3}{4} · \frac{1}{X_{0}} ,

which concludes the last open case and, therefore, the proof.

This leads to a result similar to that yielded by the Main Theorem 21, but independent of the number m of local minima in the nontrivial cycle:

Theorem 27. Let K be the number of odd numbers in a given m-cycle, and let L be the number of even numbers in it. Then

δ < \frac{K + L}{K} < δ + \frac{1}{3 log(2)} · \frac{3}{4} · \frac{1}{X_{0}} .

Proof. As in the proof of Theorem 21, the only thing we have to do is proving the inequality

∑_{i=1}^{m} T (n_{i}) ≤ K · \frac{3}{4} · \frac{1}{X_{0}} .

To do so, we proceed as we did in the proofs of Theorem 14 and Corollary 17. First, let m_{1} be a positive integer and consider the sum

∑_{i=1}^{m_{1}} T (n_{i}).

We break this sum into partial sums consisting of one, two, or three consecutive summands. We can do this in such a way that for all partial sums (with the possible exception of the last) we know by Lemma 26 that each of these is smaller than k· \frac{3}{4} · \frac{1}{X_{0}} , where k is the number of o-steps in the at most three consecutive strictly increasing parts of the given nontrivial cycle. The last partial sum consists of at most two summands. Using the trivial bounds T (n_{m_{1}−1}) < 3 · \frac{1}{X_{0}} and T (n_{m_{1}}) < 3 · \frac{1}{X_{0}} , we get

∑_{i=1}^{m_{1}} T (n_{i}) < (∑_{i=1}^{m_{1}} k_{i}) · \frac{3}{4} · \frac{1}{X_{0}} + 2 · 3 · \frac{1}{X_{0}}

= (∑_{i=1}^{m_{1}} k_{i} + 8) · \frac{3}{4} · \frac{1}{X_{0}} .

Now, let t be an arbitrarily large integer and m_{1} = t · m. Then we get

t · ∑_{i=1}^{m} T (n_{i}) = ∑_{i=1}^{t·m} T (n_{i}) < (∑_{i=1}^{t·m} k_{i} + 8) · \frac{3}{4} · \frac{1}{X_{0}}

= (t · K + 8) · \frac{3}{4} · \frac{1}{X_{0}} , where we used ∑_{i=1}^{t·m} k_{i} = t · ∑_{i=1}^{m} k_{i} = t · K.

This leads directly to

∑_{i=1}^{m} T (n_{i}) < K · \frac{3}{4} · \frac{1}{X_{0}} + ε for all ε > 0 and, therefore,

∑_{i=1}^{m} T (n_{i}) ≤ K · \frac{3}{4} · \frac{1}{X_{0}} as desired.

Remark 28. Theorem 27 leads to a reduction of the bounds on X_{0} given in or computed by the methods in [3], which are needed for reaching the next threshold on K in a nontrivial cycle, by 25%. Thus, to prove that every nontrivial cycle contains at least K > 1.375 · 10^{11} odd numbers, using previous methods one would have to show δ < \frac{K+L}{K} < δ + 1.1032 · 10^{−22}, and therefore, X_{0} ≥ 3781 · 2^{60}. With the result given in Theorem 27, it suffices to show X_{0} ≥ 2836 · 2^{60}.

If one is interested in the problem of lowering the value for X_{0} given in the last remark to the greatest extend possible, one can use the methods of Lemma 26 in an automated way.

Corollary 29. If X_{0} ≥ 1536 · 2^{60} = 3 · 2^{69} then every nontrivial cycle contains at least K > 1.375 · 10^{11} odd numbers.

Proof. We have written a small C++ program, which mainly uses the methods given in the proof of Lemma 26. There is one key exception: for every situation, the program tracks the residue classes modulo powers of two for a given number n_{i}. If the smallest positive member of this residue class is already larger than the needed bound of 3781 · 2^{60}, this case no longer needs to be considered, since then one can use the trivial bound T (n_{i}) ≤ \frac{k_{i}}{n_{i}} < k_{i} · \frac{1}{3781·2^{60}} .

This bound on X_{0} was reached after five weeks of computing time on an i9 processor of the 11th generation with 8 cores.

Remark 30. If one wants to prove that every nontrivial cycle has at least K > 1.375·10^{11} odd members with Corollary 29 it suffices to proof for all numbers less than or equal to 1536 · 2^{60} that their respective Collatz sequences reach the trivial cycle. This bound on X_{0} is only about 40% of the one needed by the methods in [3], thus saving nearly 60% of computing time requierd to reach the next threshold for the next larger lower bound on the number of members a nontrivial Collatz cycle must have. As the current fastest project for increasing X_{0}, see [2], needed over 27 months for completing the search up to 512 · 2^{60} = 2^{69}, this reduction has some impact.

In our numerical experiments, we get that by lowering the bound on X_{0} by 2^{60} (that is, e.g., from 1536 · 2^{60} to 1535 · 2^{60}) the computing time needed increases by about 1.5%. Thus, the chosen bound of X_{0} in Corollary 29 cannot be decreased by a reasonable amount before this computation becomes less effective than the search in [2].

Remark 31. All results in this paper, with the exception of Corollaries 19, 24, and 29, are independent of the exact value of X_{0}, provided it is not too small. (In all other lemmas, theorems, and corollaries we needed at most X_{0} > 765.) Thus, they scale up and give better absolute values, as better results on X_{0} become available.

References

[1] D. Barina, Convergence verification of the Collatz problem, J. Supercomputing 77 (2021), 2681–2688.

[2] D. Barina, Convergence verification of the Collatz problem, preprint, 2023. Available at

    https://pcbarina.fit.vutbr.cz.

[3] S. Eliahou, The 3x+1 problem: New lower bounds on nontrivial cycle lengths, Discrete Math. 118 (1993), 45–56.

[4] C. Hercher, Über die Länge nicht-trivialer Collatz-Zyklen (I), Die Wurzel 6 (2018), 118–128.

[5] C. Hercher, Über die Länge nicht-trivialer Collatz-Zyklen (II), Die Wurzel 7 (2018), 146–154.

[6] G. T. Leavens and M. Vermeulen, 3x + 1 search programs, Comput. Math. Appl. 11 (1992), 79–99.

[7] T. Olivera e Silva, Maximum excursion and stopping time record-holders for the 3x + 1 problem: computational results, Math. Comp. 225 (1999), 371–384.

[8] T. Olivera e Silva, Empirical verification of the 3x + 1 and related conjectures, in J. Lagarias, ed., The Ultimate Challenge: The 3x + 1 Problem, American Mathematical Society, 2010, pp. 189–207.

[9] S. Puchert, Anmerkung zum Artikel “Über die Länge nicht-trivialer Collatz-Zyklen”, Die Wurzel 11 (2018), 243–250.

[10] E. Roosendaal, 3x + 1 path records, preprint, 2022. Available at https://www.ericr.

    nl/wondrous/pathrecs.html.

[11] J. Simons and B. de Weger, Theoretical and computational bounds for m-cycles of the 3n + 1-problem, Acta Arith. 117 (2005), 51–70.

[12] J. Simons and B. de Weger, Theoretical and computational bounds for m-cycles of the 3n + 1 problem, preprint, 2010. Available at https://deweger.net/papers/

    [35a]SidW-3n+1-v1.44[2010].pdf.

[13] T. Tao, Almost all orbits of the Collatz map attain almost bounded values, Forum Math. Pi 10 (2022), e12.

[14] R. Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976), 241–252.

2020 Mathematics Subject Classification: Primary 11B83.

Keywords: Collatz conjecture, Syracuse problem, nontrivial Collatz cycle.

(Concerned with sequences \underline{A006577} and \underline{A025586}.)

Received January 23 2022; revised version received January 24 2022, December 21 2022; December 28 2022; March 12 2023. Published in Journal of Integer Sequences, March 15 2023.

Return to Journal of Integer Sequences home page.