The Collatz Conjecture: Why a Simple Rule Has No Proof

Pick any whole number. If it's even, cut it in half. If it's odd, triple it and add one. Now do it again, to whatever number you just got. And again.

Does this always end at 1?

Try it with 6: $6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$. Yep. Try 11: it climbs to 34, drops to 17, jumps to 52, and after fourteen steps, lands on 1 too. Try any number you like, on paper, in your head, on a phone. It always seems to make it down to 1.

Nobody has ever proven that it always does. And nobody has ever found a single number where it doesn't. Computers have checked every starting number up to roughly $2.95 \times 10^{20}$, that's 295 quintillion numbers, and every one of them eventually hits 1. Still, "every number we've tried" isn't a proof. It's just a very large pile of evidence.

This is the Collatz conjecture. Paul Erdős, one of the most prolific mathematicians of the twentieth century, looked at it and said mathematics wasn't ready for problems like this one. He wasn't joking, and he wasn't being modest. He meant it.

The rule is too simple to be this stubborn

Here's the whole thing, written out properly. Given a positive whole number $n$:

That's it. No exceptions, no special cases. A ten-year-old can run it by hand. And yet it's one of the most famous unsolved problems in all of mathematics.

Mathematicians have a nickname for the sequences this rule produces: hailstone numbers. Picture a hailstone forming inside a storm cloud. Updrafts toss it upward, it picks up more ice, it falls, gets caught in another updraft, rises again... and eventually, when it's heavy enough, gravity wins and it drops straight to the ground. That's exactly what these sequences do. They climb when they hit an odd number, they fall when they hit an even one, and the climbs and falls look completely random along the way. But so far, every single one eventually crashes down to 1.

Watch one of these hailstones fall. Change the starting number and notice how differently each one behaves before it lands.

Some numbers fall almost immediately. Others, like 27, bounce around for over a hundred steps and climb past 9,000 before finally coming down. There's no obvious reason a small, ordinary-looking number like 27 should take that long. That's the first hint of what makes this problem so hard: there's no visible pattern to when a number is "easy" or "hard."

Your neighbor's fate tells you nothing about yours

If a math problem is hard to prove directly, a common move is to look for structure: does the difficulty grow smoothly as the numbers grow? Is there a formula for how long a number takes to reach 1?

There isn't. Watch what happens as you scan through consecutive starting numbers.

Nudge the range up and down. You'll see numbers that finish in under ten steps sitting right next to numbers that take over a hundred. There's no ramp, no smooth curve, nothing you could fit a formula to. The number of steps a starting value takes to reach 1, mathematicians call this its stopping time, jumps around in a way that looks almost random, even though every single step is completely determined by simple arithmetic.

This matters because most proofs in number theory lean on some kind of pattern. Prove it for small cases, find the trend, extend it upward by induction. Collatz gives you nothing to extend. Knowing the stopping time of $n$ tells you almost nothing about the stopping time of $n+1$. Whatever proof exists here, it can't be "and so on, forever" reasoning. It has to be something else entirely, and nobody has found what that something else is.

We can argue it's true "on average". That's not the same as proving it.

Here's an argument mathematicians actually use to justify believing the conjecture, even without a proof.

Look at what happens to a number's size, roughly, at each step. If $n$ is even, it gets cut in half: multiply by $\frac{1}{2}$. If $n$ is odd, $3n+1$ is guaranteed to be even (an odd number times 3 is odd, plus 1 makes it even), so that odd step is always immediately followed by a halving. Combine those two moves into one "reduced step": an odd number roughly becomes $\frac{3n+1}{2} \approx \frac{3}{2}n$.

So every reduced step multiplies $n$ by roughly $\frac{1}{2}$ (if it was even) or roughly $\frac{3}{2}$ (if it was odd). If you assume, just as a rough model, that a number is equally likely to be even or odd at each step, the average effect per step is the geometric mean of those two factors:

That's less than 1. So on average, a number should shrink by about 13% per reduced step, which means, on average, every number should eventually drift down to 1. This is called the drift heuristic, and it's a genuinely useful piece of intuition. It's why almost every mathematician who works on this problem believes it's true.

But watch it against a real, specific number:

Notice the gap. The dashed line is what the "average" model predicts. The solid line is what one actual, deterministic number does. Sometimes they line up closely. Sometimes the real number overshoots the prediction by 40% or more, because that particular number happens to hit a long unlucky run of odd steps in a row.

