The Simple Math Problem We Still Can’t Solve

This column comes with a warning: Do not try to solve this math problem.

You will be tempted. This problem is simply stated, easily understood, and all too inviting. Just pick a number, any number: If the number is even, cut it in half; if it’s odd, triple it and add 1. Take that new number and repeat the process, again and again. If you keep this up, you’ll eventually get stuck in a loop. At least, that’s what we think will happen.

Take 10 for example: 10 is even, so we cut it in half to get 5. Since 5 is odd, we triple it and add 1. Now we have 16, which is even, so we halve it to get 8, then halve that to get 4, then halve it again to get 2, and once more to get 1. Since 1 is odd, we triple it and add 1. Now we’re back at 4, and we know where this goes: 4 goes to 2 which goes to 1 which goes to 4, and so on. We’re stuck in a loop.

Or try 11: It’s odd, so we triple it and add 1. Now we have 34, which is even, so we halve it to get 17, triple that and add 1 to get 52, halve that to get 26 and again to get 13, triple that and add 1 to get 40, halve that to get 20, then 10, then 5, triple that and add 1 to get 16, and halve that to get 8, then 4, 2 and 1. And we’re stuck in the loop again.

The infamous Collatz conjecture says that if you start with any positive integer, you’ll always end up in this loop. And you’ll probably ignore my warning about trying to solve it: It just seems too simple and too orderly to resist understanding. In fact, it would be hard to find a mathematician who hasn’t played around with this problem.

I couldn’t ignore it when I first learned of it in school. My friends and I spent days trading thrilling insights that never seemed to get us any closer to an answer. But the Collatz conjecture is infamous for a reason: Even though every number that’s ever been tried ends up in that loop, we’re still not sure it’s always true. Despite all the attention, it’s still just a conjecture.

Yet progress has been made. One of the world’s greatest living mathematicians ignored all the warnings and took a crack at it, making the biggest strides on the problem in decades. Let’s take a look at what makes this simple problem so very complicated.

To understand the Collatz conjecture, we’ll start with the following function:

$latex f(n) = \begin{cases}
n / 2 & \text{if $n$ is even } \\
3n+1 & \text{if $n$ is odd }
\end{cases}\ $

You might remember “piecewise” functions from school: The above function takes an input n and applies one of two rules to it, depending on whether the input is odd or even. This function f enacts the rules of the procedure we described above: For example, f (10) = 10/2 = 5 since 10 is even, and f (5) = 3 × 5 + 1 = 16 since 5 is odd. Because of the rule for odd inputs, the Collatz conjecture is also known as the 3n + 1 conjecture.

The Collatz conjecture deals with “orbits” of this function f. An orbit is what you get if you start with a number and apply a function repeatedly, taking each output and feeding it back into the function as a new input. We call this “iterating” the function. We’ve already started computing the orbit of 10 under f,  so let’s find the next few terms:

f (10) = 10/2 = 5
f (5) = 3 × 5 + 1 = 16
f (16) = 16/2 = 8
f (8) = 8/2 = 4

A convenient way to represent an orbit is as a sequence with arrows. Here’s the orbit of 10 under f:

10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1 → …

At the end we see we are stuck in the loop 1 → 4 → 2 → 1 → ….

Similarly, the orbit for 11 under f can be represented as

11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → ….

Again we end up in that same loop. Try a few more examples and you’ll see that the orbit always seems to stabilize in that 4 → 2 → 1 → … loop. The starting values of 9 and 19 are fun, and if you’ve got a few minutes to spare, try 27. If your arithmetic is right, you’ll get there after 111 steps.

The Collatz conjecture states that the orbit of every number under f eventually reaches 1. And while no one has proved the conjecture, it has been verified for every number less than 2⁶⁸. So if you’re looking for a counterexample, you can start around 300 quintillion. (You were warned!)

It’s easy to verify that the Collatz conjecture is true for any particular number: Just compute the orbit until you arrive at 1. But to see why it’s hard to prove for every number, let’s explore a slightly simpler function,ℊ.

$latex g(n) = \begin{cases}
n / 2 & \text{if $n$ is even } \\
n+1 & \text{if $n$ is odd }
\end{cases}\ $

The functionℊ is similar to f, but for odd numbers it just adds 1 instead of tripling them first. Since ℊ and f are different functions, numbers have different orbits under ℊ than under f. For example, here are the orbits of 10 and 11 under ℊ:

10 → 5 → 6 → 3 → 4 → 2 → 1 → 2 → 1 → 2 → …
11 → 12 → 6 → 3 → 4 → 2 → 1 → 2 → 1→ 2 → …

Notice that the orbit of 11 reaches 1 faster under ℊ than under f. The orbit of 27 also reaches 1 much faster under ℊ.

27 → 28 → 14 → 7 → 8 → 4 → 2 → 1 → 2 → …

In these examples, orbits under ℊ appear to stabilize, just like orbits under f, but in a slightly simpler loop:

→ 2 → 1 → 2 → 1 → ….

We might conjecture that orbits underℊ always get to 1. I’ll call this the “Nollatz” conjecture, but we could also call it the n + 1 conjecture. We could explore this by testing more orbits, but knowing something is true for a bunch of numbers — even 2⁶⁸ of them — isn’t a proof that it’s true for every number. Fortunately, the Nollatz conjecture can actually be proved. Here’s how.

First, we know that half of a positive integer is always less than the integer itself. So if n is even and positive, then ℊ(n) = n/2 < n. In other words, when an orbit reaches an even number, the next number will always be smaller.

