A Collatz Conundrum

Sophie Maclean

I want you to pick a positive integer. Any one – you have free choice. If your number is odd, I want you to multiply it by 3 and add 1. If it is even, I’d like you to halve it. Take your result and repeat the process. In fact, I want you to keep repeating until you end up stuck in the loop.

For example, if your number is 7, you would first multiply by 3 and add 1 to get 22. Now you would have an even number, so you would halve it to get 11. 11 is odd, and \(3 \times 11 + 1 = 34\). Then the pattern would continue…

Writing with arrows actually proves to be a very useful notation. We can show the path from 11 as 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> …

Your turn now. Pick your own number and follow the algorithm until you find yourself stuck in a loop. Done it?

Okay.

I’m going to start by saying that I do not know with mathematical certainty what numbers you have ended up with. But, I am going to make a guess and I am very confident in my prediction. I think that you have ended up in a cycle going 1 -> 4 -> 2 -> 1 and so on. Am I right?

You can do it again and pick a new number if you would like. I will be right again. In fact, I would bet my reputation on the fact that, for any number you pick, you will end up in the 1 -> 4 -> 2 cycle.

So how can I be so confident? Well, it all comes down to a famous conjecture:

Define the function \(f\) by:

\( f(n) = \begin{cases} n/2 \qquad \text{ if n even} \\ 3n + 1 \qquad \text{ if n odd.} \end{cases}\)

Now form a sequence by iteratively applying \(f\) to our starting number \(f(n)\). In symbols, we can write this by letting \(a_i\) denote the ith element of the sequence. Then \(a_{i+1}\) is defined iteratively by \(a_{i+1} = f(a_i)\), and \(a_0 = n\).  

It can sometimes be more useful to consider an alternative but equivalent definition of the sequence: the ith element of the sequence as being the result of applying \(f\) to \(n\) \(i\) times i.e. \(a_{i} = f^i(n)\).   

The Collatz Conjecture hypothesises that, for any integer \(n\geq 1\), this process will eventually reach 1. That is to say, that for every \(n\), there is an \(i\) such that \( f^i(n) = 1\).

If there exists an \(i\) such that \( f^i(n) = 1\), I am going to say that “\(n\) satisfied the Collatz criterion.”

You may have noticed that this process of repeatedly applying \(f\) to our \(n\) is exactly what I asked you to do at the beginning of the article. If the Collatz Conjecture is true, and we do always reach 1, then repeatedly applying \(f\) gets us stuck in a 1 -> 4 -> 2 -> 1 loop, just as I claimed in my prediction. So did I cheat? Kind of.

Despite the Collatz conjecture not requiring any high level mathematics to be understood, and despite it having been made by mathematician Lothar Collatz in 1937, almost \(100\) years ago, we still do not know whether or not the Collatz Conjecture is true. I therefore wasn’t lying when I said that I do not know with mathematical certainty what numbers you ended up with. However, we do know that it is true for all \(n \leq 2^{71} \approx 2.36 \times 10^{21}\). So I was really betting that you would not pick a number greater than 2 sextillion. In that case, I could be certain that you would end up in the cycle.

For the purposes of our game, knowing the outcome up to 2.36 sextillion was sufficient as I would be shocked if anyone picked a number greater than that. But, as a mathematician, I find that very unsatisfying. I want to know definitively – is the Collatz Conjecture true for all positive integers \(n\)? 

The calculation takes how long…?

Whilst we do not have a definitive answer for whether or not the Collatz conjecture is true, there is some strong evidence that it is true. As I have previously mentioned, the conjecture has been proven true for all values up to \(2^{71}\). This value is up to date as of 15th January 2025, and was proven by David Barina.

My first thought when reading this was that I wanted to know how long it would take my computer to do this. Let us suppose that the computer was following a naive algorithm – for each \(n\), tested in increasing order, we apply \(f\) repeatedly and only stopping when it hits 1, or reaches a cycle.

As a rough heuristic, note that every application of \(f(n)\) takes one or two calculations. My computer’s central processing unit (CPU) can perform roughly 3.2 billion calculations per second. So even if each integer got to 1 in a single application of \(f\), it would take my computer on the order of \(10^{13}\) seconds to test all the integers up to \(2^{71}\). If you run the numbers, it would take my computer nearly 25 thousand years to do all the tests.

Of course, my personal computer is not going to be anywhere near as fast as some that you may get in labs. It is also highly unlikely that any researcher doing this calculation would only harness the power of one computer.  You might therefore expect that in actuality, testing integers this way would take a lot less time than 25 thousand years. But don’t forget that this was based on the assumption that it took each integer only one application of \(f\) to get to 1. This just is not true! 

There is precisely one integer that takes one application of \(f\) to get to \(1\) i.e. \(2\). In fact, aside from 2 (and \(1\) itself), all integers take at least two steps, and the number of steps for \(n\) to reach \(1\) is always at least \(\log_2(n)\) ¹. This means that half the integers from 1 to \(2^{71}\) take at the very least \(70\) steps, with some taking much more.

So it looks like this naive approach – even with lots of high powered computers – is still going to take quite some time. Certainly more than the period of time for which humans have had computer technology! There must, therefore, be some way to speed up our testing.