And that's the whole problem with the heuristic. "On average" is a statement about randomness, and these numbers aren't random. Every single one is fixed and deterministic: 27 always does exactly what 27 does, forever. The drift argument tells you what a typical number should do. It says nothing, mathematically, about whether some specific number out there, maybe one with a billion digits, could be the one unlucky exception that climbs forever and never comes down. An average is not a guarantee. That gap between "usually true" and "always true" is exactly where the unsolved part of this problem lives.

Change the 3, and the whole thing falls apart

Here's a question worth sitting with: why $3n+1$ specifically? Why not $5n+1$, or $7n+1$? The halving rule for even numbers stays exactly the same. Only the multiplier for odd numbers changes.

Slide the multiplier up from 3 and watch what happens to the exact same starting number, 27. At $m=3$, it eventually settles down to 1. Push $m$ to 5 or 7, and the sequence either shoots off toward infinity or gets trapped in a completely different repeating loop that never touches 1 at all.

Run the same drift calculation from the last section, but with a general multiplier $m$ instead of 3, and you'll get an average shrink factor of $\sqrt{\frac{1}{2} \cdot \frac{m}{2}} = \sqrt{\frac{m}{4}}$. Plug in $m=3$ and you get roughly 0.866, safely under 1. Plug in $m=5$ and you get roughly 1.118, safely over 1. The number 3 sits right at the edge where this whole system tips from "should shrink" to "should grow." It's not an arbitrary choice baked into a famous problem. It's the specific constant that makes the outcome genuinely uncertain instead of obviously one thing or the other.

That's a real clue about why this is hard. A general proof technique that works for "any similar rule" can't exist, because most similar rules behave completely differently. Whatever proof eventually resolves the Collatz conjecture, it has to be sensitive to the exact arithmetic relationship between 2 and 3, not some broad principle about halving and multiplying. We don't currently have proof techniques that are that precise.

The closest anyone has come

The Collatz conjecture goes by other names too: the 3n+1 problem, the Syracuse problem, Kakutani's problem, Thwaites' conjecture. Different mathematicians in different countries ran into it independently in the 1930s through the 1950s, which is itself a sign of how naturally this question shows up once you start playing with number sequences.

Nobody has proven it. But in 2019, Terence Tao got closer than anyone before him. He proved that almost every starting number, in a precise statistical sense, eventually drops to a value extremely small compared to where it started. It's a genuinely major result, built on tools from probability and logarithmic density that hadn't been aimed at this problem before. But "almost every" isn't "every". There could still be a vanishingly rare exception hiding somewhere in the infinite set of whole numbers, one number Tao's method simply doesn't reach. That's the difference between the best partial result in ninety years and an actual proof.

There's an even stranger possibility on the table. In 1972, John Conway showed that generalized versions of Collatz-style rules, ones a bit more flexible than $3n+1$, can be built to simulate any computer program. That means a slightly broader question, does this particular number-iterating machine always halt, can be formally undecidable: not just unproven, but unprovable, in the same way the halting problem is unprovable in general. Nobody has shown that the original Collatz conjecture itself falls into that trap. But its cousins do, and that's unsettling enough that most people working on this problem take the possibility seriously.

It's a strange company to be in. The Collatz conjecture sits alongside problems like the Riemann hypothesis, a question that's easy to state and catastrophically hard to prove, where the gap between "we believe it" and "we've proven it" is doing a huge amount of work. If you want to get precise about what "proven" even means in mathematics, and why a mountain of checked examples never counts as one, our piece on mathematical proof walks through exactly that line.

The short version

Take any whole number. Halve it if it's even, triple it and add one if it's odd. Repeat. Every number anyone has ever tested, out past 295 quintillion of them, eventually reaches 1. Nobody has proven it happens for every number, and nobody has found one where it doesn't.

The difficulty isn't the arithmetic. It's that the rule mixes multiplication and addition in a way that erases any pattern to lean on: neighboring numbers don't share a fate, the "should shrink on average" argument is a statement about typical behavior and not a guarantee, and the whole outcome hinges on the razor-thin relationship between 2 and 3 specifically, not some general property you could prove once and reuse. It's a two-line rule that a ten-year-old can run by hand, and it has quietly defeated every proof technique mathematicians have thrown at it for almost a century.