- A child can follow the 3n+1 rule, yet nobody can prove it.
- Every integer tested up to 2^68 eventually reaches 1.
- Terence Tao's 2019 result is statistical, not a proof.
The Collatz conjecture is a famous unsolved problem in mathematics that asks whether one simple rule always ends at 1. Take any positive whole number; if it is even, halve it; if it is odd, multiply by 3 and add 1; then repeat. The conjecture says every starting number eventually reaches 1, yet no one has proved it since Lothar Collatz posed it in 1937.
Why It Matters
Key figure
1937
year Lothar Collatz posed the problem
The Collatz conjecture is the canonical example of a problem that is trivial to state and apparently impossible to prove. A ten-year-old can understand the rule in a minute. The world's mathematicians have failed to settle it for nearly ninety years.
That gap between simplicity and difficulty is the whole point. It is a standing reminder that an easy-looking statement carries no promise of an easy proof, a lesson it shares with several other deceptively plain questions in our piece on unsolved math problems that sound deceptively easy.
The Hungarian mathematician Paul Erdős captured the mood with a verdict that is still quoted. "Mathematics is not yet ready for such problems," he reportedly said, and he offered $500 to anyone who could solve it. The prize remains unclaimed.
It is worth knowing because it marks a boundary in what current methods can reach. Some hard problems eventually fall, as Andrew Wiles showed with Fermat's Last Theorem.
Others, like the Riemann Hypothesis, sit unproved for generations. Collatz belongs firmly in the second group.
How It Works
Key figure
2^68
integers verified to reach 1
The rule has only two branches. If the current number is even, divide by 2. If it is odd, multiply by 3 and add 1. You apply whichever branch fits and keep going.
Start at 6 and the sequence runs 6, 3, 10, 5, 16, 8, 4, 2, 1. Once a sequence hits 1 it falls into the loop 4, 2, 1, 4, 2, 1 forever, so reaching 1 counts as the finish. Every starting number tried so far ends this way.
Why it resists proof comes down to the tug-of-war inside the rule. Halving pulls numbers down, while the 3n+1 step pushes odd numbers up, and an odd step is usually followed by halvings. On average a sequence drifts downward, but "on average" is not "always," and proving it for every one of infinitely many starting numbers has defeated all comers.
Computers have checked an enormous range. Every positive integer up to about 2^68, roughly 2.95 times 10^20, has been verified to reach 1, with continued checking pushing even higher. That verification is not a proof, because it covers only a finite set; infinitely many larger numbers remain untested in principle.
The strongest progress came in 2019 from Terence Tao at UCLA, in a paper titled "Almost all orbits of the Collatz map attain almost bounded values." Using a probabilistic argument, he showed that almost all starting numbers, measured by logarithmic density, eventually drop to almost bounded values. It is a statistical statement about most numbers, not a proof that every number reaches 1, and Tao has suggested a genuinely new approach may be needed.
Key Context
Lothar Collatz, a German mathematician, posed the problem in 1937, two years after finishing his doctorate. The question has collected an unusual number of aliases since then: the 3n+1 problem, the Syracuse problem, the Ulam conjecture, Kakutani's problem, Hasse's algorithm, and the Thwaites conjecture. The crowd of names reflects how many mathematicians independently fell under its spell.
Partial results began arriving in the 1970s, showing that most sequences eventually drop below where they started. Ivan Korec set the strongest density record in 1994, and it stood until Tao surpassed it in 2019. No counterexample, meaning a number that runs to infinity or settles into a different loop, has ever turned up despite quintillions of tests.
FAQ
What is the 3n+1 rule and why is it so hard to prove despite being simple?
The rule is: if a number is even, halve it; if it is odd, multiply by 3 and add 1; then repeat. The difficulty is that halving pulls numbers down while the 3n+1 step pushes them up, so a sequence only drifts downward on average. Proving it falls to 1 for every one of infinitely many starting numbers, not just on average, has resisted all methods since 1937.
Has the Collatz conjecture been proven, and what does "verified up to 2^68" mean?
No, it has not been proven. Computers have checked every positive integer up to about 2^68 (roughly 2.95 times 10^20) and confirmed each one reaches 1. That is verification, not proof, because it covers only a finite range, and infinitely many larger numbers remain unchecked.
Did Terence Tao solve the Collatz conjecture in 2019, and what did his result actually show?
No, he did not solve it. Tao proved that almost all starting numbers, measured by logarithmic density, eventually reach almost bounded values, the biggest progress in decades. It is a statistical statement about most numbers rather than a proof covering every number, and a single divergent number or new loop would still disprove the conjecture.
Why does the Collatz conjecture have so many names?
Several mathematicians studied the problem independently and attached their own names to it. It is variously called the 3n+1 problem, the Syracuse problem, the Ulam conjecture, Kakutani's problem, Hasse's algorithm, and the Thwaites conjecture. The abundance of labels reflects how widely and separately the question spread.
What would a counterexample to the Collatz conjecture look like?
It would be a single starting number that never reaches 1. That could happen in two ways: the sequence runs off toward infinity without dropping back, or it settles into a repeating loop other than 4, 2, 1. No such number has been found despite quintillions of tests.
Related Reading
Sources
- Primary Sources:
- The Notorious Collatz conjecture (Terence Tao, UCLA)
- The 3N+1 Problem (T. Ian Martiny, University of Pittsburgh thesis)
- Additional Context:
- New Breakthrough in the 82-Year-Old Riddle Known as the Collatz Conjecture (Dartmouth Mathematical Society)
- Mathematician Proves Huge Result on "Dangerous" Problem (Quanta Magazine)
Fact Check: Claim-by-Claim Verification Verified
Independently verified by Claude and Perplexity (sonar-pro-search) across two rounds. All core mathematical claims supported against Terence Tao's writeup and arXiv paper, a University of Pittsburgh thesis, the Dartmouth Mathematical Society, and Quanta Magazine. Two quotation/title wordings were corrected before publication.
Sources used for verification
- The Notorious Collatz conjecture - Terence Tao (UCLA)
- The 3N+1 Problem - University of Pittsburgh thesis
- New Breakthrough in the 82-Year-Old Riddle - Dartmouth Mathematical Society
- Mathematician Proves Huge Result on "Dangerous" Problem - Quanta Magazine