Simplifying and Sieving

The first thing we can do to speed up our algorithm is to realise that, instead of showing that for every \(n\), there is an \(i\) such that \( f^i(n) = 1\), we actually just need to show that for every \(n>1\), there is an \(i\) such that \( f^i(n) < n\). Why is this enough? Well this means that we can apply an inductive argument: If the Collatz criterion is met for every integer \(1 <= k <n\), and \( f^i(n) < n\), then the Collatz criterion is met for \( f^i(n)\) and therefore must be true for \(n\). 

This already speeds up our algorithm as we can reduce the amount of duplicate work. Especially as we are testing \(n\) in increasing order, this means we will stop as soon as we have reached a number for which we already know the Collatz criterion to apply. 

Another way of speeding up the algorithm is by applying what Barina refers to as a \(3^k\) sieve. I will first show you the \(3^1\) sieve, then how to extend this. First observe that 

\(f^2(2n + 1) = f( 3(2n+1) + 1) = f( 6n + 4) = 3n + 2\)

Here, the first application of \(f\) multiplies by 3 and adds 1, because \(2n+1\) is odd. Then we have an even number so we halve it. Because we are testing whether \(n\) satisfies the Collatz criterion in increasing order of \(n\), by the time we come to test \(3n + 2\), we have already tested \(2n+1\). So assuming we have not already found a counter example to the Collatz conjecture, we know that by the time we reach \(3n+2\), we will have already tested it.

We therefore do not need to test any numbers of the form \(3n + 2\) – these are often referred to as numbers that are 2 modulo 3. This cuts down the amount of numbers we need to test by ⅓. 

That is the \(3^1\) sieve. The \(3^2\) sieve applies similar reasoning but instead looks at numbers modulo \(3^2 = 9\). For example, repeatedly applying \(f\) gives

So we therefore do not need to test any numbers of the form \(9n+4\), i.e. numbers which are \(4\) modulo \(9\). Furthermore, any numbers which are \(2, 5\) or \(8\) more than a multiple of \(9\) are \(2\) modulo \(3\), so we do not need to check them either. This now eliminates 4/9 of the numbers we need to check!

Unfortunately, though this seems to be a promising method, applying a \(3^k\) sieve does not eliminate anything extra for \(k>2\). So we have already reached the limit of this improvement.

In Binary?

One final improvement on the algorithm can be obtained by converting \(n\) into binary. 

If the binary representation ends in \(k\) ones, we can apply \(3n + 1\),  followed by (n/2) (which we shall refer to as Iterate 1) \(k\) times. This takes our original \(n\), which will be of the form \(b2^k -1\) to \(b3^k -1\) with \(k\) sets of Iterate 1. 

If the binary representation ends in \(k\) zeros, we can apply \(n/2\) (which we shall refer to as iterate 0), \(k\) times, each time essentially deleting \(k\) zeroes from the end of the binary representation. This takes our original \(n\), which will be of the form \(a2^k\) to \(a\) with \(k\) sets of Iterate 2.

For example, let’s take \(7\). In binary, \(7\) is written \(111\), so is \(2^3 – 1\). We now immediately know that after \(3\) iterates, \(7\) goes to \(3^3 – 1 = 27 – 1 = 26\). Note that we don’t know what numbers we travel through to get from \(7\) to \(26\). We only care where we end up after completing Iterate 1 three times. 

Now we are at \(26\). In binary, \(26 = 11010\). So this will go to \(1101 = 13 = 7 \times 2^1 -1\) after the application of the even step. One odd step takes us to \(7 \times 3^1 – 1 = 20\). In binary, \(20 = 10100\), and so on.

Written another way, we have shown that

Remember, we don’t care which numbers come in between in the sequence. By allowing ourselves to jump straight to the end result of the \(k\) iterates, we can save a lot of calculation time. In fact, for odd \(n\), we compute an average of \(4\) iterates at each application of our algorithm.

What Next?

The above methods have been used to speed up testing whether integers satisfy the Collatz criterion, and will continue to be used, I’m sure, to show that the conjecture is true for greater and greater \(n\). So, when does it stop?

Obviously if we ever find a counter example, we have immediately disproved the Collatz conjecture, and the venture stops straight away. On the flip side, with every new number we find that satisfies the Collatz criterion, we can be more and more confident that the Collatz conjecture is true. But unfortunately, this will never be enough to be certain. Mathematicians learned this the hard way.

For a long time, it was thought that the Pólya conjecture, which claims that at least half of the natural numbers less than \(N\) have an odd number of prime factors, for any \(N\). This was believed to be true from when Pólya conjectured it in 1919, right through to when C. Brian Haselgrove found a counter example of roughly \(1.845 \times 10^{361}\) in 1958.

So, for now, the Collatz conjecture remains that – a conjecture. Maybe you will be the one to finally prove it.

1. To see this, note that \(a_i = f^i(n)\) is either over \(3\) times as large as \(a_{i-1}\) or half the size. So the magnitude shrinks at most by a factor of \(2\).  ↩︎

The post A Collatz Conundrum originally appeared on the HLFF SciLogs blog.