Now, if n is odd, then ℊ(n) = n + 1 which is bigger than n. But since n is odd, n + 1 is even, and so we know where the orbit goes next: ℊ will cut n + 1 in half. For an odd n the orbit will look like this:

… → n → n + 1 → $latex \frac{n+1}{2}$ → …

Notice that $latex \frac{n+1}{2}$ = $latex \frac{n}{2}$ + $latex \frac{1}{2}$. Since $latex \frac{n}{2}$ < n and $latex \frac{1}{2}$ is small, $latex \frac{n}{2}$ + $latex \frac{1}{2}$ is probably also less than n. In fact, some simple number theory can show us that as long as n > 1, then it’s always true that $latex \frac{n}{2}$ + $latex \frac{1}{2}$< n.

This tells us that when an orbit under ℊ reaches an odd number greater than 1, we’ll always be at a smaller number two steps later. And now we can outline a proof of the Nollatz conjecture: Anywhere in our orbit, whether at an even or an odd number, we’ll trend downward. The only exception is when we hit 1 at the bottom of our descent. But once we hit 1 we’re trapped the loop, just as we conjectured.

Can a similar argument work for the Collatz conjecture? Let’s go back to the original function.

$latex f(n) = \begin{cases}
n / 2 & \text{if $n$ is even } \\
3n+1 & \text{if $n$ is odd }
\end{cases}\ $

As with ℊ, applying f to an even number makes it smaller. And as with ℊ, applying f to an odd number produces an even number, which means we know what happens next: f will cut the new number in half. Here’s what the orbit under f looks like when n is odd:

… → n → 3n + 1 → $latex \frac{3n+1}{2}$ → …

But here’s where our argument falls apart. Unlike our example above, this number is bigger than n: $latex \frac{3n+1}{2}$ = $latex \frac{3n}{2}$ + $latex \frac{1}{2}$, and $latex \frac{3n}{2}$ = 1.5n, which is always bigger than n. The key to our proof of the Nollatz conjecture was that an odd number must end up smaller two steps later, but this isn’t true in the Collatz case. Our argument won’t work.

If you’re like me and my friends back in school, you might now be excited about proving that the Collatz conjecture is false: After all, if the orbit keeps getting bigger, then how can it get down to 1? But that argument requires thinking about what happens next, and what happens next illuminates why the Collatz conjecture is so slippery: We can’t be sure whether $latex \frac{3n+1}{2}$ is even or odd.

We know that 3n + 1 is even. If 3n + 1 is also divisible by 4, then $latex \frac{3n+1}{2}$ is also even, and the orbit will fall. But if 3n + 1 is not divisible by 4, then $latex \frac{3n+1}{2}$ is odd, and the orbit will rise. In general we can’t predict which will be true, so our argument stalls out.

But this approach isn’t completely useless. Since half of all positive integers are even, there’s a 50% chance that $latex \frac{3n+1}{2}$ is even, which makes the next step in the orbit $latex \frac{3n+1}{4}$. For n > 1 this is less than n , so half the time an odd number should get lower after two steps. There’s also a 50% chance that $latex \frac{3n+1}{4}$ is even, which means there’s a 25% chance that an odd number will be reduced to less than half of where it started after three steps. And so on. The net result is that, in some average way, Collatz orbits decrease when they encounter an odd number. And since Collatz orbits always decrease at even numbers, this suggests that all Collatz sequences must decrease in the long run. This probabilistic argument is widely known, but no one has been able to extend it to a complete proof of the conjecture.

Yet several mathematicians have proved that the Collatz conjecture is “almost always” true. This means they’ve proved that, relative to the amount of numbers they know lead to 1, the amount of numbers they aren’t sure about is negligible. In 1976 the Estonian American mathematician Riho Terras proved that, after repeated application of the Collatz function, almost all numbers eventually wind up lower than where they started. As we saw above, showing that the numbers in the orbit consistently get smaller is one path to showing that they eventually get to 1.

And in 2019, Terence Tao, one of the world’s greatest living mathematicians, improved on this result. Where Terras proved that for almost all numbers the Collatz sequence of n ends up below n, Tao proved that for almost all numbers the Collatz sequence of n ends up much lower: below $latex \frac{n}{2}$, below $latex \sqrt{n}$, below $latex \ln n$ (the natural log of n), even below every f(n) where f(x) is any function that goes off to infinity, no matter how slowly. That is, for almost every number, we can guarantee that its Collatz sequence goes as low as we want. In a talk about the problem, Tao said this result is “about as close as one can get to the Collatz conjecture without actually solving it.”

Even so, the conjecture will continue to attract mathematicians and enthusiasts. So pick a number, any number, and give it a go. Just remember, you’ve been warned: Don’t get stuck in an endless loop.

Exercises

1. Show that there are infinitely many numbers whose Collatz orbits pass through 1.

2. The “stopping time” of a number n is the smallest number of steps it takes for the Collatz orbit of n to reach 1. For example, the stopping time of 10 is 6, and the stopping time of 11 is 14. Find two numbers with stopping time 5.

3. In a recent talk on the Collatz conjecture, Terrance Tao mentioned the following Collatz-like function:

$latex h(n) = \begin{cases}
n / 2 & \text{if $n$ is even } \\
3n-1 & \text{if $n$ is odd }
\end{cases}\ $

Tao points out that in addition to the 1 → 2 → 1 → 2 → 1… loop, two other loops appear. Can you find them?

Answers