A-Lists

On the Analysis page we saw that the members of the n-cycles in a 3x+K system, where K = 2^m−3ⁿ, can be generated from sets of 'n' integers [a₁, a₂, ..., a_n], where ∑a_i = m, a_i≥1.

I'm calling these lists A-Lists.

The set of values generated by rotating the members of the A-List [s₁, s₂, ..., s_n, s₁] forms a loop in 3x+K. I'm calling the smallest member of this set the "Loop Seed".

The script I use to generate A-Lists looks like this. It assumes n ≥ 1 and m ≥ n.

def createALists (m,n):
    """
    Create all lists of n integers, >= 1, that add up to m
    """

    if n == 1:
        return [[m]]

    spare = m - n

    ret = []

    # The first integer can take values in the range 1 to 1 + spare

    for i in range (1+spare):
        a0 = i + 1
        list_set = createALists (m - a0, n-1)
        for l in list_set:
            ret.append ([a0]+l)

    return ret

The loop member generated by an A-List, 'S', is

The code I use to perform this calculation looks like

def calcAListValue(list):
    """
    Generic calculator of S values for arbitrary A-Lists
    """

    l = len (list)

    if l < 1:
        return 0

    if l == 1:
        return 1

    if l == 2:
        return 3 + 2 ** list [0]

    return 3**(l-1) + 2 ** list [0] * calcAListValue(list[1:])

Another way to generate the seeds from a set of A-Lists starts with the beads in boxes analogy.

First place m beads in n boxes, with at least one bead in each box, then take one bead and move it one box to the left. This operation creates a larger 'S' value. The consequence of this is that the A-List that generates the largest loop member is [m−n+1, ...,1, 1, 1], as there are no more possible moves. By working in reverse we can show that the smallest loop member corresponds to [1, 1, 1,...,m−n+1]. Starting with [1,1,...m−1+1] we can generate a graph (strictly a DAG or directed acyclic graph) of all the A-Lists for a given (m,n) pair. Here are the graphs for (5,3), (6,3), (7,3) and (8,3).

The same graphs with the K and A-Values

K = 5	K = 37	K = 101	K = 229

This shows that for a given (m,n) pair we can work out the range of possible seed values - S_min≤S≤S_max - relatively easily. We can then use the values S_min∕K and S_max∕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.

Here we show the first A-List graph for n=4 (K=47). Now we've partitioned the loop members into loops and highlighted the largest (red) and smallest (green) loop members.

And when (m,n) = (8,5), K = 13

This provides a much stronger constraint on the possible location of loops, as all loops must contain a smallest member, which will be one of the green values in the above diagrams. The largest of these "Loop Seeds" is much smaller than the largest loop value, and grows very slowly relative to the largest value, as we will see in the Largest Loop Seeds section.

Applying the 3x+K operation to an A-List rotates the list one place to the left; [a₁, a₂, ..., a_n] → [a₂, ..., a_n, a₁]. If S₁ ≡ [a₁, ...] and S₂ ≡ [a₂, ...], then (3.S₁ + K)∕2^a1 = S₂.

Let's assume that S₁ is a loop seed, the smallest member of a loop in 3x+K. The next member of the loop, S₂, must be greater than S₁, so (3.S₁ + K)∕2^a1 > S₁, which is equivalent to K > (2^a1−3)S₁, so, if a₁ > 1 then S₁∕K ≤ 1.

To find loops in 3x+1, other than the familiar [1,4,2,1], we need loop seeds where S > K; this excludes all potential seeds where the A-List starts with 2 or more, so all "interesting" loop seeds must have an A-List that starts with a 1.

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 following algorithm,

def makeBalancedList (m,n):
    """
    Create the most balanced a-list
    """
    ret = []
    inc = float(m)/float(n)
    val = inc

    for i in range (n):
        ret.append(int(val))
        val = val - int(val) + inc

    return ret

which tries to spread the extra '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.

 n   m   A-List

 2   4   [2, 2]
 3   5   [1, 2, 2]
 4   7   [1, 2, 2, 2]
 5   8   [1, 2, 1, 2, 2]
 6  10   [1, 2, 2, 1, 2, 2]
 7  12   [1, 2, 2, 1, 2, 2, 1]
 8  13   [1, 2, 1, 2, 2, 1, 2, 2]
 9  15   [1, 2, 2, 1, 2, 2, 1, 2, 2]
10  16   [1, 2, 1, 2, 2, 1, 2, 1, 2, 2]
11  18   [1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2]
12  20   [1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2]

This next table shows how the seeds generated by the above lists compare with the K values. The largest seed/K occurs in the (5,8) system 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.

 n   m         K       seed    seed/K 

 2   4         7          7     1
 3   5         5         23     4.6
 4   7        47        101     2.149
 5   8        13        319    24.538
 6  10       295       1357     4.6
 7  12      1909       5095     2.669
 8  13      1631      14501     8.891
 9  15     13085      60191     4.6
10  16      6487     159181    24.538
11  18     84997     579943     6.823
12  20    517135    2378821     4.6
13  21    502829    5805215    11.545
14  23   3605639   21687773     6.015
15  24   2428309   59586967    24.538
16  26  24062143  213933253     8.891

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. We know for instance that all the numbers less that 10¹² have been tested (and probably a lot more by now). This means that to find a loop we need to find examples where the largest seed divided by K is greater than 10¹². If we extend n up to about 500 we find some larger values, but nowhere near 10¹².

   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 

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 look like

   n    m    seed/K      m/n   m/n - log(3)/log(2)

 304  482    615.073   1.586     0.000564 
 305  484    180.521   1.587     0.001923 
 306  485  72058.065   1.585     0.000005 
 307  487    255.704   1.586     0.001357 
 308  489    128.512   1.588     0.002700 

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.