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). With some labor the following table of convergents can be found (for a longer list see OEIS: A005564).
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 |
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.
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 | 668,557,677,334,400,000,000 | 6,645,223,342,021,410,000,000 | 98,205,919,982 |
24 | 137,528,045,312 | 29,155,337,030,558,700,000,000 | 61,243,912,479,726,000,000,000 | 206,292,067,968 |
25 | 753,110,839,881 | 423,752,428,472,120,000,000,000 | 2,320,490,679,441,000,000,000,000 | 1,129,666,259,822 |
26 | 5,409,303,924,479 | 4,357,393,390,309,000,000,000,000 | 31,297,471,658,252,000,000,000,000 | 8,113,955,886,719 |
27 | 6,162,414,764,360 |
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 10^{20} are convergent. Up to 2^{60} (≈ 1.15 . 10^{18}) 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 . 10^{18}.
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.
Back to the general 3x+1 page.