On the Analysis page we saw that the members of the n-cycles in a 3x+K system, where K = 2m−3n, can be generated from sets of 'n' integers [a1, a2, ..., an], where 'm' = ∑ai and all ai≥1.
I'm calling these lists "a-lists".
The set of values generated by rotating the members of the a-list [s1, s2, ..., sn, s1] forms a loop in 3x+K. I'm calling the smallest member of this set the "Loop Seed".
Try it, choose n ≥ 1 and m ≥ n (Limit will restrict the numner of lists created). N: M: Limit:
If you tried the a-list generator in the previous section you will notice that each list is associated with a value. These values are calculated using the equation
This is implemented the function T3A1.AListToValue also in t3a1.js.
Another way to generate a-lists from the 'm' and 'n' values us to use the beads in boxes analogy. If you distrubute the 'm' beads among the 'n' boxes with at least one bead in each box you will have an a-list. You can see how this works it using the boxes below. We start with one bead in each box and then place all the leftovers in the box on the right. If you click on a box it will move one bead from that box to the box one to the left.
Boxes (n): Beads (m):
Every time you move a bead the display above updates to shows the list you have generated along with the corresponding 'S' value. Below that I show the loop that this 'S' value generates in the 3x + K system. You will notice that as you move the beads to the left the 'S' value always gets larger. So we can conclude that the list with the largest 'S' value is the one generated by [m−n+1, …, 1, 1] and that the starting list, [1, 1, …, m−n+1], represents the smallest 'S' that forms a loop with the selected 'm' and 'n' values.
Another interesting consequence is that as lists [m−n+1, …, 1, 1] and [1, 1, …, m−n+1] are rotations of each other the largest and smallest values will appear in the same loop, and will be adjacent.
The controls above will only allow you to explore one of the possible paths from the smallest 'S' value to the largest, whichever path you follow you will always move from smaller to larger values. All paths are the same length, involving m−n steps.
If you combine all the routes you can generate a directed graph (strictly a DAG or directed acyclic graph) all the a-lists for a given (m,n) pair. You canuse these controls to generate one of these graphs. The combol box allows you to switch between three modes, the "a-lists", the 'S' values and the ratio of S/K. This last value is interesting when in a later section we use the "a-lists" to constrain the possibilities of finding loops in 3x + 1. I haven't limited the range of values you can input, but you will find that 'm' values bigger than 12 become impractical.
Boxes (n): Beads (m): Show: Colour mode:
The previous section shows how generate a set of a-lists for a given pair of 'm' and 'n' values. Each a-list generates a single seed. The set of seeds generated by rotating an a-list form a loop in the 3x + K system. If we could find a seed value that is a multiple of K we we would identify a a loop in the 3x + 1 system that contains 'm' even values and 'n' odd values.
The controls in the previous section allow you to experiment with loops and seeds for some small values of 'm' and 'n'. All loops will contain a smallest value, and by using the colour options you can see that the smallest values in each loop are all near the top of the diagram. For a given (m,n) pair we can work out the range of possible seed values
Smin ≤ S ≤ Smax
relatively easily. We can then use the values Smin ∕ K and Smax ∕ K to constrain the range of x values that could form a loop containing 'm' even values and 'n' odd values in 3x+1. This quite quickly leads to the observation that when m ≥ 2n all potential x values are less than are equal to one, so there can be no loops with twice as many (or more) even values as odd ones.
An even stronger constraint can be on the locations of loops can be obtained by focusing on the smallest member of each loop (the "loop seed"), which will be one of the green values in the above diagram (when you choose "Loop Seeds" as the colour mode). As you search through the 'm' and 'n' values you can see that the largest loop seed value grows much more slowly than the largest loop value, as we will see in the Largest Loop Seeds section. You can also observe this effect in the circle drawing tool below.
This divides a circle into a set of points, starting at 0 and moving around to Smax. 0 and Smax are both at the top. All the 'S' values generated by a (m,n) pair are plotted around the circumferance. The smallest value in each loop is coliured green and the largest is red, all the others are white. The lines join the points in each loop.
Boxes (n): Beads (m):
The largest loop seed for a given pair (m,n) determines the range of values that need to be searched to find or eliminate the possibility of a loop in 3x+1. For instance, the largest loop seed in (7,4) is 101. As K is 47, the largest odd number that could form a loop with seven even values and 4 odd ones in 3x+1 must be less than 101∕47. As 101∕47 is about 2.14m the only value we need test is one. This does form a loop, but not a (7,4) one.
Which tries to spread the extra m-n 'beads' as uniformly as possible. It is based on Bresenham's Line Algorithm which is used to draw lines on pixelated devices like a computer screen. The algorithm above is equivalent to drawing a line from (1,1) to (n,m). Here are some examples. The 'm' values are chosen to give the smallest positive K values for a given 'n' (m = ceil(n×log(3)/log(2)).
The largest ratio (seed/K) in this list appears at (5,8), but the same ratio reappears in (10,16) and (15,24). This is no coincidence, as the balanced list for (10,16) is [1,2,1,2,2,1,2,1,2,2]. This is the same cycle as generated by (5,8) only repeated twice.
The next table looks for records in seed/K as we increase 'n', it runs up to about 500. It also shows how close m/n is getting to log(3)/log(2).
n m seed/K m/n m/n - log(3)/log(2) 2 4 1.000 2.000 0.415037 3 5 4.600 1.667 0.081704 5 8 24.538 1.600 0.015037 17 27 108.012 1.588 0.003273 29 46 281.944 1.586 0.001244 41 65 867.140 1.585 0.000403 94 149 2419.681 1.585 0.000144 147 233 4862.054 1.585 0.000072 200 317 9266.540 1.585 0.000037 253 401 19584.905 1.585 0.000018 306 485 72058.065 1.585 0.000005
The first ratio greater than 24.538, which we found at n = 5, is 108.012 at n = 17. This tells us that to eliminate the possibility of a loop with 17 or fewer odd numbers we have to test seeds up to 107 (the largest odd number less than 108.012). To eliminate loops with fewer than 307 odd members we only need to search up to 72057.
Notice how new records correspond to cases where m/n is very close to log(3)/log(2). This is because in these cases K is atypically small. The values either side of n = 306 are shown in the next table.
(a) (b) a x b n m seed/K m/n m/n - log(3)/log(2) 304 482 615.073 1.586 0.000564 0.3467876 305 484 180.521 1.587 0.001923 0.3470956 306 485 72058.065 1.585 0.000005 0.3472867 307 487 255.704 1.586 0.001357 0.3469187 308 489 128.512 1.588 0.002700 0.3469625
I've added an extra column, "seed×(m/n − log(3)/log(2))". Notice that the values in this column are all close to 0.347. You can use the controls in the previous section to try some other values. For instance, for 'n' values around 13,000 we get:
(a) (b) a x b n m seed/K m/n m/n - log(3)/log(2) 13000 20605 9234.977 1.585 0.000037499 0.3463050 13001 20607 4997.281 1.585 0.000069420 0.3469108 13002 20608 14202.647 1.585 0.000024424 0.3468907
Note: The above interactive section will calculate numbers of this magniture but it isn't very quick. The value of S/K provodes a constraint on where loops might be in the 3x+1 system, for there to actually be a loop, S/K needs to be an integer. From the above experiments we can find a rough estimate of S/K just from the values of 'm' and 'n';
S/K ~= 0.347/(m/n - log(3)/log(2))
Given that most small numbers have beed tested we probably need to start looking for seed values greater than 1016, which requires
m/n - log(3)/log(2) < 3.47×10-17
This gives us a way to constrain the smallest cycle that might appear in 3x+1, but doesn't really say anything about the smallest value, as there are an infinite number of a-lists and K values that will have ratios in any range we care to mention. What appears to be missing is seed values that are exact multiples of K. Whether there is some fundamental reason why these values are never multiples of K or it is just a statisticaly unlikely I don't know.
The fact that these largest seeds increase so slowly relative to K is what allows us to put major constraints on where any loops may be found in 3x+1. There is more about log(3)/log(2) on its own page.
If we assume that the relationship between seed/K and m/n − log(3)/log(2) converges around 0.36 and that all numbers up to somewhere in the region of 1016 have been tested, then any loop in 3x+1 requires m/n − log(3)/log(2) to be less than 3.6×-15.
(c) John Whitehouse 2011 - 2017