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:
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:
j | p_{j} | q_{j} |
---|---|---|
1 | 1 | 1 |
2 | 2 | 1 |
3 | 3 | 2 |
4 | 8 | 5 |
5 | 19 | 12 |
6 | 65 | 41 |
7 | 84 | 53 |
8 | 485 | 306 |
9 | 1,054 | 665 |
10 | 24,727 | 15,601 |
11 | 50,508 | 31,867 |
12 | 125,743 | 79,335 |
13 | 176,251 | 111,202 |
14 | 301,994 | 190,537 |
15 | 16,785,921 | 10,590,737 |
16 | 17,087,915 | 10,781,274 |
17 | 85,137,581 | 53,715,833 |
18 | 272,500,658 | 171,928,773 |
19 | 357,638,239 | 225,644,606 |
20 | 630,138,897 | 397,573,379 |
21 | 9,809,721,694 | 6,189,245,291 |
22 | 10,439,860,591 | 6,586,818,670 |
23 | 103,768,467,013 | 65,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).
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 q_{j}.
For every j there is a maximal critical value (N_{max}) of N beyond which higher values of N do not give any further improvement of the minimal cycle length. The value of N_{max} is equal to q_{j} * (q_{j} + q_{j+1}) / 2 . For j = 6 this value lies at N = 1927. At this value q_{6} = 2 * N_{0} / (q_{6} + q_{7}) 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 (N_{min}) for this row that further improvements can be obtained. The value of N_{min} can be seen to lie at q_{j-1} * (q_{j} + q_{j+1}) / 2 . For j=7 this value lies at N = 7360. At this value 2 * N_{0} / (q_{7} + q_{8}) 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 N_{min} and N_{max} are rounded)
j | q_{j} | N_{min} | N_{max} | k_{min} at N_{max} |
---|---|---|---|---|
1 | 1 | |||
2 | 1 | |||
3 | 2 | |||
4 | 5 | |||
5 | 12 | 132 | 318 | 18 |
6 | 41 | 564 | 1,927 | 62 |
7 | 53 | 7,360 | 9,513 | 80 |
8 | 306 | 25,732 | 148,563 | 459 |
9 | 665 | 2,488,698 | 5,408,445 | 998 |
10 | 15,601 | 15,783,110 | 370,274,134 | 23,402 |
11 | 31,867 | 867,431,201 | 1,771,837,067 | 47,801 |
12 | 79,335 | 3,035,921,290 | 7,558,126,447 | 119,003 |
13 | 111,202 | 11,969,231,783 | 16,776,990,139 | 166,803 |
14 | 190,537 | 599,449,615,674 | 1,027,115,802,069 | 285,806 |
15 | 10,590,737 | 2,036,079,429,954 | 113,172,673,831,054 | 15,886,106 |
16 | 10,781,274 | 341,535,948,748,930 | 347,680,491,387,159 | 16,171,911 |
17 | 53,715,833 | 1,216,368,161,954,000 | 6,060,343,986,623,000 | 80,573,750 |
18 | 171,928,773 | 10,677,992,615,805,000 | 34,177,151,614,467,000 | 257,893,160 |
19 | 225,644,606 | 53,574,551,736,291,000 | 70,312,888,338,719,500 | 338,466,909 |
20 | 397,573,379 | 743,140,051,792,797,000 | 1,309,718,777,460,900,000 | 596,360,069 |
21 | 6,189,245,291 | 2,539,711,459,647,450,000 | 39,537,096,854,067,000,000 | 9,283,867,937 |
22 | 6,586,818,670 | 222,990,560,815,925,000,000 | 237,314,619,175,287,000,000 | 9,880,228,005 |
23 | 65,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 1 . 10^{16} 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 1 . 10^{16} 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 . 10^{15}, 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.
Back to the general 3x+1 page.