On the Analysis page we saw that the members of the n-cycles in a 3x+K system, where
can be generated from sets of 'n' integers
[a¬1, a¬2, …, a¬n]
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.
Each A-list can be used to calculate a value, 's', using the equation:
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:
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 ^6. The K value for  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^-3^6=(2^6-3^3)*(2^6+3^3) ≡ 3367=37*91 m=4, n=2 ⇒ 2^-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.
|1||1||-1||||-1, -2, -1, …|
|1||2||1||||1, 4, 2, 1, …|
|2||3||-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.
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.
|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.|
|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.|
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.
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.
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
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.
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 been tested we probably need to start looking for seed values greater than 1016, which requires
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