The 4n-1 Modification

We have seen earlier how the 3x+1 tree can be compressed into a tree containing only odd numbers. This page describes a further modification that retains all the odd numbers but aranges them into a simpler tree where each node has only one or two precursors. This transformation takes two parts. The first is to notice that all the all the predecessors of a number form a series, where each is four times the previous one, plus one. Redirecting the arrows in the tree so that the decent follows this path rather than going directly to the next odd number transforms the tree on the left to the one on the right.

This image shows the first 7 rows of the reverse tree anchored at 1.

The colour scheme has been expanded to colour values of the form 8n+5 in yellow. To constuct the reverse tree we start at the root and then calculate the predecessors using the algorithm

def previous(x):

    if x == 1:
        return [5]

    r = x % 6

    n1 = 4 * x + 1

    if r == 1:
        return [n1, (4 * x - 1) / 3]

    if r == 5:
        return [n1, (2 * x - 1) / 3]
    
    return [n1]

This shows that every value 'x' has a precursor of the forn 4x+1. Values of the form 6x+1 have a precursor (4x-1)/3 and those of the form 6n+5 one of (2x-1)/3. So all values have a yellow precursor and 2/3rds have a red, green or blue one.

So although yellow values only form 25% of the set of integers they will occupy roughly 60% of each row in this tree.

The above algorithm makes 1 a special case as it is is own precursor.

As the yellow squares tend to hog to bottom of the tree the other colours are forced further out. The image on the left shows the smallest tree that contains the odd numbers 0 - 29. It is 49 rows deep and contains only 10 yellow cells out of 59. So it seems that forward trees are disproportionately short of yellow cells while reverse trees have an excess. This property or reverse trees will always be true because of the nature of the reverse algorithm, the forward tree situation might just be by chance.

The images below compares the glide structures calulated using the standard 3x+1 equation and this 4n-1 alternative.

3x+1 Glide Tree

4n-1 Glide Tree

The two trees are different because the (x-1)/4 step interrupts some potential glides, for instance, the 15 glide in 3x+1 looks like [15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10], which translates to 15→5 when we ignore the even numbers. In the 4n-1 scheme 53 is followed by 13 (rather than 160), so the glide becomes 15→13.

To search for loops agorithmically we need to combine a sequence of iteration steps into an equation of the form f(x) = x.

There are three types of iteration step, x→3x/2, x→(3x+1)/4 and x→(x+1)/4. If we convert these to equations we get:

Which gives us two integer solutions, x = 0 and x = 1. For two iterations there are 9 equations:

"f(x) ⊕ g(x)" is equivalent to "f(g(x))".

These equations show that there is a 2-cycle [-2,-3] which is probably the cycle that all negative numbers convege on. The 1-cycle solutions [0, 1/3, 1] are repeated, as solutions to f(x) = 0 will also be solutions to f(x)⊕f(x) = 0.

All the operations in this table are of the form x → (3ⁿ * x + k) / 2^m, so we can simplify the notation by replacing the expressions with 3-tuples (n,k,m). We can then define the operation ⊕ as:

(n1,k1,m1) ⊕ (n2,k2,m2) = (n1+n2, k2*3ⁿ¹ + k1*2^m2, m1+m2)

In this notation the list looks like

Notice the operation isn't commutative, A⊕B ≠ B⊕A. However, if A=(n1,k2,m1), B=(n2, k2, m2) and C=(n3, k3, m3) then

A⊕(B⊕C) = (A⊕B)⊕C = (n1+n2+n2, k1*2^(m2+m3) + k2*2^m3*3ⁿ¹ + k3*3^(n1+n2), m1+m2+m3).

So the operation is associative. To find a loop we need to find a tuple (n,k,m) such that

For potential 3-cycles there are 27 permutations. All the members of a potential loop will have the same m and n values, as these don't depend on the order the tuples are combined. If we label the three atoms A=(1,0,1), B=(1,1,2) and C=(0,1,2) then the n value will be N_A + N_B and m will be 2*(N_B+N_C)+N_A, where N_A is the number of As in the cycle, etc. The 27 potential loop values are showin in the following table, organised into 11 potential loops.

The only combination that produces values greater than one is ABB. When searching for larger loops we can eliminate the cases where all the terms are the same AA...A, BB...B, CC...C as these always lead to x values of [0, 1, 1/3]. We can also eliminate those cases where (2*(N_B+N_C)+N_A)/(N_A+N_B) < log(3)/log(2), as these will be negative. The best place to search for loops is where 2^m is only slightly greater than 3ⁿ, though as 'n' amd 'm' get larger "slightly" is only a relative term. For 4-cycles we can use these two constraints to eliminate loops based on AAAA, AAAB, AABB, BBBB and CCCC.

For any pair of 'm' and 'n' values we need to find values of k such that k /( 2^m - 3ⁿ) is an integer. This is exactly the same problem that we had with the standard approach. The difference here is that the 'm' and 'n' values don't relate directly to the loop size. The standard equation with n=3 and m=5 generates the seeds [19, 31, 49, 23, 37, 29]. To find the corresponding seeds in this scheme we need to locate those potential loops where 2*(N_B+N_C)+N_A = 5 and N_A+N_B = 3. The only possible loops with this constraint are based on ABB and AAAC. These give the potential seed values 14,17,21 and 8,12,18,27. These are different from the values in the classic equation.