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

Generating a-lists

The attached Javascript file (t3a1.js) contains a function called "T3A1.CreateALists" that can be used to generate all the lists associated with a pair of numbers.

Try it, choose n ≥ 1 and m ≥ n (Limit will restrict the numner of lists created). N: M: Limit:


Converting a-lists to values

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

S = 3n-1 + 3n-2 × 2a1 + 3n-3 × 2a1+a2 + … + 2a1+a2+...+a(n-1)

This is implemented the function T3A1.AListToValue also in t3a1.js.

A-lists and loops

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.

a-list Graphs

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:  


Loop Seeds

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):


Largest Loop Seeds

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.

From the graphs above we can see that all the loops seeds are clustered at the top. We can postulate that this patten continues for larger n values. We can also notice that the largest loop seed has an a-list that has the form of what I call the most balanced list. This is generated using the function T3A1.MakeBalancedList in the associated javascript.

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

2 4 [2,2] 7 7 1
3 5 [1,2,2] 5 23 4.6
4 7 [1,2,2,2] 47 101 2.149
5 8 [1,2,1,2,2] 13 319 24.538
6 10 [1,2,2,1,2,2] 295 1357 4.6
7 12 [1,2,2,1,2,2,1] 1909 5095 2.669
8 13 [1,2,1,2,2,1,2,2] 1631 14501 8.891
9 15 [1,2,2,1,2,2,1,2,2] 13085 60191 4.6
10 16 [1,2,1,2,2,1,2,1,2,2] 6487 159181 24.538
11 18 [1,2,1,2,2,1,2,2,1,2,2] 84997 579943 6.823
12 20 [1,2,2,1,2,2,1,2,2,1,2,2] 517135 2378821 4.6

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.

You can use the controls below to examine seeds generated by other 'm' and 'n' values:

N: M:



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.

Other pages


(c) John Whitehouse 2011 - 2017