1. Introduction
  2. The Reverse Tree
  3. The Forward Tree
  4. Glide Structure
  5. Glide Records
  6. Larger View of the Uncondensed Tree
  7. Comparison of the condensed and Uncondensed Trees


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.

In the 3x+1 transform we 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.

The Reverse Tree

In this new tree every node has only one or two precursors, so it is possible to calculate a complete tree for any finite number of iterations. 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 in the "Get4nPredecessors" function in the script attached to this page.

Try it:


Every value 'x' has a predecessors of the forn 4x+1. In addition, values of the form 6n+1 and 6n+5 have a second predecessor, (4x−1)/3 or (2x−1)/3 respectively. So all values have a yellow predecessors and 2/3rds have a red, green or blue one.

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

Because there are only two routes the tree can take at each step we can map the options onto the binary digits 0 and 1. The choice is arbitrary, but I'm choosing to have '0' represent the (2x−1)/3 and (4x−1)/3 options and 1 represent the 4n+1 option. You can see how integers map to values in the 4n+1 tree using these controls:


If you use the table option you will see that most values map to 0.

Forward Tree

The forward calculation is implemented in the "NextOdd4" function of the attached script. We can use this to generate the sequence for any starting number.


If you start with 27 you can generate the longest sequence shown in the image on the left. The branches can be added using the seeds 9, 21 and 25. Combining all these series generates the tree which contains all the odd numbers up to 31. 33, the smallest number missing extends the branch starting at 25, try it in the calculator above.

This tree 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.

Glide Structure

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.

As we saw above thew new equation anchors an infinite sequence of numbers of the form 8n+5 to every other number, so we can condense these out the same was as we did for the even numbers earlier. Now the glide tree looks like this.

Condensed 4n−1 Glide Tree

All the nodes that previously converged on 13 now converge on 3. You can construct your own glides here:


Glide Records

This tabls shows glide records, based on the length, each row in the table shows the longest glide found searching all the starting numbers up to the value in the start column. Length is the number of iterations required to get from "Start" to "End". You can check these using the glide calculator on the observations page.

 Length      Start         End

      2          1 →         1
      3          3 →         1
      5          7 →         3
     42         27 →        15
     60        703 →       209
     74      10087 →      9111
     97      35655 →     19603
    120     270271 →    107221
    123     362343 →    107811
    131     667375 →    282729
    133    1027431 →    413159
    170    1126015 →    523397
    175    8088063 →   4287153
    213   13421671 →  12335167
    217   26716671 →  17480277
    228   56924955 →  26515279
    266   63728127 →  33014059

This second tabls shows the glide records obtained using the condensed algorithm. At least for these first few rows the starting values are the same. The lengths are shorter and some of the end values are smaller because the 8n+5 values have been "condensed" out.

 Length      Start         End

      2          1 →         1
      4          7 →         3
     37         27 →        15
     51        703 →       209
     64      10087 →      9111
     85      35655 →     19603
    103     270271 →      1675
    104     362343 →    107811
    105     401151 →     44759
    110     667375 →    282729
    115    1027431 →    413159
    141    1126015 →    130849
    155    8088063 →   4287153
    182   13421671 →  12335167
    188   26716671 →    273129
    194   56924955 →  26515279
    237   63728127 →  33014059

Larger view of the uncondensed tree

Here is the complete tree extended to 11 rows. I include this to demonstrate excess of yellow cells in the tree. One of the strange properties of infinite sets is that you can have apparant paradoxes like this where although only 25% of the nodes are yellow, any finite fragment of the tree (other than the very smallest) will contain about 60%.

Comparison of the condensed and Uncondensed Trees

These two images compare the uncondensed 4n−1 tree for odd numbers up to 999 with the equivalent condensed version, where the 8n-5 numbers are omitted.

Uncondensed   Condensed

Other pages


(c) John Whitehouse 2011 - 2016