Contents

Introduction

On the Analysis page we saw that the members of the n-cycles in a 3x+K system, where

K=2^m-3^n

can be generated from sets of 'n' integers

[a¬1, a¬2, …, a¬n]

where

m=∑a¬i, a¬i≥1

From here on I will be referring to these list of 'a' values as "A-lists". We will explore the relationship between A-lists and potential loops in 3x+1 in the next section.

Lists and loops

Each A-list can be used to calculate a value, 's', using the equation:

s=3^[n-1]+3^[(n-2)]*2^[a1]+3^[(n-3)]*2^[(a1+a2)]+…+3^0*2^[(a1+a2+…+a(n-1))]

If an A-list has 'n' members we can use it to calculate a set of s-values, [s¬1, s¬2, …, s¬n] by rotating the members and recalculating 's'. If we rotate to the left by repeatedly moving the first member to the end, the generated set of s-values will correspond to the odd elements of a cycle in the 3x+K system. The 'a' values determine the number of even steps between each odd one. This is explained in more detail on the algorithmic loops page. Essentially:

s¬[i+1]=(3s¬i+K)/2^[ai]

Dividing by 2^[ai] skips the even values so that we can move straight to the next odd one.

These sets of 's' values will have a smallest member, which I will call the "Loop Seed". If the same seed appears more than once in the list then the loop will factorise into 2 (or more) smaller loops. For instance

[1, 1, 4, 1, 1, 4] → [4277, 8099, 1729, 4277, 8099, 1729]

For a loop to factorise, 'n' and 'm' must have a common factor. Here, n=6, m=12 and K=3367. 6 and 12 are both divisible by 3, so the list factorises to [1,1,4]^2. [1,1,4] has a K value of 37 and generates the loop [47, 89, 19].

When a list factorises like this the K value of the smaller loop is a factor of the K value of the original. Here the larger K (3367) is 91 times the smaller (37). The 's' values are also factors, [4277, 8099, 1729] is 91*[47,89,19]. There is a another 3-member repeated loop, [1,2,3]^2 and a repeated 2 member loop [1,3]^3M. [1,3] has a K value of 7, which is also a factor of 3367.

And, finally, we have [2,2,2,2,2,2], which is [2]^6. The K value for [2] is 2^2-3^1=1, so we have found a loop in 3x+1. Unfortunately it is the classic [1,2,4,1] loop, with one odd member (1) and two even ones (4 and 2).

Generically we can show:

2^[2m]-3^[2n]=(2^m-3^n)*(2^m+3^n)
2^[3m]-3^[3n]=(2^m-3^n)*(2^[2m]+2^m*3^n+3^[2n])
…

Which in our specific case gives

m=6, n=3 ⇒ 2^[12]-3^6=(2^6-3^3)*(2^6+3^3) ≡ 3367=37*91
m=4, n=2 ⇒ 2^[12]-3^6=(2^4-3^2)*(2^8+2^4*3^2+3^4) ≡ 3367=7*481

You can generate the lists above, and others with up to 12 members using the widget below. This simulates distributing 'm' beads among 'n' boxes, with at least one bead in each box. Enter an 'n' value (number of boxes) and an 'm' value (number of beads). It starts with all the spare beads in the rightmost box and you can move them to the left by clicking on the box.

Boxes (n): Beads (m):

This panel shows some attributes of the list you've created using the above boxes.

   

Most of these should be familiar, the interesting ones are 'hcf' and 'S/K'. If hcf (F) is greater than 1 then all the S-valeus will have a common factor with K, so as well as generating a loop in 3x+k, this sequence will also create a loop in 3x+K/F. You can see an example of this with n=6, m=10 which has a 'k' value of 295 and several loops with seeds divisible by 5. There is also a loop with a common factor of 57.

The other interesting value is S/K. If you are lucky enough to find a list such that S¬0 is a multiple of K, that is not in the list below, you will have found a contradiction to the Colatz conjecture.

Known 3x+1 loop generating lists

