The 3x+1 cycles page

There is no known proof that no cycle, other than the rather trivial 4-2-1 exists in positive integers. However it is known that no such cycle can exist with a 'small' number of elements (we'll be more exact later on).

The current status on 3x+1 cycles is based on a theorem by Crandall. In 1978 he proved the following:

Theorem (Crandall, 1978)
Define 3x+1 trajectories using (3x+1)/2 for odd elements and x/2 for even elements.
Let N0 be the lowest element of a 3x+1 cycle in positive integers of cycle length k.
Furthermore, let pj / qj be a convergent with j > 4 of the expansion of the continued fraction of ln(3) / ln(2).
Then k > (3/2) * min ( qj , 2 * N0 / (qj + qj+1)

The proof can be found in this reference.

To elaborate the practical consequences of this theorem the first task is therefore to work out the convergents of the continued fraction of ln(3) / ln(2). With some labor the following table of convergents can be found (for a longer list see OEIS: A005564).


From these numbers, in particular the denominators, it is possible to determine a minimal cycle length once it is known that all numbers below a particular N actually are convergent.

Example :
Assume that all numbers up to 1500 can be shown to converge to 1.
Therefore no cycle (other than 4-2-1) can have a lowest element < 1500. Assume for the moment that a cycle exists with 1500 as its lowest element.
Now from the table above take j = 6. We see that q6 = 41.
The factor 2 * N0 / (qj + qj+1) works out as 2 * 1500 / (41+53) which is roughly 31.
Since 31 < 41 we find that the cycle length can not be lower than 3/2 * 31 = 47.

The example above clearly shows two things. First of all the minimal cycle length can be determined from the lowest N that is not yet known to be convergent. Secondly the minimal cycle length does not increase gradually with N, but increases in intervals, depending on the values of qj.

For every j there is a maximal critical value (Nmax) of N beyond which higher values of N do not give any further improvement of the minimal cycle length. The value of Nmax is equal to qj * (qj + qj+1) / 2 . For j = 6 this value lies at N = 1927. At this value q6 = 2 * N0 / (q6 + q7) so both expressions of the theorem yield identical numbers. Once it is known all numbers below 1927 are convergent the minimal cycle length can therefore be set at (3/2) * 41 which yields 62.

To increase the minimal cycle length beyond this value the next row at j=7 is needed. For lower N though the value of the second expression is below 41 and the minimal cycle length can therefore not be increased. It is only when N reaches a minimal critical value (Nmin) for this row that further improvements can be obtained. The value of Nmin can be seen to lie at qj-1 * (qj + qj+1) / 2 . For j=7 this value lies at N = 7360. At this value 2 * N0 / (q7 + q8) is equal to 41, and higher N therefore yield higher values for the minimal cycle length.

Working out these critical values for rows with j > 4 yields the following values :
(Note : larger entries for Nmin and Nmax are rounded)

jqjNmin Nmaxkmin at Nmax
1131,867 867,431,2011,771,837,06747,801
1279,335 3,035,921,2907,558,126,447119,003
13111,202 11,969,231,78316,776,990,139166,803
14190,537 599,449,615,6741,027,115,802,069285,806
1510,590,737 2,036,079,429,954113,172,673,831,05415,886,106
1610,781,274 341,535,948,748,930347,680,491,387,15916,171,911
1753,715,833 1,216,368,161,954,0006,060,343,986,623,00080,573,750
18171,928,773 10,677,992,615,805,00034,177,151,614,467,000257,893,160
19225,644,606 53,574,551,736,291,00070,312,888,338,719,500338,466,909
20397,573,379 743,140,051,792,797,0001,309,718,777,460,900,000596,360,069
216,189,245,291 2,539,711,459,647,450,00039,537,096,854,067,000,0009,283,867,937
226,586,818,670 222,990,560,815,925,000,000237,314,619,175,287,000,0009,880,228,005
2365,470,613,321 668,557,677,334,400,000,0006,645,223,342,021,410,000,00098,205,919,982
24137,528,045,312 29,155,337,030,558,700,000,00061,243,912,479,726,000,000,000206,292,067,968
25753,110,839,881 423,752,428,472,120,000,000,0002,320,490,679,441,000,000,000,0001,129,666,259,822
265,409,303,924,479 4,357,393,390,309,000,000,000,00031,297,471,658,252,000,000,000,0008,113,955,886,719

The results clearly show that the minimal possible cycle length is currently pretty large. This is because current results almost certainly indicate that all numbers up to 1020 are convergent. Up to 260 (≈ 1.15 . 1018) all numbers were checked for convergence independently by numerous projects, including the author. Lately several projects have expanded this search substantially (see the Path record page for details). The current limit is 752 . 1018.

If we accept that all numbers below the number mentioned above are indeed convergent then the numbers in row 22 indicate that a 3x+1 cycle must contain at least 9.88 billion (or roughly 10 billion) elements.

Finally we should take into account that the values above are valid for the variety of the 3x + 1 problem where an 'odd' iteration is defined as resulting in (3x+1) / 2. If one defines such an iteration as simply 3x+1, cycle lengths increase by a factor ln(6) / ln(3) ≈ 1.63. Using this definition the minimal length for a non-trivial cycle is currently well over 16 billion elements.

The proof of Crandall's Theorem can be found in
R. E. Crandall, On the "3x+1" problem, Math Comp, 32 (1978) 1281-1292.
Many thanks to the late Vic Vyssotski for working out the convergents of the continued fraction as depicted in the first table and supplying helpful insights as well.

Back to the general 3x+1 page.