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). There is apparently no 'neat' way of obtaining these factors so these have to be calculated numerically. With some labor the following table of convergents can be found:

jpjqj
111
221
332
485
51912
66541
78453
8485306
91,054665
1024,72715,601
1150,50831,867
12125,74379,335
13176,251111,202
14301,994190,537
1516,785,92110,590,737
1617,087,91510,781,274
1785,137,58153,715,833
18272,500,658171,928,773
19357,638,239225,644,606
20630,138,897397,573,379
219,809,721,6946,189,245,291
2210,439,860,5916,586,818,670
23103,768,467,01365,470,613,321

From this table it is possible to determine a minimal cycle length once it is known that all numbers below a particular N actually are convergent (eventually reach 1).

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 : Bigger entries for Nmin and Nmax are rounded)

jqjNmin Nmaxkmin at Nmax
11   
21   
32   
45   
51213231818
6415641,92762
7537,3609,51380
830625,732148,563459
96652,488,6985,408,445998
1015,60115,783,110370,274,13423,402
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    

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 below 500 . 1015 are convergent. Up to this limit all numbers were checked for convergence independently both by Tomás Oliveira e Silva and the author (see current status), using different software and running on different hardware platforms. The 'almost certainly' simply references the fact that it is almost impossible to guarantee one hundred percent correctness when one makes computer algorithms run for many CPU years. The author firmly believes though that the results are correct. Note also that no inconsistencies between the two result sets were encountered.

If we accept therefore that all numbers below 500 . 1015 are indeed convergent then the numbers in row 19 indicate that a 3x+1 cycle must contain at least 338,466,909 (or roughly 330 million) elements. Note that this is likely to remain the lower limit for a bit longer, since it can only be improved by demonstrating the convergence of all numbers below 743 . 1015, which will take more computing effort.

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 roughly 553 million.

Reference :
The proof of Crandall's Theorem can be found in
R. E. Crandall, On the "3x+1" problem, Math Comp, 32 (1978) 1281-1292.
Acknowledgement :
Many thanks to Vic Vyssotski for working out all 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.