Constraints

The largest loop member can be used to provide a constraint on the smallest possible cycle size. For instance, 82 is the smallest cycle size where the largest possible loop member is more than 1015. As we know that all numbers smaller than 1015 don't form loops we can use this fact to prove that no cycles smaller than 82 exist. This isn't  a very good constraint though as the cycle containing the largest possible loop member will also contain a number of smaller values. In fact by rotating the set of 'a' values we can see that the loop with the largest member also contains the smallest.

We can call the smallest member of a loop its 'seed'. For a given cycle size we can search all the loops and identify the largest seed. In the K= 82 system this value is about 867K, so to eliminate the possibility of 82−cycles in 3x+1 we only need to test values up to 867, which is a lot smaller than 1015. For large loops we can't simply search for the largest seed so we need a method of predicting it, see Largest loop seeds.

We know that for a given pair of 'm' and 'n' values the size of the loop is m+n, 'n' odd values and 'm' even ones. We also know that the range of possible values is constrained by the loop members. The range of loop members increases relatively smoothly with 'n', but the conversion into the 3x+1 system depends on the value K, which behaves less smoothly. If we are going to find any loops in the domain of the integers we can comprehend we will need to look at systems where K is atypically small. These occur when m∕n is close to, but larger than, log(3)∕log(2). On the Integer approximations to log(3)∕log(2)page I identify 'm' and 'n' values where this is the case.

The first few pairs are shown in the following table.
m ∕ n cycle size K Max Loop seed Max(LS) ∕ K
2∕1 3 1 1 1.000
5∕3 8 5 23 4.600
8∕5 13 13 319 24.538
27∕17 44 5077565 548440271 108.012
46∕29 75 1.738e+012 4.901e+014 281.944
65∕41 106 4.204e+017 3.646e+020 867.140
149∕94 243 6.658e+042 1.611e+046 2419.681

The table shows that simply by confirming that there are no loops in 3x+1 seeded by values below 2500 the smallest cycle must contain more than 243 values. Let's try some of the larger values we found:

m ∕ n cycle size K Max Loop seed Max(LS) ∕ K
1539∕971 2510 1.886e+460 4.501e+465 238,670
22619∕14271 36890 1.049e+6805 3.411e+6812 32,525,517
301994∕190537 492531 1.153e+90902 8.194e+90913 710,220,447,737

Our best estimate of log(3)∕log(2), 301994∕190537, leads us to the conclusion that to eliminate the possibility of any loops with 492531 or fewer members we need to test the first 711 billion values. Extending these tests any further is quite tricky, the last row in the table has us comparing numbers with 91 thousand digits.

Other Pages

Boxes and Beads: An alternative view on the search for loops.

Other pages

 

(c) John Whitehouse 2011-2013