The Collatz conjecture: a simple rule nobody can prove
The Collatz conjecture says that if you start with any positive whole number and repeatedly halve it when it is even, or triple it and add 1 when it is odd, you will always reach 1. Computers have checked it for every starting number up to about 2.36 Γ 10Β²ΒΉ, yet nobody has proved it is true for all numbers. It remains one of the most famous unsolved problems in mathematics. The Collatz sequence calculator lets you follow any starting number, and this guide explains what is known.
The rule
Pick a positive integer n. If n is even, the next number is n Γ· 2. If n is odd, the next number is 3n + 1. Repeat. Once the sequence reaches 1, it would cycle 1 β 4 β 2 β 1 forever, so we stop there and count the steps taken. The problem is named after Lothar Collatz, who introduced it in 1937, and is also known as the 3n + 1 problem. The sequences are nicknamed hailstone numbers because they rise and fall repeatedly, like hailstones in a storm cloud, before finally dropping.
Following a few numbers
Start at 6: 6 β 3 β 10 β 5 β 16 β 8 β 4 β 2 β 1, which takes 8 steps. Start at 7 and the path wanders further: 7 β 22 β 11 β 34 β 17 β 52 β 26 β 13 β 40 β 20 β 10 β 5 β 16 β 8 β 4 β 2 β 1, which is 16 steps with a peak of 52. Powers of two are the easy case: 32 simply halves down to 1 in 5 steps.
Then there is 27. It takes 111 steps, 41 of them through odd numbers, and climbs as high as 9,232 before it finally falls to 1. Its neighbour 28 needs only 18 steps. Nothing about 27 looks special, which is exactly what makes the problem so strange: tiny changes in the starting number produce completely different journeys.
Hailstones and record holders
Because the paths are so irregular, people hunt for starting numbers with long journeys. I checked these with the calculator's record search:
- below 100, the longest path starts at 97 (118 steps, also peaking at 9,232, because its path joins the one from 27);
- below 1,000, it starts at 871 (178 steps);
- below 10,000, at 6,171 (261 steps);
- below 1,000,000, at 837,799 (524 steps).
Step counts grow slowly compared with the numbers themselves, which is one piece of evidence that the sequences really do tend to come down. Paths also merge: once two starting numbers hit the same value, they share the rest of the journey.
Why it is so hard to prove
There are only two ways the conjecture could fail. Some starting number could enter a loop that never reaches 1, or some sequence could grow forever. Ruling both out for every number is the hard part. A rough argument says the sequences should shrink: if you look only at the odd numbers in a sequence, each is on average about 3/4 of the previous one. But an average is not a proof, and the rule mixes multiplication by 3 with division by 2 in a way that existing tools struggle to control.
Paul ErdΕs put it memorably: "Mathematics may not be ready for such problems." There is even a reason to think simple-looking rules can be beyond reach: in 1972 John Horton Conway proved that a natural generalisation of the Collatz problem is undecidable, meaning no algorithm can settle every case.
What mathematicians do know
The conjecture has been verified by computer for all starting values up to 2β·ΒΉ, about 2.36 Γ 10Β²ΒΉ, and every one reaches 1. That is strong evidence, but not proof, since a counterexample could be larger still. The best theoretical result came in 2019, when Terence Tao showed that almost all starting numbers, in a precise statistical sense, eventually fall below any function of the starting value that grows to infinity, however slowly. That says a typical sequence comes down very far, while still leaving room for rare exceptions.
Exploring it yourself
The calculator works with whole numbers of any size, exactly, so you can try a 50-digit start and watch it come down. It shows the step count, the peak and how many steps were odd or even, with a log-scale chart of the path. Binary gives another view: halving an even number just removes a trailing zero from its binary form, as Binary, explained from zero shows, so the interesting steps are the 3n + 1 ones. The binary calculator lets you watch that happen, the big number calculator handles the arithmetic for huge starts, and the number sequence calculator explores other integer sequences. Pascal's triangle: the patterns hidden in a triangle of numbers covers another simple rule that hides deep patterns.
Sources and further reading
The claims in this guide rest on these references, which were checked when the guide was last updated. Spotted an error? The contact page says how to report it.