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 brings us to another tree, this time containing all the integers starting at 1. 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.

In this tree no node has more than two other nodes converging on it, so working back is as easy as working forward. The second transformation is to notice that, as all the numbers in the tree are odd we can map them onto the sequence of integers by making the transformation k→(k+1)/2. The first 6 rows in this new tree are shown below. The loop from '1' to '1' has been omitted. The colour scheme is based on modulo three. The forward and reverse transformations are: Forward Reverse x % 4   0: x → 3x / 2   1: x → (3x + 1) / 4   2: x → 3x / 2   3: x → (x + 1) / 4 x % 3   0: x → [4x - 1, 2x / 3]   1: x → [4x - 1, (4x - 1) / 3]   2: x → [4x - 1] The above tree was actually generated using the reverse transformation and shows all the values in the first seven rows. If we construct the tree in the forward direction, using seeds up to 20, we get the tree on the left. Note that 14, which is quite remote from the root corresponds to 27 in the original 3x+1 equation. 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 appears as 15→5 (we ignore the even numbers so 10 becomes 5). With the 4n-1 step included, 53 is followed by 13 (rather than 160), so the glide becomes 15→13, which translates to 8→7 in the 4n-1 tree. Glide Records How do the glide records in this scheme compare with those in 3x+1? The first three columns show glide records in this scheme for numbers up to 30 million. The column on the right shows the first 12 glide records in the 3x+1 scheme. Length Start End 3x+1 equivalent 1 1 1 1 3 2 1 3→1 5 4 2 7→5 42 14 8 27→23 60 352 105 703→157 74 5044 4556 10087→961 97 17828 9802 35655→29405 120 135136 53611 270271→2513 123 181172 53906 362343→161717 --- --- --- 381727→161717 --- --- --- 626331→597017 131 333688 141365 --- 133 513716 206580 1027431→619739 170 563008 261699 1126015→98137 175 4044032 2143577   213 6710836 6167584   217 13358336 8740139   228 28462478 13257640

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.