nmKA-list3x+1 Loop
11-1[1]-1, -2, -1, …
121[2]1, 4, 2, 1, …
23-1[1,2]-7, -20, -10, -5, -14, -7, …

You can see these loops by entering the 'n' and 'm' values into the widgit above. Two of these produce 'k' values of -1, you can translate these to loops in 3x+1 by dividing all the values by -1.

List organisation

The "boxes and beeds" widget above can generate all the possible lists for a given (m,n) pair, but it will only allow you to explore one of the possible routes through the set of possibilities. The graph below shows all the possible routes from the starting list [1,1,1,...,1,m-n-1] to the endpoint [m-n-1, 1,1,1,...,1]. It is generated using the same 'm' and 'n' values as the beads panel.

 

Label Mode: Colour mode:  

The above chart allows you to explore a number of list aspects and, using the colour options, to highligh loops and other elements select a "label mode" and use the arros to cycle through the colour mores.

Label Mode
Minimal Just shows the list structure with no labels.
List Shows the list elements.
Value (s) Shows the 'S' value generated by rotations of the list.
Smin Shows the smallest 'S' value generated by rotations of the list, corresponds to the seed.
Smax Shows the largest 'S' value generated by rotations of the list.
S/K Shows the list's 'S' value divided by (2^m-3^n).
Smax / Smin The ration of the largest and smallest S values generated by rotations of the list.
Smin/K Shows the 'Smin' (seed) value divided by (2^m-3^n). This will give you an idea of the range of 'm' and 'n' values you will need to explore to find exceptions to the Collatz conjecture. You'll see that for the values accessible above all these ratios are very small. If we are going to disprove the conjecture we will need to move to much larger 'm' and 'n' values. We will explore how large later.
HCF (S,K) Shows the highest common factor of S and K. It this is more than one then this list will correspond to cycles in other 3x+k systems where k (2^m-3^n) divided by a factor of the HCF.
Loop Index How the lists are organised into loops. This is clearer if you use the colour controls to highlight loops at the same time.
 
Colour Mode
Min and Max values Highlights the lists that generate the minimum (green) and maximum values (pink) in the cycles.
HCF>1 Highlights the lists where the highest common factor of 's' and 'K' is greater than one.
Loop 'n' Highlights the lists that generate the n'th loop.

Constraints on loops in 3x+1

If you experiment with the "boxes and beeds" controls above you will notice that as you move down the rows that the value of S¬0 increases. You can confirm this by viewing the 'S' values in the graph. As this graph contains all possible lists for the given (n,m) it follows that the list [1,1,1,...,1,m-n-1] generates the smallest 'S' and [m-n-1,1,1,1,...,1] the largest.

This allows you to create a constraint on any loops in 3x+1. If an A-list corresponds to a loop in 3x+1 then the odd members of this loop must fall in the range S¬[min]/K<=x<=S¬[max]/K. For the default values (n,m)=(5,9) this means that any loop can only contain odd values in range 1-7. We already know this list doesn't generate a loop because all the S/K values are fractions, but it does mean that a given (n,m) we can calculate the range S¬[min]/K to S¬[max]/K, and combine this with our knowledge of numbers that have already been tested to identify ranges of 'n' where loops might be found.

Relative S-value sizes

This view shows all the 'S' values generated by the (m,n) pair specified above aranged around a circle, starting with 0 and moving clockwize around to Smax, which, being full circle, is also at the top. The smallest value in each loop (the seed) is coloured green and the largest is red, all the others are white. The lines join the points in each loop.

 

Display:

Generating a-lists

For loops in 3x+K, where K=2^m-3^n we need to choose 'n' a-values, >=1, that add up to 'm'. If we want a positive K we need m>n*log(3)/log(2), and if we are hoping to find a loop in 3x+1 we need m<2*n

Enter m and n values and see the lists generated: (Limit will restrict the number of lists created). N: M: Limit:

   

TODO: Extract the actual loops and look for common factors

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, the numbers run clockwise. 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.

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

nma-listKSS/K
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:

   

Constraints

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 been 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