The Collatz Conjecture – Maths Society

Yuvan D

The Collatz conjecture is one of the most infamous yet simple mathematical problems in the world. No one can seem to prove it, despite the attention of some of the world’s best mathematicians. So how does it work and why can’t we solve its mystery yet?

The conjecture begins by choosing a random number. We then apply two rules to this number, and keep applying these rules to the result:

If the number is odd, you multiply it by 3, then add 1 to it.

If the number is even, you divide it by 2.

These two rules can be written algebraically as:

$3x+1$
$\frac{x}{2}$

For example, let’s take 7. 7 is odd, so we substitute it into the first equation:

$3\times7+1=22$

The result, 22, is even, so we substitute it into the second equation:

$22\div2=11$

We keep repeating this pattern: $11\to34\to17\to52\to26\to13\to40\to20\to10\to5\to16\to8\to4\to2\to1$

Eventually, the sequence reaches 1, and here’s where it gets interesting. 1 is odd, so we multiply it by 3 and add 1 to get 4. 4 is even, so we divide it by 2 to get 2, and 2 is also even, so we halve it again to get 1. Here, we’re stuck in a 4–2-1 loop. The conjecture is this:

For every positive integer, if you continue applying these rules, you will eventually end up in the 4-2-1 loop.

This is the Collatz Conjecture, named after German mathematician Lothar Collatz, who introduced the idea in 1937. However, the problem has many other origin stories and names, such as the Ulam Conjecture, Hasse’s Algorithm and ‘3n+1’.

Why is the conjecture famous

Among the world of mathematicians, the 3n+1 problem was not famous but infamous, because the paths that different numbers take vary so widely that it’s difficult to even start making progress towards it.

For example, for a number like 26, once you apply 3n+1 to it it rises to 40, and takes 10 steps to reach 1. So, its total ‘stopping time’ would be 10.

But, if you take the very next number, 27, it bounces around all over the place. In fact, it climbs up all the way to 9232 and takes 111 steps for it to get to 1.

Why do all, or most, of the numbers always reach one?

You may ask, if all odd numbers are multiplied by 3 and have 1 added to them, but all even numbers are divided by 2, shouldn’t the sequences in the Collatz Conjecture increase rather than decrease?

Each odd number is followed by an even number, as an odd number substituted into 3n+1 will always be even. Since that even number is divided by 2, that means most of the odd numbers only increase by a factor of about $\frac{3}{2}$ .

Imagine a path from an odd number in a 3n+1 sequence. You’ll always end up with an even number next. 50% of the time, dividing by 2 brings you back to an odd number. 25% of the time, you divide by 4 to get to the next odd number. In this case, the next odd number will be about ¾ of its initial value. $\frac{1}{8}$ of the time, you divide by 8 to get to the next odd number, and $\frac{1}{16}$ of the time, you divide by 16 to get to the next odd number, and so on. This is illustrated in the diagram below.

If we take the geometric mean of this, you find that on average, you multiply by ¾ to get from one number to the next (which is less than 1), so statistically speaking, it makes sense as to why at least the vast majority of positive integers end up at 1 after these rules are applied.

A geometric mean is another type of mean, similar to the arithmetic mean, which is written algebraically as $\frac{x_1+x_2+…+x_n}{n}$ . The geometric mean is written algebraically as: $\sqrt[n]{x_1\times x_2\times…\times x_n}$

How could the conjecture be false?

There are two ways the conjecture could be false:

1. There could be one ‘random’ number that starts a sequence that keeps going forever and doesn’t stop.

2. There is a sequence of numbers that form another closed loop, like 4-2-1. All these numbers would be disconnected from the other numbers that branch back into 4-2-1.

However, no loop or sequence that shoots off to infinity has been found yet, and not for a lack of trying.

Mathematicians have tested by brute force every single number up to $2^{68}$ : that is 295,147,905,179,352,825,856 digits. In fact, given this information, mathematicians have calculated that any loop other than 4-2-1 made of positive integers must be at least 186 billion numbers long.

On the other hand, if you include negative numbers, you get 3 independent loops of numbers starting at low numbers like -17, -5 and -1. So why should there be disconnected loops on the negative side of the number line, but not on the positive side?

$2^{68}$ may seem like a lot of digits, but on the scale of all numbers, it’s nothing. For example, counterexamples for other conjectures have gone up to numbers as high as $1.845\times10^{361}$ .

So, for a range equal to or greater than $2^{1000}$ using brute force isn’t an option. You’ll need to use an intelligent method to prove/disprove the conjecture.

In conclusion, the Collatz Conjecture highlights the vast depth of maths that is yet to be explored and the peculiar beauty of numbers, and it remains one of the simplest yet most mind-boggling puzzles of all time.