Circularity In The Collatz Sequence
Bradley Berg December 30, 2022
Updated: July 4, 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 Collatz 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
We'll also be using the algebraic expansion of the Collatz sequence derived in Berg[1].
Seed * 3^L + Di L
Ni = --------------- where: Di = ∑ 3^(L-i) * 2^Ki-1
2^Ki i=1
L is the number of odd transitions.
Ki is the sum of even transitions up through step i.
D = DL is the final value of Di.
For a run of length L, the total sum of even transitions, KL, is denoted as an unsubscripted letter K. The formula below gives its lower bound as a run goes below the horizon. It is also the width in bits of the 3^L term or order( 3^L ). The actual value can be larger than Ko when there are a few additional even steps needed in the final transition to reach the next odd value.
K = KL >= Ko = ⌈L * log2(3)⌉ = order( 3^L )
We will also apply the bounds derived for D:
3^L - 2^L <= D <= L * 3^(L-1)
A cycle occurs when a run reaches a value that is the same as the Seed.
Let L be the number of steps taken to reach parity; giving the candidate cycle
length. Substituting Seed for NL we can rewite the algebraic
expansion to derive an expression for the Seed.
Note that D is divisible by Seed and
Seed * 3^L + D
NL = --------------
2^K
Seed * 2^K = Seed * 3^L + D
Seed * (2^K - 3^L) = D
D
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 substitute the maximum value of D. Any Seeds above this bound cannot lead to a cycle.
Dmax L * 3^(L-1)
Seed <= --------- = ------------
2^K - 3^L 2^K - 3^L
The closer 3^L is to 2^K the denominator gets smaller and the maximum Seed
allowed to form a loop gets larger. When the binary representation of 3^L has
multiple leading one bits then the difference becomes smaller. The number of
leading ones becomes a metric for closeness; which is denoted as Phi.
For each additional leading one the denominator
For 2^K to be the closest to 3^L the value of K used is it's minimum value:
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 except for the last nine values (with decimal exponents) are approximate.
Lowest Exponent for K >= Maximum
Phi 3^Exponent with Ones ⌈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 839_554_604_110_048_768_0e6
The main thing to notice is that maximum candidate Seeds are far smaller than any actual Seeds required to produce 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.
Observations about leading ones in powers of three confirm the contention by Eliahou[2] that "that the inverse proportion of odd elements in a cycle is very close to log2,(3)". His paper counts even transitions in the length and derives a significant constraint on the term, K. The constaint constants have corresponding powers of three; which are here by correlated.
K = 301_994*a + 17_087_915*b + 85_137_581*c
2^301_994 > 3^190_537 23 leading one bits
2^17_087_915 > 3^10_781_274 26 leading one bits
85_137_581 = 34_175_830 + 51_263_745 - 301_994
2^34_175_830 > 3^21_562_548 25 leading one bits
2^51_263_745 > 3^32_343_822 24 leading one bits
53_715_833 = 21_562_548 + 32_343_822 - 190_537
L = 190_537*a + 10_781_274*b + 53_715_833*c
This modified constraint on L also verifies his calculation that cycles must have at least 17_087_915 even steps. The length derived is the value of K corresponding to 3^10_781_274 which has 26 leading one bits.
The smallest possible length of a cycle can be extended to a minimum of 137_528_045_312 odd steps. Barina[2] shows that all runs up to 2^71 terminate and do not loop. The first power of three wider than 71 bits with 38 leading one bits is 412_584_135_936. Any larger candidate cycle lengths will be a power of 3 with at least 38 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 candidate loop length is simplified so as to be 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 for a maximum Seed can be derived from the constraint on candidate Seeds. The revised formula depends on the number of leading one bits in 3^Length (Phi). For a given value of Phi the new upper bound on Seeds is simplified as the run length times a constant.
L * 3^[L-1]
Seedmax = ------------ <= (L/3) * (2^[Phi+1] - 1)
2^K - 3^L
It's easiest to see how considering the leading one bits works with an
example using binary arithmetic. In this case 3^L has 6 leading one bits
1000000_0_0000000000 1000000_0_0000000000 2^Ko - 111111_0_1111111111 - 111111_0_0000000001 - 3^L = [111111 | 0 | xxxxxxxxx1] -------------------- -------------------- 1025 = 1_0000000001 2047 = 1_1111111111
The example uses Ko = ⌈3^Exponent⌉. In the case where K exceeds Ko the denominator gets twice as large. In turn Seedmax is twice as small so that using Ko is still a valid bound for Seedmax. Using the actual value of K the bound could be improved, but it is not needed in this case.
The range of
2^[K-Phi-1] < 2^K - 3^L 2^[65-6-1] < 2^65 - 3^41 L = 41 and K = 65 #400_0000_0000_0000 < #5d5_e309_84a0_95d5
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-Phi-1] 2^[K-Phi-1] < 2^K - 3^L
3^L
--------- < 2^[Phi+1]
2^K - 3^L
3 * Seedmax 3^L
-------- = --------- <= 2^[Phi+1] - 1 Seedmax <= (L/3) * (2^[Phi+1] - 1)
L 2^K - 3^L
Runs were computed for lengths up to a 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 same value of Phi
K Number of even transitions for the Closest Length
Dmax / (2^K - 3^L) Maximum candidate Seed where Dmax = L * 3^[L-1]
(L/3) * (2^[Phi+1]-1) Simplified maximum candidate Seed
Seedmax <= L/3 * (2^[Phi+1]-1) Seedmax / Closest K Dmax / (L/3) *
Length Length 2^K - 3^L (2^[Phi+1]-1)
Phi=1 Smax <= 3/3 * L 0.99999 190_538 301_996 190_537 190_538
Phi=2 Smax <= 7/3 * L 2.33326 172_874 273_999 403_360 403_372
Phi=3 Smax <= 15/3 * L 4.99993 175_953 278_879 879_753 879_765
Phi=4 Smax <= 31/3 * L 10.33246 214_959 340_702 2_221_056 2_221_243
Phi=5 Smax <= 63/3 * L 20.99511 172_876 274_002 3_629_550 3_630_396
Phi=6 Smax <= 127/3 * L 42.33281 134_571 213_290 5_696_768 5_696_839
Phi=7 Smax <= 255/3 * L 84.99022 3_884 6_156 330_102 330_140
Phi=8 Smax <= 511/3 * L 170.14730 1_942 3_078 330_426 330_787
Phi=9 Smax <= 1023/3 * L 340.46035 971 1_539 330_587 331_111
Phi=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 71 bit Seeds terminate, if 3^L has one lead bit then no loop shorter than 2^71 Odd steps exists. Lengths with one leading one bit covers half of all possible runs.
The simplified constraints are linear with respect to the run length
for a given number of leading ones. The maximum candidate
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; D 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 D was calculated for runs starting with each of these small Seeds. D gets large quickly so we'll plot the log2(D) instead. The graph of the run length in log2(D) scale is remarkably linear with only a small amount jitter.
Since the D 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 next chart makes the jitter visible and shows minimum
and maximum bounds. Values of DL are divided by
For this sample peak jitter occurs at length 275 is 12.958. Mainly it shows that DL is not just closer to the minimum, but has a constant trend line of about 3.175. Also, it significantly diverges from the maximum. For all known values outside the charted range the maximum jitter was 10.96 at a length of 474.
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 Phi Loop Smax/L
Length Seed/L log2(D) (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-Phi-1] < 2^K - 3^L
Dmax = 13 * 3^L
Smax = 13 * 3^L / (2^K - 3^L) < 13 * 3^L / 2^[K-Phi-1]
< 13 * 2^[Phi + 1] * 3^L/2^K
< 26 * 2^Phi
Phi 26 * 2^Phi
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
The trend line for DL is also a straight line and is even closer to 3^L than for Seeds with fewer trailing one bits. When computating Dmin the exponent of 2^Ei is one in all but the last term. Since the low one bits are processed first the leading terms in DL will also have Ei set to one. Consequently DL for Beans is very close to Dmin.
The chart shows that DL / 3^L is very close. For run legths over 1250 it is under 3. As length get larger we can expect more uniform runs to prevent any outliars.
Seed bound is small
2^[K-Phi-1] < 2^K - 3^L
Dmax L * 3^(L-1) 3^(L+1)
Seed <= --------- = ------------ => ---------
2^K - 3^L 2^K - 3^L 2^[K-Phi-1]
Long run length must be a power of 3 with many leading one bits.
The Seed need tp be Beans.
Seed required for a long run is a Bean.
I has at least a third of the legth in ones.
Bean > 2^[L/3]
Bean < 3^(L+1)/2^K - 3^L
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). "Improved verification limit for the convergence of the Collatz conjecture".
The Journal of Supercomputing. 81, 810 (2025).
[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 * D
2^KL = 3^L + C * D / 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*D / 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