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 N₀ be the lowest element of a 3x+1 cycle in positive integers of cycle length k. Furthermore, let p_j / q_j be a convergent with j > 4 of the expansion of the continued fraction of ln(3) / ln(2). Then k > (3/2) * min ( q_j , 2 * N₀ / (q_j + q_j+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).

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.

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 q₆ = 41. The factor 2 * N₀ / (q_j + q_j+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 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₆ = 2 * N₀ / (q₆ + q₇) 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₀ / (q₇ + q₈) 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²⁰ are convergent. Up to 2⁶⁰ (≈ 1.15 . 10¹⁸) 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¹⁸.

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.

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 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.