The Collatz Conjecture

Contents

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

Introduction

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: Show

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:

Show Create Table

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. Show   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.

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.

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

Show

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

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.