The Simple Math Problem We Still Can’t Solve (2024)

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 inputnand applies one of two rules to it, depending on whether the input is odd or even. This functionfenacts the rules of the procedure we described above: For example,f(10) = 10/2 = 5 since 10 is even, andf(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 functionf.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 underf,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 underf:

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

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

Similarly, the orbit for 11 underfcan 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 underf 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 tof, but for odd numbers it just adds 1 instead of tripling them first. Sinceℊ andf are different functions, numbers have different orbits underℊthan underf. 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 underf. 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 underf, 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 then + 1 conjecture. We could explore this by testing more orbits, but knowing something is true for a bunch of numbers — even2⁶⁸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 ifnis 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, ifnis odd, thenℊ(n) =n+ 1 which is bigger thann. But sincenis odd,n+ 1 is even, and so we know where the orbit goes next:ℊwill cutn+ 1 in half. For an oddnthe 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}$ <nand $latex \frac{1}{2}$ is small, $latex \frac{n}{2}$ + $latex \frac{1}{2}$ is probably also less thann. In fact, some simple number theory can show us that as long asn> 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ℊ, applyingf to an even number makes it smaller. Andas withℊ,applyingf 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 underflooks like whennis 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 thann: $latex \frac{3n+1}{2}$ = $latex \frac{3n}{2}$ + $latex \frac{1}{2}$, and $latex \frac{3n}{2}$ = 1.5n, which is always bigger thann.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 that3n+ 1is even. If3n+ 1 is also divisible by 4, then$latex \frac{3n+1}{2}$is also even, and the orbit will fall. But if3n+ 1is 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}$.Forn> 1this is less thann,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 everyf(n) wheref(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

Click for Answer 1:

Click for Answer 2:

Notice that 2⁵ has stopping time 5, since 2⁵ → 2⁴ → 2³ → 2² → 2 → 1 → …. And since 2⁴ has stopping time 4, any number that is one step away from 2⁴ has stopping time 5. For example, 5 → 16 → 8 → 4 → 2 → 1. Could there be others?

Click for Answer 3: