Exploring the Collatz Problem

Home » Misc.

Introduction

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!

Visualizations of Collatz Length

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:

Length of n from 1 to 200

Length of n from 10,000 to 10,200

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)!

Length of n from 7,000 to 7,100

Sequences in reverse yield a Predecessor Tree

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.

Predecessors of 16 as a tree

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.

Predecessor Tree of Odd Numbers

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:

Click to see larger image

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

To be continued ...

This site is valid XHTML+RDFa, CSS.