Almost Proven

The Collatz Conjecture starts with a deceptively simple proposition. Pick a positive whole number. If the number is odd, multiply it by 3 and then add one to the result. If the number is even, divide it by two instead. Then repeat the process, only stopping if you get the value 1 as your result.

In 1937, German mathematician Lothar Collatz hypothesized that for any natural number you might choose to start with, you will ultimately end up with the value one as your final result. In the following chart, we’ve shown the trajectory of results you would get for each starting whole number you might pick from one to fifteen, which are called orbits in mathematicalese, which shows some of the inherent complexity that lurks within the seemingly simple algorithm.

The Collatz Conjecture, or Collatz Problem, is one of the most famous open propositions in math, because in all the time since it was first proposed, it has not yet been proven. Sure, it’s been demonstrated for the first quintillion natural numbers (those with 19 or fewer digits), but no one has been able to definitively prove it applies for every natural number that might ever be contemplated.

That’s why it was big news in the math world several weeks ago when Terence Tao published a paper and blog post to claim that he had almost proven the conjecture. Tao is something of a rock star among mathematicians, where his contribution to the particular problem of the Collatz Conjecture was to determine that the potential counterexamples of where it might be false are extremely rare.

Alas, that’s not to say he found such a counterexample, which would officially close the Collatz problem because it would have been demonstrated to not be true, nor is it the elusive proof that there are no such potential counterexamples, which would also close the books on the question of the conjecture’s validity.

Regardless, Tao’s paper represents forward progress in resolving the question, which may provide a foundation for future work that does ultimately prove the conjecture.

Part of what makes the problem fascinating is that it does lead to very interesting structures when the resulting orbits are visualized. For instance, if you look at the orbits for n = 14 (light orange) and n = 15 (light gray) in our chart above, would you have ever expected them to ‘reflect’ off each other through their first eight iterations before syncing to degrade together at their ninth iteration? Or that n = 9 would produce the longest orbit, with the highest number of iterations before degrading to one, for the starting numbers we presented?

If you prefer factor trees, you could check out Jason Davies’ Collatz graph application. Or, if you visualize many more orbits, you might get a structure that looks suspiciously organic, as Alex Bellow illustrates in the following Numberphile video:

But before you get too excited, we would be remiss if we didn’t leave you with xkcd’s take on the Collatz Conjecture.

A little Collatz goes a long way!