*Incomplete and in-progress...*

The Collatz Conjecture
(or Collatz problem or 3x+1 problem or hailstorm problem and many more)
is an unsolved conjecture in mathematics related to the Collatz function, which is the function that
takes a positive integer *n* to *n/2* if *n* is even or to *3n + 1* if *n* is odd.

The conjecture is that for any initial starting number that is a positive integer, iterative application of the function eventually results in *1*.

For example, if we start with *3*, the successive values are *10* (via *3n+1*), *5* (via *n/2*), *16, 8, 4, 2, 1*. We call the
sequence of numbers *3, 10, 5, 16, 8, 4, 2, 1* the *Collatz sequence* for *n = 3*, and the length
of this sequence (not including the initial *3*) is called the *Collatz length* — in this case, *7*.

If we start with *17*, then the sequence is *17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1*.
Sometimes the route to *1* is very circuitous. For example, the Collatz sequence for *27* has a length of *111*,
and it meanders above *9,000* at one point. *9,663* takes *184* steps, and its highest value
is more than 27 million!

Here are some images that give a sense of how the length of the Collatz sequence varies with *n*. Click on
any image to get a bigger version.

Note the spike at *n = 27* in the following image:

As you can see, there is quite a bit of variety in the lengths, and yet there are regularities too. You can see many examples of two or three consecutive values of *n*
that have the same length, and there are much longer stretches of consecutive values, too. The following illustrates that from *7083* to *7099*, all *n* have
the same length (57)!

If we look at any particular sequence — e.g., *3, 10, 5, 16, 8, 4, 2, 1* — we note that we could start at the end, with *1*, and apply the rules *in reverse* to end up with the initial number.
Moreover, we could continue this process past our original number.

The rules in reverse are slightly more complicated, since in the reverse direction a number can be followed by two different numbers, one through each
of the two rules. For example, we could get to *16* using the original rules by applying the *n/2* rule to *32*, or we could get to *16* by applying the *3n+1* rule to
*5*. Thus, if we are starting with *16* and trying to find the following numbers in the reverse sequence, we see that it is followed by both *5* and *32*.

The following image illustrates this scenario, and uses the following conventions (as do all the tree images): going to a number via the reverse of the *3n+1* rule is illustrated
by a solid line to a purple node; going to a number via the reverse of the *n/2* rule is illustrated by a dotted line to a blue node.

If we consider the tree that is formed by running the rules in reverse, starting with *1*, it should be clear that the Collatz Conjecture is equivalent to saying that the predecessor
tree is really a tree (not a graph: no cycles) and that every positive number is in the tree somewhere.

As you can see in the following image, which shows the first 20 levels of the predecessor tree starting at 1, the tree gets very wide, very fast.

To relate this tree to the examples we’ve seen above, you can find *3* in the tree, and then follow the path back to *1*, and the numbers you’ll pass through are the numbers
of the Collatz sequence starting with *3*. The number of nodes that you go to in order to walk from *3* up to *1* is *7*, which was the Collatz length for *3*. Thus,
the depth of a node is the Collatz length, and the nodes from a node to the root of the tree represents the Collatz sequence for that number. In the previous tree, you’ll note that *27* is absent.
Since the Collatz length of *27* is *111*, the tree would have to be at least *111* levels deep in order to contain *27*.

As we can see in the tree above, the image gets overwhelming very quickly. In order to see more of the tree, we can just include the odd-numbered nodes, connecting each odd-numbered node to its odd-numbered predecessor without any intermediate even-numbered predecessors. The edge from one odd node to another will be labeled with the number of intermediate even nodes that were omitted.

Here is a tree that includes the first 100 smallest odd numbers that are reachable before a depth of 10:

It’s easy to recreate the even numbers that are omitted using the compressed tree. For example, starting with *13*, in the third level, we would apply the *3n + 1* rule once, yielding *40*, and then apply the *n/2* rule as many times as the label on the edge between *13* and its parent node, *5*. In this case, we would apply *3* halving operations, which yields *20, 10, 5*, which is the parent node’s value.

To be continued ...

This site is valid XHTML+RDFa, CSS.