This table lists run lengths and the smallest corresponding
Circularity In The Collatz Sequence
Bradley Berg December 30, 2022
Updated: June 17, 2025
Copyright 2025, Bradley Berg. All rights are reserved.
If a run of the Collatz sequence repeats a value then it will cycle indefinitey. Should such a cycle exist a run that starts with any value in the cycle will always loop back to itself.
The definition of the sequence used here uses only odd steps. In this form Ei is the number of Even steps in the term i. Consequently Ei is also the number of trailing zeros in the numerator and is always one or more.
N0 = Seed
Ni * 3 + 1
Ni+1 = ----------
2^Ei
This paper uses the algebraic expansion of the Collatz sequence from Berg[1].
Seed * 3^L + DL
Ni = ---------------
2^Ki
L
where: Di = ∑ 3^(L-i) * 2^Ki-1
i=1
L is the number of odd transitions.
Ki is the number of even transitions up to step i.
For a run of length L, the total number of even transitions, KL, is denoted as an unsubscripted letter K. The formula below gives the minimum value when a run goes below the horizon. It is also the width in bits of the 3^L term or ord( 3^L ). The actual value can be larger when there are a few additional even steps needed to reach the next odd value.
K = KL >= ceiling[L * log2(3)]
We will also be using the bounds derived for DL:
3^L - 2^L <= DL < L * 3^(L-1)
A cycle is formed when a run reaches a value that is the same as the Seed. Let L be the number of steps taken to reach parity; which gives the cycle length. Substituting Seed for NL we can rewite the algebraic expansion to derive an expression for the Seed.
Seed * 3^L + DL
NL = ---------------
2^K
Seed * 2^K = Seed * 3^L + DL
Seed * (2^K - 3^L) = DL
DL
Seed = ---------
2^K - 3^L
While there are no examples of non-trivial cycles,
this same algebra can be applied to other similar sequences to find cycles.
Appendix A has examples of cycles in the
To place an upper bound on candidate Seeds producing a cycle we can subtite the maximum value of DL. Any Seeds above this bound will not lead to a cycle. It can quickly be approximated using logarithms.
Dmax L * 3^(L-1)
Seed <= --------- = ------------ = 2^{ log2(L) + [L-1]*log2(3) - log2(2^K - 3^L) }
2^K - 3^L 2^K - 3^L
The following table lists, by increasing numbers of leading one bits, the lowest corresponding power of three. The exponent in the 3^L term is the same as the run length. The maximum candidate Seed was precisely calculated using large integer arithmentic. However, the last 6 values (with decimal exponents) are approximate.
Lead Lowest Exponent for K >= Maximum Ones 3^Exponent with Ones ceiling(3^Exponent) Candidate Seed 1 0 1 1 2 3 5 5 3 10 16 30 4 5 8 31 5 29 46 381 6 41 65 1_185 7 147 233 6_700 8 253 401 27_071 9 306 485 99_729 10 1_636 2_593 583_014 11 8_951 14_187 6_559_828 12 12_276 19_457 17_302_830 13 14_271 22_619 45_086_468 14 31_202 49_454 285_812_386 15 15_601 24_727 285_814_986 16 47_468 75_235 1_447_674_321 17 158_670 251_486 7_216_076_047 18 79_335 125_743 7_216_089_270 19 2_858_055 4_529_910 984_572_334_110 20 1_524_296 2_415_952 984_572_556_883 21 762_148 1_207_976 984_572_684_000 22 381_074 603_988 984_572_747_479 23 190_537 301_994 984_572_779_218 24 32_343_822 51_263_745 294_401_817_722_590 25 21_562_548 34_175_830 294_401_819_242_984 26 10_781_274 17_087_915 294_401_822_283_771 27 118_212_940 187_363_077 7_488_744_334_928_739 28 343_857_546 545_001_316 32_030_557_428_155_608 29 171_928_773 272_500_658 32_030_556_104_819_832 30 1_987_866_895 3_150_694_485 1_252_079_112_168_798_720 31 1_192_720_137 1_890_416_691 1_252_079_526_003_966_464 32 795_146_758 1_260_277_794 1_252_079_319_086_365_440 33 397_573_379 630_138_897 1_252_079_422_545_161_728 34 19_760_456_010 31_319_581_773 216_890_195_207_551_385_6e2 35 13_173_637_340 20_879_721_182 216_890_768_697_793_587_2e2 36 6_586_818_670 10_439_860_591 216_889_908_462_998_912_0e2 37 72_057_431_991 114_208_327_604 4_358_504_283_644_284_8e5 38 412_584_135_936 653_930_383_851 51_015_354_143_722_124_8e5 39 275_056_090_624 435_953_589_234 51_011_037_779_838_918_4e5 40 137_528_045_312 217_976_794_617 51_013_195_916_128_128_0e5 41 3_149_971_404_836 4_992_586_555_009 248_421_187_229_626_419_2e6 42 4_656_193_084_598 7_379_891_435_205 <<< TBD >>> three.power.shift@48: Count= 314_83395_10636 Shift=4990000001024 three.power.shift@57: Exponent= 314_99714_04836 Shift= 499_25864_91904 Three`S smax2@48: L=3149971404836 K=4992586555009 Delta=0.49926e13 Dmax=0.49926e13 Shift smax2@49: Smax=0.810390625000000000e 2 S=2.484211872296264192e 24
The main thing to notice is that the maximum candidate Seeds are far smaller than any actual Seeds required producing the corresponding run lengths. With 27 leading ones the smallest exponent (run length) is 118_212_940, but the maximum Seed allows only 53 bits. The maximum run length for any Seed up through 53 bits is only 559. With such an extreme difference in run lengths this data is compelling evidence that cycles are not going to be possible.
This work confirms the contention by Eliahou[2] that "that the inverse proportion of odd elements in a cycle is very close to log2,(3)". It also verifies his calculation that there cycles must have at least 17_087_915 even steps. His paper counts even transitions in the length. The length derived is the value of K corresponding to 3^10_781_274 which has 26 leading one bits.
Here the required loop length is extended to a minimum of 72_057_431_991 odd steps. David Barina[1] showed all runs up to 2^68 terminate and do not loop. For a power of three this exponent has 37 leading one bits and is the first candidate to have a maximum Seed wider than 68 bits. Any larger candidate cycle lengths will need at least 37 leading one bits.
In this section bounds on candidate Seeds for cycles are refined
and then compared to actual Seeds needed for run lengths.
The upper bound on candidates is simplified and is used to place a
constant bound on
The simplified formula is applied to the lowest known Seeds that produce run lengths through 470. The relationship between the run lengths and Seeds is determined.
A simplified formula can be derived from the constraint on candidate Seeds. The formula depends on the number of leading one bits in 3^Length. The closer 3^L is to 2^K the denominator gets smaller and the maximum Seed gets larger. The number of leading ones in the binary representation of 3^L becomes a metric for closeness. For each additional leading on the denominator (2^K - 3^L) gets twice as small.
L * 3^[L-1]
Seedmax = ------------
2^K - 3^L
It's easiest to see how this works with an example using binary arithmetic. In this case 3^L has 6 leading one bits (L = 41), a zero bit, and 10 trailing bits. The 10 trailing bits are unknown except that the low order bit is a one. The range of possible values for the difference is then 1025 to 2047.
1000000_0_0000000000 1000000_0_0000000000 2^K - 111111_0_1111111111 - 111111_0_0000000001 - 3^L = [111111 | 0 | xxxxxxxxx1] -------------------- -------------------- 1025 = 1_0000000001 2047 = 1_1111111111
The range of
2^[K-Ones-1] < 2^K - 3^L < 2^[K-Ones]
The lower bound of the range can be used to determine the maximum candidate Seed for a given loop length. From the formula for Seedmax We can derive an inequality by substituting the lower bound as follows.
Dmax L * 3^[L-1]
Seedmax = ---------- = -----------
2^K - 3^L 2^K - 3^L
3 * Seedmax 3^L 2^K 2^K > 3^L
----------- = --------- < ------------
L 2^K - 3^L 2^[K-Ones-1] 2^K - 3^L > 2^[K-Ones-1]
3^L
--------- < 2^[Ones+1]
2^K - 3^L
3 * Seedmax 3^L
-------- = --------- <= 2^[Ones+1] - 1 Seedmax <= (L/3) * (2^[Ones+1] - 1)
L 2^K - 3^L
Runs were computed for lengths up to 1 billion to verify the simplified
constraint. The table has examples of Seed limits for the first ten counts of
leading ones in 3^L. Runs were found that have the highest ratio of:
You can't help but notice that some of the lengths are relatvely short.
In these cases the ratio peaked early in those runs.
Being simpler the revised formula is slightly less restrictive than the previous bound,
but is easier to work with and calculate.
Seedmax / Length Ratio of Dmax / (2^K - 3^L) to the Closest Length
Closest Length Smallest (2^K - 3^L) found amongst many runs with the number of Ones
K Value of K for the Closest Length
Dmax / (2^K - 3^L) Maximum candidate Seed where Dmax = L * 3^[L-1]
(L/3) * (2^[Ones+1]-1) Simplified maximum candidate Seed
Seedmax <= L/3 * (2^[Ones+1]-1) Seedmax / Closest K Dmax / (L/3) *
Length Length 2^K - 3^L (2^[Ones+1]-1)
Ones=1 Smax <= 3/3 * L 0.99999 190_538 301_996 190_537 190_538
Ones=2 Smax <= 7/3 * L 2.33326 172_874 273_999 403_360 403_372
Ones=3 Smax <= 15/3 * L 4.99993 175_953 278_879 879_753 879_765
Ones=4 Smax <= 31/3 * L 10.33246 214_959 340_702 2_221_056 2_221_243
Ones=5 Smax <= 63/3 * L 20.99511 172_876 274_002 3_629_550 3_630_396
Ones=6 Smax <= 127/3 * L 42.33281 134_571 213_290 5_696_768 5_696_839
Ones=7 Smax <= 255/3 * L 84.99022 3_884 6_156 330_102 330_140
Ones=8 Smax <= 511/3 * L 170.14730 1_942 3_078 330_426 330_787
Ones=9 Smax <= 1023/3 * L 340.46035 971 1_539 330_587 331_111
Ones=10 Smax <= 2047/3 * L 678.54736 40_153 63_641 27_245_712 27_397_730
When there is only a single leading one bit, any candidate Seed would have to be less than the run length. Since we know that all 68 bit Seeds terminate, if 3^L has one lead bit then no loop shorter than 2^68 Odd steps exists. This covers half of the possible runs.
The simplified constraints are linear with respect to the run length
for a given number of leading ones. The maximum candidate
This table lists run lengths and the smallest corresponding
Trendline for the log2( Seed / L ) 0.0798 * L + 4.7621 Largest known variance for a Seed 1_00893_22492_96231 @ L = 559 Estimate for log2( Seed / L ) at 559 49.37030 Actual value of log2( Seed / L ) 40.71505 Lower bound on all known Seeds 0.0673 * 1.05687^L
In this range the largest number of leading ones is 9 in 3^306.
The smallest actual Seed for a run length of 306 is 33_980_539_439 and
The maximum bound on DL can be tightened further by considering only the smallest Seed that produces a given run length. Reasoning that longer runs are sustained by front loading them with more odd steps and fewer even steps; DL should get smaller. After examining a few long runs it became apparent that this was the case.
The smallest Seed was determined for runs of lengths up thru 470. The value of DL was calculated for runs starting with each of these small Seeds. DL gets large quickly so we'll plot the log2 of DL instead. The graph of the run length in log2(D) scale is remarkably linear with only a small amount jitter.
Since the DL term encapsulates the hailstone effect combined with Seeds having chaotic values, you'd expect the result to be highly irregular. Instead they fall neatly along the line:
log2(D) = log2(3)*L + 1.6668 Dest = 3.175*3^L Dmin = 3^L <= D <= 13 * 3^L = Dmax
This is not as unreasonable as it might seem. Consider that when the run length is increased by 1 a new term, 3^(L-1)*2^K, is added to the front of the sum for DL. Seeds are odd so this first step in a run is always: (3*Seed + 1) / 2^1
Since the terms of the sum are within an order of magnitude of each other the sum is roughly tripled and the jitter remains small. As run lengths get larger the number of terms increase by the same amount further averaging out the result. Consequently as the length increases DL is about three times larger with an overall average of three.
Using the value of Dmax for small Seeds an upper bound on candidate Seeds to cycle is:
Smax = 13 * 3^L / (2^K - 3^L) = 13 / (2^K / 3^L - 1)
Run Smallest Actual log2 Ones Loop Smax/L
Length Seed/L log2(DL) (Dmax) Smax
50 21 80.593 82.944 1 19 0.380
100 6081 159.859 162.192 1 31 0.310
150 309037 239.554 241.440 2 67 0.447
200 1859356 318.844 320.689 7 2494 12.470
250 7205950 398.643 399.937 1 19 0.076
300 3545471941 478.148 479.185 1 31 0.103
350 11482339350 556.952 558.433 2 65 0.186
400 544990735650 635.531 637.681 6 1244 3.110
450 1125704645042 716.379 716.929 1 19 0.042
13 / (2^K / 3^L - 1) < 0.0673 * 1.05687^L
2^[K-Ones-1] < 2^K - 3^L
Dmax = 13 * 3^L
Smax = 13 * 3^L / (2^K - 3^L) < 13 * 3^L / 2^[K-Ones-1]
< 13 * 2^[Ones + 1] * 3^L/2^K
< 26 * 2^Ones
Ones 26 * 2^Ones
1 52
2 104
3 208
:
50 29_27339_75779_08224
100 3.2959e31
150 3.7108e46
200 4.1780e61
221 8.7620e67
250 4.7041e76
The
If we look at the ratio, N/S, for a run we see it is close to
chart N/S and 3^L/2^K for smalls????
Let N/S = 3^L/2^K + E
For a Run:
N * 2^K = S * 3^L + D
2^K * N/S = 3^L + D/S
2^K * (3^L/2^K + E) = 3^L + D/S
3^L + 2^K * E = 3^L + D/S
2^K * E = D/S
2^K is big and E is small and their product is chaotic. D/S is positive so E also has to be positive.
For a a Loop: N = S
S * 2^K = S * 3^L + D
D = S * (2^K - 3^L)
2^K = 3^L + D/S
2^K * (3^L/2^K + E) = 3^L + D/S
3^L + 2^K * E = 3^L + D/S
2^K * E = D/S = 2^K - 3^L
E = (2^K - 3^L) / 2^K = 1 - 3^L/2^K
1/2 < E < 1
For a given loop length E is a constant between 1/2 and 1. This is much larger than E for actual runs.
Chart E for small runs and E for a loop.
We need to show that E < 1/2 in runs; especially as ones get bigger.
For a run:
2^K * E = D/S
E = D / (S * 2^K)
For a loop:
S * (2^K - 3^L) = D
2^K - 3^L = D / S = e * 2^K
e = 1 - 3^L / 2^K
Bounds were derived that are useful for understanding loops in the Collatz conjecture.
Calculations using these constraints show there are no loops with fewer than 6_586_818_670 odd elements. The constraints are consistent with observable behavior. As such they help explain what we are seeing. In turn this makes the constraints easy for others to validate or to find a counter example should something be mistaken.
We've shown that the smallest Seeds for long run lengths are limited to a small constant value. This makes a loop with a large Seed impossible.
[1] Berg, Bradley (2025). "Algebraic Expansion Of The Collatz Sequence". Preprint.
[2] Barina, David (2020). "Convergence verification of the Collatz problem".
The Journal of Supercomputing. 77 (3):
[3] Eliahou, Shalom (1991). "The 3x+1 problem: new lower bounds on
nontrivial cycle lengths".
Discrete Mathematics 118 (1993)
To see how the loop constraints can be met in a loop we look to the 3*n-1 variation of the Collatz series. In addition to terminating at one this version has two small circularities.
N is Even: N' = N / 2
N is Odd: N' = (3 * N - 1) / 2
Seed Values
5 14, 7, 20, 10, 5, ...
17 50, 25, 74, 37, 110, 55, 164, 82, 41, 122,
61, 182, 91, 272, 136, 68, 34, 17, ...
Next we plug in the values for these cycles into the revised series. Note that in this case the addition in the sequence is flipped to subtraction. This cuases the sign in the D series to flip.
i Ei Ki Ni Di Seed = 5
0 0 0 5 0
1 1 1 7 -1
2 3 4 5 -5
Seed divides D: D2 = -5 = 5 * -1
Close powers: 2^3 = 3^2 + D2 / Seed
8 = 9 - 1
i Ei Ki Ni Di Seed = 17
0 0 0 17 0
1 1 1 25 -1
2 1 2 37 -5
3 1 3 55 -19
4 2 5 41 -65
5 1 6 61 -227
6 1 7 91 -745
7 4 11 17 -2363
Seed divides D: D7 = -2363 = 17 * -139
Close powers: 2^11 = 3^7 + D7 / Seed
2048 = 2187 - 139
There are also small loops in varient sequences where odds transition to 3n+C; where C is a positive odd constant and not a multiple of 3. In this case the loop constraints are revised as follows.
Seed * C * 2^KL = Seed * 3^L + C * DL
2^KL = 3^L + C * DL / Seed
3*N+19: Seed = 5 C = 19 Loop = {5, 17, 35, 31, 7}
N K D
5 0 0
17 1 1
35 2 5
31 4 19 5 * 2^11 = 10240 = 5 * 3^5 + 475
7 8 65
5 11 475 2^11 = 3^5 + 19 * 475 / 5 = 2048
Using the equality, here are some loops for C under 100:
3*N+C 2^K = 3^L + C*DL / Seed Loop values
3*N+ 5: 2^27 = 3^17+5*189900931/187 187 283 427 643 967 1453 1091 1639 2461 1847 2773 2081 781 587 883 1327 1993
3*N+19: 2^11 = 3^5 +19*475/5 5 17 35 31 7
3*N+23: 2^5 = 3^2 +23*7/7 7 11
3*N+25: 2^27 = 3^17+25*189900931/935 935 1415 2135 3215 4835 7265 5455 8195 12305 9235 13865 10405 3905 2935 4415 6635 9965
3*N+25: 2^27 = 3^17+25*352383011/1735 1735 2615 3935 5915 8885 3335 5015 7535 11315 16985 12745 9565 1795 2705 2035 3065 2305
3*N+29: 2^17 = 3^9 +29*42251/11 11 31 61 53 47 85 71 121 49
3*N+29: 2^65 = 3^41+29*55258418497115015011/3811 3811 5731 8611 12931 19411 29131 43711 65581 49193 18451 27691 41551 62341
46763 70159 105253 78947 118435 177667 266515 399787 599695 899557 674675
1012027 1518055 2277097 853915 1280887 1921345 180127 270205 202661 152003
228019 342043 513079 769633 36077 27065 10153
3*N+35: 2^8 = 3^4 +35*85/17 17 43 41 79
3*N+47: 2^7 = 3^4 +47*85/85 85 151 125 211
3*N+49: 2^38 = 3^22+49*124233085375/25 25 31 71 131 221 89 79 143 239 383 599 923 1409 1069 407 635 977 745 571 881 673 517
3*N+53: 2^29 = 3^17+53*792382399/103 103 181 149 125 107 187 307 487 757 581 449 175 289 115 199 325 257
3*N+55: 2^5 = 3^3 +55*19/209 209 341 539
3*N+59: 2^10 = 3^6 +59*665/133 133 229 373 589 913 1399
3*N+65: 2^24 = 3^12+65*4748765/19 19 61 31 79 151 259 421 83 157 67 133 29
3*N+67: 2^30 = 3^16+67*261519653/17 17 59 61 125 221 365 581 905 1391 265 431 85 161 275 223 23
3*N+71: 2^10 = 3^5 +71*341/31 31 41 97 181 307
3*N+79: 2^23 = 3^14+79*12094865/265 265 437 695 541 851 329 533 839 649 1013 1559 1189 1823 1387
3*N+83: 2^12 = 3^7 +83*2507/109 109 205 349 565 889 1375 263
3*N+85: 2^100 = 3^56+85*104351656096075462196663857141/7 7 53 61 67 143 257 107 203 347 563 887 1373 1051 1619 2471 3749 2833
1073 413 331 539 851 1319 2021 1537 587 923 1427 2183 3317 2509 1903
2897 1097 211 359 581 457 91 179 311 509 403 647 1013 781 607 953 23
77 79 161 71 149 133 121
3*N+89: 2^17 = 3^8 +89*23783/17 17 35 97 95 187 325 133 61
3*N+91: 2^12 = 3^6 +91*2183/59 59 67 73 155 139 127
Here are two longer loops with a lengths of 336 and 366:
::::::: 3*N+3365 Seed = 203 1987 4663 8677 7349 6353 2803 5887 10513 4363 8227 ... 10241 4261 4037 3869 3743 7297 3157 3209 2^624 = 3^336 + 3365 * 419979665850796354334819203385016158491711717552630135326 ... 5765655556868486257128575741096209 / 203 ::::::: 3*N+4351 Seed = 245 2543 2995 1667 1169 3929 8069 14279 11797 19871 ... 76733 117275 22261 35567 27763 10955 1163 2^672 = 3^366 + 4351 * 110340281416782247488138207132548013726344301635807480 ... 9389679513583085955741034037736313165 / 245