The rule is among the simplest in mathematics. Take any positive integer . If is even, divide it by . If is odd, multiply by and add . Now repeat the rule on whatever number you just got. Keep going.
Start with . You get . Once you hit , the rule cycles you through forever. Start with . You get . Sixteen steps and you are back at again.
Try any other positive integer you like. Five, eleven, a hundred, a million. Every single one, eventually, falls into the cycle . The Collatz conjecture, posed by Lothar Collatz in 1937, is the statement that this is always true:
Starting from any positive integer and applying the rule repeatedly, you will eventually reach .
That is the entire conjecture. It is among the easiest mathematical problems to state — comprehensible to a curious twelve-year-old — and it is among the hardest to prove. Nearly ninety years after Collatz wrote it down in his notebook, no one has any idea how to settle it. This article is about why the problem is so hard, and about a single trajectory — the most famous one — that shows the strangeness of what we are facing.
The trajectory of 27
The number looks no different from any other. It is odd, so the rule starts off badly: triple it and add one to get . Halve to , triple-plus-one to , halve to , halve again to , and so on. The most striking feature of the trajectory becomes apparent only after dozens of steps: the numbers do not go down. They wander up and down — but mostly up — for a very long time. The trajectory peaks at , more than three hundred times the starting value, before finally collapsing all the way to .
The picture shows the trajectory on a logarithmic scale. The visible structure — a noisy upward drift for two-thirds of the journey, then a steep collapse — is typical of Collatz trajectories that go high. There is no smooth pattern, no obvious force pulling the trajectory back down, no place where you can point at the curve and say “now it has to come back.” It just does, eventually. And for every starting number anyone has tried, it does the same.
Why is this hard?
The reason the conjecture has resisted proof is the asymmetry of the two operations. Halving cuts a number’s size in half. Tripling-plus-one nearly triples it. So on average each odd step makes the number grow by a factor close to , and each even step makes it shrink by a factor of . After many steps you expect a mix of about half evens and half odds. The expected multiplicative growth per step is then roughly , so on average a Collatz trajectory should shrink in the long run. This heuristic argument predicts that nearly every trajectory should eventually reach — and the empirical evidence is overwhelming. Every positive integer up to about has been individually verified.
But none of this is a proof. Average behaviour does not preclude a single rogue trajectory that grows forever, or a single cycle other than that some starting value falls into and never escapes. To prove the conjecture you would have to rule out every such bad trajectory and every such bad cycle for every one of the infinitely many starting points, and the techniques mathematicians have for ruling out such things — congruence arguments, divisibility, generating functions, analytic number theory — all seem to have nothing to grip onto here. The reason is that the rule mixes additive structure (“add 1”) with multiplicative structure (“multiply by 3” and “halve”), and there is no algebraic mechanism that handles both at once cleanly. As Paul Erdős reportedly put it: “Mathematics is not yet ready for such problems.”
Some progress that is not progress
A handful of partial results have been proved. No non-trivial small cycles exist: any other cycle would have to have length at least , which essentially rules them out for any practical starting value. Almost every trajectory comes close to its starting value at some point — a theorem of Terence Tao from 2019, which is the strongest general result so far, but which still leaves open the existence of single counterexamples. The set of starting values that are not eventually mapped below has been shown to be very thin, in a precise statistical sense. None of this proves the conjecture.
Meanwhile small variants of the rule turn out to be undecidable. John Conway showed in 1972 that a generalisation of Collatz, in which different residue classes mod some integer trigger different linear maps, can simulate any computer program. The halting problem for such generalised Collatz rules is therefore undecidable: there is no algorithm that takes a starting number and a rule and answers “does it always reach 1?” Whether the specific rule is decidable remains unknown, but Conway’s result is a warning sign. Some Collatz-like problems are genuinely beyond the reach of any algorithm, and the boundary between provable and unprovable is closer than mathematicians are comfortable with.
A small piece of cultural mathematics
The Collatz conjecture has acquired a peculiar cultural fame. It has been the subject of an XKCD comic (“The Collatz Conjecture states that if you pick a number, and if it’s even divide it by two and if it’s odd multiply it by three and add one, and you repeat this procedure long enough, eventually your friends will stop calling to see if you want to hang out”), of computer-science memes, and of a steady stream of amateur proofs that always turn out to be wrong. The reason it is famous outside professional mathematics is the same reason it is hard inside: the problem feels close to a child’s puzzle, and the surprise of its difficulty is part of the charm.
There is a deeper lesson behind that surprise, however. Number theory has a long history of problems that look elementary but turn out to be deep. The infinitude of primes (proved by Euclid) is elementary; the twin prime conjecture (are there infinitely many primes that differ by ?) is not. The fact that integers factor uniquely into primes is elementary; the Goldbach conjecture (every even integer is a sum of two primes) is not. The Collatz conjecture is the modern champion of this tradition, a problem whose statement and difficulty have no relation to each other.
What it teaches, in the end, is humility. The integers — that we have been calculating with since childhood, that classical mathematics has been studying for three thousand years — still contain mysteries that the current state of the art is helpless to resolve. The next major breakthrough on the Collatz problem may come from a high-school student who notices what generations of professionals have missed, or from a new branch of mathematics that we have not yet invented. Either way, it will be one of the most celebrated proofs of the century. Until then, the rule for odd and for even remains a tiny, perfect mystery: easy to play with, hopeless to settle, sitting quietly in plain sight.
Frequently asked
Who first posed the Collatz problem?
The German mathematician Lothar Collatz, in 1937, while still a graduate student at the University of Hamburg. He wrote it in his notebook but never published it formally. The problem circulated by word of mouth for decades and accumulated several alternative names — Ulam's conjecture, Kakutani's problem, the Syracuse problem, the hailstone sequence — before settling on Collatz's own name in the 1980s. It is now widely regarded as one of the simplest open problems in mathematics, in the sense that anyone can understand the question, and one of the hardest, in the sense that no one knows how to answer it.
How far has the conjecture been checked?
Every positive integer up to about 2.95 × 10²⁰ — verified by a distributed computing project completed in 2020. That covers a few hundred million-million-million numbers, all of which reach 1. The verification proves nothing on its own, since the conjecture asserts something about every positive integer, but it gives massive empirical support and rules out simple counterexamples. If a number that does not reach 1 exists, it must be larger than any number a human has ever needed for any purpose, which is part of what makes the problem feel so close yet so hard.
What did Paul Erdős say about it?
Erdős offered 500 dollars for a proof and is widely reported to have said, 'Mathematics is not yet ready for such problems.' His judgement, after a lifetime in number theory, was that the techniques mathematicians currently possess are simply inadequate to attack this kind of question. The conjecture sits in a region of mathematics where the tools that solve other problems — divisibility, congruences, generating functions, analytic estimates — seem to have nothing to grip onto. The problem is too elementary to be approachable.
What is the connection to undecidability?
John Conway showed in 1972 that a small generalisation of the Collatz problem — replacing the specific rule '3n + 1' with a family of similar piecewise-linear rules — is undecidable: there is no algorithm that can determine, for an arbitrary such rule, whether all starting numbers eventually reach 1. His construction, called FRACTRAN, can in fact simulate any computer program at all. This suggests that the Collatz problem itself may not be merely hard but may sit close to the boundary of what is provable in principle, even though that has never been demonstrated for the specific 3n + 1 rule.