Let’s play a game…

Pick a positive whole number. Any such number. Got it? Okay, if it’s an odd number, then multiply by three and add one. If it is an even number then divide by two.

Do the same for the resulting new number and keep doing this. If you arrive at the number 1 at some point, then you are done.

I realize that this is not the funniest game in the world but please play along a little more. I promise you this will be good!

For example, if we start at 7, we get the following sequence (from now on called a Collatz sequence):

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

If we start at 19 we get:

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

Note that at some point we arrived at the number 22 in both of the above sequences, therefore they have the same tail.

The question is this: do we always end up at 1?

Believe it or not, but the above question is a deep mystery. It is unsolved despite enormous efforts by very clever mathematicians!

This problem is called The Collatz Conjecture.

Into Chaos

But why is it so hard to solve? After all, a kid would understand the rules of this game. It seems very simple.

By an initial look at the Collatz sequences for small numbers, we don’t see any irregularities or unintuitive surprises but when we get to, for example, the number 27, the corresponding sequence is 111 steps long and it gets as high as 9232 before descending rather quickly towards 1.

If we plot the sequence for 27, we get the following graph:

This seems kind of random, and in fact, there is a certain randomness to this problem which makes it very hard to work with. We will get back to this in a bit.

Note that if n is an odd number then 3n+1 is an even number and we need to divide it by 2, thus we can combine the two steps into one as simply (3n+1)/2.

When we combine the two steps above, we’ll call the resulting sequence the shortened Collatz sequence.

Consider the following function:

This function will output the next number in the shortened Collatz sequence given that z is is an integer of course.

But this function, if we define it on the complex plane, is an entire function which means that we can feed it any complex number and it is complex differentiable (analytic).

Marc Chamberland investigated the iterations of this function on the real line and it turns out that this leads to a dynamical system.

He showed that the conjecture does not hold for all positive real numbers since there are infinitely many fixed points, as well as orbits.

The corresponding beautiful Collatz fractal can be seen below:

This shows that indeed there is some inherently random about these sequences.

Dynamical systems and fractals are known to stem from chaotic systems like for example the weather where the defining feature is that the system is extremely sensitive to initial conditions.

For our problem it means that there is a huge difference between considering whole numbers and real numbers even though we can get arbitrarily close to a given whole number by a sequence of real numbers — the corresponding Collatz sequences can be very different.

This creates chaos and randomness.

The Solution

So what would a solution look like?

Well, we need to show two things.

First, we need to prove that all sequences are bounded. That is, there exists a number M such that no matter what number we start with, all the numbers in the corresponding sequence are less than M.

In other words, there are no infinite Collatz sequences. Where by infinite I mean that the set of numbers in the sequence is of (countably) infinite cardinality i.e. there is a bijection to the natural numbers.

Second, we need to show that no cycles can occur. That is, we will never hit a number twice in a Collatz sequence. Recall that we stop at 1. If we move on from 1, then the 4, 2, 1 sequence repeats indefinitely.

Of course, there is another solution.

The conjecture might be wrong… Yes, it has been verified with starting values up to about 2⁶⁸, which is of course a ridiculously big number but other conjectures have been known to fail where the first example was an insanely big number.

In 1958 the Pòlya conjecture was disproved by a counterexample of about 1.845 × 10³⁶¹ which is much much MUCH bigger than out relatively small number of 2⁶⁸.

Actually, there is yet another thing that could be happening here.

Mathematicians tend to not talk much about this, because it is very unpleasant to think about.

The Collatz conjecture could be unsolvable within our axiomatic system - meaning that no matter how hard we try, we simply do not have the tools to crack it.

Don’t be Seduced by the Beauty of the Problem

So why is it a dangerous problem?

Because, when you are trying to solve a mathematical problem and you don’t know if you are able to solve it, you are spending your precious time on… maybe nothing…

Time is the most valuable commodity and it is very easy to throw it away on mathematics - especially when a problem looks this simple. But trust me. It is anything but simple. It is like the Sirens from Greek mythology:

The Sirens of Greek mythology began specifically as a group of creatures who looked like beautiful women, but were really man-eating beasts. They sat on the shore and sang with voices so seductive and compelling that anyone who heard their song became absolutely mesmerized with them. So mesmerized, in fact, that they became obsessed with reaching the shore to get closer to the sound.

And then the Sirens would eat them.

~ The Sirens — Mythology’s Original Temptresses (gods-and-monsters.com)

This problem is much like this. It seems so beautiful and simple but before you know it, you have spend years of research and energy on nothing.

Actually, many professors warn their PhD students not to go there.

Nothing, really?

Well, I only partially agree on the above..

Personally, I have spend many many hours thinking about the Riemann hypothesis, the twin prime conjecture and (I must admit) the Collatz conjecture, but I never felt I wasted my time because thinking about these beautiful problems gives me joy.

I like the process and the challenge. And even though you might not get closer to solving the actual problem, you might develop some lemmas or some other tools in the process.

If nothing else, you get to know the feeling of doing raw research and to join the many people that have gone down this road before.

You just have to make sure you don’t loose your way. Always leave a trail of breadcrumbs so you can find your way back home.