Some of my more long-term readers (one or both of you) may have figured out by now that I like stuff I can animate. In the case of numbers and math, that’s whatever I can automate in a VBScript and feed into an Excel spreadsheet, then save as individual jpegs that I can stitch together in a movie editor. So, I’m always looking for some way of doing that when I find a new formula or algorithm. Unfortunately, Collatz doesn’t immediately lend itself to any kind of animation I consider interesting, but that doesn’t stop me from at least drawing up different kinds of charts in an attempt to try.

So, what exactly is the Collatz Conjecture telling us? In effect, the algorithm creates a series of “ladders” through the application of the first rule (if the number is even, divide it by 2). The ground level of the ladder is any one of the odd integers greater than 1. The ladder itself consists of that “ground” times powers of 2 (i.e.: 3, 6, 12, 24, 48, 96…, which is just 3*(1, 2, 4, 8, 16, 32…)). The exception to this is the ladder that has 2 for the ground, and we can think of that as 1*(2, 4, 8, 16, 32…)

Rule 2 (if the number is odd, multiply by 3 and add 1) is what allows us to change ladders. At a minimum, the new number will place us on rung 1 of the new ladder (e.g. – n0 = 3; n1 = 9 + 1, the new ladder has a ground of “5”). Looking at this a little closer, numbers in a sequence get bigger by a factor of about 1.5 when rule 2 applies, because it’s immediately followed by rule 1 at least once, assuming rule 2 lands on the first rung of the new ladder. Otherwise, hitting the ladder farther up (say with n0 = 5, n1 = 16, n2 = 8, n3 = 4, n4 = 2, n5 = 1) causes the ladder to “collapse” all the way down to the odd-numbered root by a factor of 4 or greater. It’s this collapse of the ladder that prevents the sequence from going to infinity any faster than by 1.5, if at all. The Conjecture, in fact, states that any positive integer you start with will eventually go to 1, which is due specifically to rule 2 switching to rungs relatively high up on certain ladders, and then that ladder collapsing.

Given that rule 1 results in the sequence going to odd numbers before rule 2 can take effect, it would kind of make sense to remove all even numbers from a chain and only consider the odd-numbered points. Looking at the above badly-drawn chart, that’s essentially what we have. 7->22->11->34->17->52->26->13->40->20->10->5->16…1 turns into 7->11->17->13->5->1. There’s no real pattern that I can see easily, but there is an implication.

Actually, there’s an unstated third rule that I feel needs to be put forth now. Rule 0: If n = 1, stop.

I know it’s part of the description of the algorithm, but I want it to be more blatantly obvious. If we mindlessly apply rules 1 and 2, we get into an infinite loop, where 1->4->2->1… With rule 0 in place, we can claim that 2 is no longer the exception for the ladder ground values, and that 1 is in fact the lowest-most ladder and 2 is the first rung on it. The above odd-number reduction chain (7->11->17->13->5->1) makes more sense this way.

Getting back to the Conjecture, if we treat all of the chains that branch off of the root value of 1 as a tree, then every positive integer should appear in this tree once and only once. The implication is that we will never see an odd number showing up twice in the reduction chain (i.e. – 7->11->17->13->5->7…) which would produce an infinite loop.

If we pretend that the Conjecture is wrong, it means that there is either a second (or more) tree independent of the main root=1 tree, or that there is at least one chain that forms a closed loop. For an independent tree, we’d need either some minimum number that the tree reduces to and goes no farther in the sequence (the role that 1 plays in the main tree), or that goes to infinity so there is no “root” per se. Remember, rule 2 represents a maximum growth factor of 1.5, while rule 1 is unpredictable, and gives a growth factor anywhere from 0.5 to almost 0. Since we can’t have a minimum root value that isn’t 1, the root sequence has to go to infinity, but that means that the combination of rules 1 and 2 MUST have a growth factor in this root sequence that is greater than 1 by some fraction. But, that means that every time we switch ladders via rule 2, we hit rung 1 of the next higher odd number more often than we don’t. In other words, for Nn+1 = (3Nn + 1)/2; Nn+1 must almost always be odd. For this to hold true, there must be an entire, infinite class of numbers for which the Collatz sequence never intersects any branch of the main tree. This is unlikely at best.

This leaves the second case, where there’s an infinite loop. Say we start with 9. The sequence would be 9->28->14->7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1. BUT, rather than collapsing down from 40 to 10 (we hit the third rung up on the 5 ladder) what if we’d collapsed down from 40 to 9? Looking only at the odd numbers in the chain, we’d get 9->7->11->17->13->9. Then, applying rule 2 again, we’d just repeat the loop. What this means is, at large enough numbers, there could be a case where Nn/2^x = N0. If this happened, it would invalidate the Conjecture, which says that, in effect, (as mentioned above) no number can appear twice in one chain. Naturally, this situation would also create a Swiss cheese effect in the main tree, where an infinite number of points branching off the closed loop are not part of the main tree (those points that are factors of N*2^x).

Intuitively, it seems clear that the Conjecture has to hold true, but no one’s ever proved it conclusively. In a way, the Collatz algorithm is a lot like the generation of prime numbers. Using a brute force Sieve of Eratosthenes approach of drawing out the chains for each new odd number not yet attached to the main tree leaves a bunch of holes (i.e. – “prime numbers”), which then represent a new branch on the main tree for some odd-numbered node that is much larger than the “prime” we started with (e.g. – starting with 7 takes us to the node point at 13, on the 5-ladder). The question then becomes, is there a way to analyze any random positive integer, without using rules 1 and 2, and determine the number of steps it would take to reach 1? If the result was infinite, then that integer would have to be in the closed loop.

For such a simple algorithm, it’s actually a lot of fun to play with.