Introduction

This section of the site discusses the discoveries that can be made simply by iterating the equation and noting the results.

  1. Introduction
  2. The full tree
  3. The odd tree
  4. The glide tree
  5. Residues
  6. Working Backwards
  7. The 5x+1 system
  8. 3x + 1 Index

The full tree

Although we stated at the start of the site we would be concentrating on the odd numbers, let us first look at the whole tree. This can be constructed by combining all the individual sequences, like the one based on 29 we saw on the home page, into a single tree. This illustration shows a few nodes near the root.

I've coloured the nodes to highlight some aspects of the structure.

Yellow Multiples of 2
Red Multiples of 3
Green Numbers of the form 6n+1
Blue Numbers of the form 6n+5

The tree consists of a collection of infinitely long strings of even numbers [..., 16n, 8n, 4n, 2n], each one rooted on an odd number, 'n'. The illustration shows the strings based on 1, 3, 5 and 21.

Some of these strings spawn sub-strings (for instance, 16 in the string based on 1 spawns a new string based on 5). Strings based on multiples of 3 never spawn sub-strings, other odd numbers spawn a new string every second node (1st, 3rd, 5th, ... for blue nodes and 2nd, 4th, 6th, ... for green ones).

The root of the tree is the loop [4,2,1]. This is probably the only loop. If there are any other loops they will anchor independent trees that have no connections to this one.

The odd tree

As we have noted earlier, all even numbers are the product of an odd number and a power of 2. Once the sequence encounters an even number we are destined to reach the root odd number. We can simplify the above tree by collapsing the infinite set [n, 2n, 4n, 8n, ...] into the single node 'n'. When we do this to the previous tree we get this simpler representation

The [4,2,1] loop reduces to just '1'. The numbers on the lines represent the number of iterations to get from one number to the next, one more than the number of even numbers encountered along the way and hence one more than the 'a' values mentioned on the introductory page and discussed in more detail on the a-lists page. To calculate how far numbers are from the root we have add together the lengths of these vectors. For example, to get from 213 to 1 will take 8 + 5 = 13 steps.

The set of odd numbers that precedes a value displays the colour sequence green, blue, red, though they don't always start on the same colour. This is because these numbers follow the sequence n → 4n + 1. For instance the predecessors of 5 follow the sequence 3, 13, 53, 213, ...

Drawing these trees by hand (as in the above example) is a bit tedious so most similar images on this site are generated using a combination of Python and GraphViz. A Python script creates the GraphViz 'dot' files and GraphViz converts these to illustrations. Click here to see the tree containing all the odd numbers up to 201.

See also

Size Records: Every sequence will have a largest member. As we explore the sequences generated from ever increasing seed values we will continuously encounter larger largest values. This page enumerates a few of these record holders.

Length Records: Each sequence will have a length. As we increase the seed value we will encounter longer sequences. Each time we encounter a sequence that is longer than all the previous ones this will be a length record. To be continued.

The glide tree

Glides are sequences that end when a number smaller than the seed is encountered. The sequence we met earlier based on 29

[29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

includes the glide

[29, 88, 44, 22]

as 22 is the first number smaller than 29 encountered. I prefer to work with odd glides, and ignore the even numbers. The glide of 29 then becomes

[29, 11].

Construct a glide sequence:

 

The odd glide maps one odd number to second (smaller) one, so it will eventually arrive at 1 (or get caught in a loop). This gives us another way of constructing a tree of odd numbers, the "glide tree". This illustration shows the glide tree for odd numbers up to 39. Note that '1' is drawn differently, to identify that there isn't a glide. In 3x+1 this is the only known number that doesn't have a glide, but in other systems like 3x+5 there can be many (see "Glide Structure", below).

See also

Glide Structure: If you start with a value and iterate until you reach a smaller value you have a "glide". Join all these together and you have the glide structure. In 3x+1 the structure is a tree. This link shows the 3x+1 tree for a larger range of values and also examines the structure of other systems, 3x+5, 7, 11 and 13, where there are multiple loops. Where the basic tree seems to be tall and narrow, the glide trees tend to be short and wide.

Glide Record Holders: These identify the longest glide encountered so far as we increase the seed number. The link actually refers to a page showing the first 12 odd glide record holders. These get quite long quite quickly, for instance, the 3rd record holder is 27, which has 38 members.

[27, 41, 31, 47, 71, 107, 161, 121, 91, 137, 103, 155, 233, 175, 263, 395, 593, 445, 167, 251, 377, 283, 425, 319, 479, 719, 1079, 1619, 2429, 911, 1367, 2051, 3077, 577, 433, 325, 61, 23]

Glide Chain Records: If you examine the diagram above you can see that '3' is the smallest number only one step away from 1. The smallest number two steps away is 7, and for 3 steps it is 9. These, being the smallest numbers at successive distances from the root form the glide chain record holders. The Glide Chain Records page explores these record holders for a larger sequence of seeds.

Residues

The "residue" of a sequence is calculated by counting the number of odd and even terms in a descent and then calculating 2even/(x * 3odd). If we choose x=7, for instance we get the series [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1], which has 11 even and 5 odd members (we don't count the '1'),  so:

R(7) = 211/ (7 * 35) = 2048/1701 = 1.2039976...

Eric Roosendaal introduces residues on one of his pages - see http://www.ericr.nl/wondrous/index.html - where he discusses the non-uniformity of the distribution and postulates that the largest residue is R(993):

R(993) = 261/ (993 * 332) = 1.2531421...

This chart shows the residue distribution for all the odd numbers in the range 3 to 1048575, in bins of 0.001. See the following links for more information.

Residues can be calculated from the a-list generated by the seed (see the introductory page). Set 'n' to the number of 'a' values and 'm' to their sum. The residue is now:

R(seed) = 2m/(seed x 3n) ≡ (2/3)n x 2m-n / seed;

The second version is better for calculating as it is less likely to overflow and probably more accurate. Calculate a residue:

 

See also

The Residue Page: On this page we discus the distribution of the residue values (see illustration above) and speculate on whether R(993) really is the largest value. My distribution will be slightly different from Eric's as I ignore the even numbers.

Residue Records: Although 993 is probably the largest residue among all numbers, finding record holders when we exclude multiples of 3 is more interesting.

Domains of Attraction: Before converging on one, sequences must pass through one of one's predecessors (1, 5, 21, etc). Which of these routes a number takes has a large impact on its residue as we can see in the chart above, which is colour coded according to domain. This link explores the relative popularity of these gateways.

The 5x + 1 System

5x+1: A related system based on the 5x+1 equation.

Other pages

 

(c) John Whitehouse 2011 - 2016