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{IMP}2^[12]-3^6=(2^6-3^3)*(2^6+3^3) ≡ 3367=37*91
m=4, n=2{IMP}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
||n||m||K||A‐List||3x+1 Loop| |1|1|-1|[1]|-1, -2, -1, …| |1|2|1|[2]|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.
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. There are a number of dispay options that can be selected from the drop down list below the image. The default one shows all the loops generated by m and n, sortted by the seed values (displayed in cyan). The "circle" view shows all the values aranged around a circle, moving clockwise. 0 and Smax are at the top. In all views the smallest value in each loop (the seed) is coloured cyan and the largest is red, all the others are white. The lines join the points in each loop.
Display:
Value distribution
This next widgit allows you to explore how the values of K, S¬[min], S¬[max], and the largest seed vary with m and n. It charts values for 1{LT}n{LT}33 and 1{LT}m{LT}53, with the constraint that log(3)/log(2){LT}(m/n){LE}2 The range of ''m and 'n' is limited by the precission of the built in 64 bit javascript numbers, where MAX_SAFE_INTEGER=2^[53]-1=9007199254740991.
show: , Scale:
Currently showing:
You will notice the we only plot a narrow wedge, this is the band where values that identify loops in 3x+1 could be found. In the top right, where m{GT}2n, all values will be less than in 0, and in the bottom left region all values would be negative. This is the region where the 2 loops involving negative values, described above, were found. For most charts, most of the region will be white because the range of values is very large, with the very largest reducing the others to insignificance. For instance, K¬[max]~=4.5*10^[15]. Even using logarithms doesn't help much.
To constrain the search for loops we can look at the "MaxSeed/K" chart. For a given value of 'n' this is the largest odd number we need to test to rule out a loop in 3x+1 containing 'n' odd values. Here we can see that the largest value for any 'n' less than 33 is 281, so to rule out any loop with up to 32 odd members we only need to test the integers up to this value. As much larger numbers than this have already been tested, we are going to have to expand our range of 'n' values somewhat. This next table shows the values that contribute to calculating the seed values.
Choose an offset from m¬0(n), the smallest 'm' value that gives a positive solution for a given 'n':
Notice how when m=2n, MaxSeed/K=1. This generates a loop with n odd members and 2n even ones, but in every case this is just the basic [1,4,2] loop repeating n times. S¬[min] is only a function of n, and converges on 3^n from below. Once we move away from the offset equals 0 the seed/K values become very small. That might change for very large n values, below we'll explore this in more detail.
Larger n values
This graph will display the currently selected attribute from the "value distribution" for a fixed the offset from m¬0(n) up to a specified 'n' vales. Choose the n value and select "Show".
Nmax :
Click "Show" to view graph
Anchoring A‐Lists in the 3x+1 tree
It seems reasonable to assume that any finite length A‐List will generate a sequence somewhere in the 3x+1 tree, and if it generates one sequence it will generate an infinite number. On the generic value page we show that such lists can be show to start with a value 2^m*k+b¬0 and pass through a sequence of values 3^j*2^i*k+b¬l until they reach 2*3^n*k+b¬l, m>=i>=1, n>=j>=0 and m+n+1>=l>=0, where n is the length of the A_List and m the sum of the members.
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)).
{h}n | {h}m | {h}A‐List | {h}K | {h}S | {h}S/K {h} 2 | 4 | [2,2] |{tar} 7 |{tar} 7 |{tar} 1.000 {h} 3 | 5 | [1,2,2] |{tar} 5 |{tar} 23 |{tar} 4.600 {h} 4 | 7 | [1,2,2,2] |{tar} 47 |{tar} 101 |{tar} 2.149 {h} 5 | 8 | [1,2,1,2,2] |{tar} 13 |{tar} 319 |{tar} 24.538 {h} 6 | 10 | [1,2,2,1,2,2] |{tar} 295 |{tar} 1357 |{tar} 4.600 {h} 7 | 12 | [1,2,2,1,2,2,1] |{tar} 1909 |{tar} 5095 |{tar} 2.669 {h} 8 | 13 | [1,2,1,2,2,1,2,2] |{tar} 1631 |{tar} 14501 |{tar} 8.891 {h} 9 | 15 | [1,2,2,1,2,2,1,2,2] |{tar} 13085 |{tar} 60191 |{tar} 4.600 {h} 10 | 16 | [1,2,1,2,2,1,2,1,2,2] |{tar} 6487 |{tar} 159181 |{tar} 24.538 {h} 11 | 18 | [1,2,1,2,2,1,2,2,1,2,2] |{tar} 84997 |{tar} 579943 |{tar} 6.823 {h} 12 | 20 | [1,2,2,1,2,2,1,2,2,1,2,2] |{tar} 517135 |{tar} 2378821 |{tar} 4.600
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).
{h}n |{h} m |{h} seed/K |{h} m/n |{h} m/n - log(3)/log(2) {h} 2 |{tar} 4 |{tar} 1.000 | 2.000 | 0.415037 {h} 3 |{tar} 5 |{tar} 4.600 | 1.667 | 0.081704 {h} 5 |{tar} 8 |{tar} 24.538 | 1.600 | 0.015037 {h} 17 |{tar} 27 |{tar} 108.012 | 1.588 | 0.003273 {h} 29 |{tar} 46 |{tar} 281.944 | 1.586 | 0.001244 {h} 41 |{tar} 65 |{tar} 867.140 | 1.585 | 0.000403 {h} 94 |{tar} 149 |{tar} 2419.681 | 1.585 | 0.000144 {h} 147 |{tar} 233 |{tar} 4862.054 | 1.585 | 0.000072 {h} 200 |{tar} 317 |{tar} 9266.540 | 1.585 | 0.000037 {h} 253 |{tar} 401 |{tar} 19584.905 | 1.585 | 0.000018 {h} 306 |{tar} 485 |{tar} 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.