The Collatz Conjecture

Take any positive whole number. If it is even, halve it. If it is odd, multiply it by three and add one. Now apply the same rule to the result, and keep going. The Collatz conjecture says that whatever number you start from, the sequence always reaches 1. Nobody has been able to prove it.

Try it with 7. You get 22, then 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Sixteen steps, done. Start from 27 instead and something stranger happens: the sequence climbs to 9,232 before collapsing, and takes 111 steps to land. Values produced this way are called hailstone numbers, because they rise and fall like hailstones in a storm cloud before finally hitting the ground. The demo above draws that flight for any number you give it, up to 30 digits. Type 27 and watch.

Where it came from

The conjecture carries the name of Lothar Collatz, a German mathematician who filled his student notebooks with iteration problems in the 1930s. The date usually attached to it is 1937. The paper trail is thinner than that suggests: Collatz published nothing about the problem at the time, and in later life he was careful not to claim he had invented it outright. What is certain is that he worked on rules of exactly this kind, and that this one spread through the mathematical world by word of mouth for decades before anyone wrote it down properly.

That travel history explains the aliases. At Syracuse University it became the Syracuse problem. Stanisław Ulam passed it around Los Alamos, so some older texts call it Ulam’s problem. Shizuo Kakutani spread it through Yale and Chicago in the 1960s, where it ate so many research hours that he joked it had been planted to slow American mathematics down. Nothing appeared in print until the early 1970s. By then the problem was already notorious.

What has actually been proved

Less than you might expect after nearly ninety years. The honest answers come in two kinds: brute computation and probabilistic theory.

Computation first. David Barina at the Brno University of Technology runs a distributed verification project that has checked every starting value below 2^71, roughly 2.4 sextillion numbers. Every single one reaches 1. That milestone was reached in January 2025, with GPU code spread across thousands of parallel workers on European supercomputers, and the same run turned up four new path records, starting values whose flights climb higher than any smaller start manages.

As evidence, this is worth something. As proof, it is worth nothing. The integers never run out, and mathematics has a history of conjectures that held for astronomically many cases before failing. A counterexample the width of the observable universe in digits would falsify Collatz just as thoroughly as a small one.

The theory is where Terence Tao comes in. In 2019 he proved a result titled “Almost all orbits of the Collatz map attain almost bounded values”. In plain terms: pick a starting number at random and, with overwhelming likelihood, its sequence will eventually drop below any slowly growing threshold you care to name. Almost every number falls almost all the way down. Mathematicians regard this as the strongest theoretical progress ever made on the problem. It still leaves the conjecture itself untouched, because “almost all” is not “all”, and a stubborn family of exceptions could hide in the gap.

Paul Erdős put up $500 for a solution and, as Jeffrey Lagarias records in his survey of the problem, remarked that “Mathematics is not yet ready for such problems.” That was decades ago. The consensus has not moved.

Why such a simple rule is so hard

The trouble starts with a clash of number systems. Halving is a natural operation in base 2: it removes a zero from the end. Tripling is natural in base 3. The Collatz rule welds the two together, and no known technique can track what repeated tripling-plus-one does to the binary digits of a number. Each step scrambles whatever structure the previous step exposed.

Worse, the sequences behave like random walks. An odd step multiplies by three and adds one, but the result is always even, so at least one halving follows, and on average enough halvings follow to shrink the number overall. A back-of-envelope argument therefore says a typical sequence should drift downwards, which matches what the demo shows you. But an average says nothing about the worst case. And induction, the standard tool for statements about all whole numbers, gets no grip here: the sequence starting at 27 soars past 9,000, so knowing the fate of every number below 27 tells you nothing about 27 itself.

Why a computer science site cares

The Collatz function reads like a three-line computer program, and the resemblance runs deep. In 1972 John Conway studied generalised Collatz functions, rules that apply a different linear operation depending on the remainder of the current value. He proved that such functions can simulate any computer program whatsoever. His later invention FRACTRAN, a programming language whose programs are nothing more than lists of fractions, is a Turing-complete descendant of the same idea.

The consequence is blunt: no general method can decide whether an arbitrary Collatz-like rule sends every number to 1. A method that could would also solve the halting problem, which Turing proved impossible in 1936. The original 3n+1 rule is one fixed instance, so the theorem does not condemn it; a proof may yet exist. But any technique powerful enough to settle all of its cousins in one sweep provably cannot exist. Researchers hunting for a general engine run straight into the wall Turing built, the same one that shaped the foundations era of the field.

The problem also keeps surfacing inside small machines. Hunt for the busy beaver numbers and you find that some of the smallest Turing machines whose halting behaviour remains unresolved are, on inspection, computing Collatz-like iterations. The simplest open problem in arithmetic and the simplest open problems in computation appear to be the same animal seen from two sides.

Record flights

Among starts below 100, 27 is the famous one: 111 steps, a peak of 9,232, more than 340 times where it began. The champion below 10,000 is 6,171, which needs 261 steps. Both are presets in the demo, and the shape of their flights, a long ragged climb followed by a sudden collapse, is typical of record holders. At the top end, Barina’s verification project tracks path records among numbers of twenty or more digits, and every one of them still comes down.

What would settle it

A proof must show that every positive integer, without exception, reaches 1. A disproof needs one of two things: a sequence that grows forever, or a cycle other than the 4, 2, 1 loop at the bottom of every known flight. Below 2^71 neither exists, so any counterexample is a number far beyond anything you would type by accident. The demo gives up after 100,000 steps. If you ever hit that ceiling with a genuine number, check your input carefully, because a real ceiling hit would be the most famous counterexample in modern mathematics.

There is money on the table too. In July 2021 the Japanese company Bakuage offered 120 million yen, around a million US dollars at the time, for a resolution either way, with the rules published at mathprize.net. No award has been announced. Erdős’s $500 also stands unclaimed after half a century.

So the state of play is this: every number anyone has ever tried falls to 1, and nobody can say why. The demo above will take any number up to 30 digits if you fancy a go. So far, the conjecture always wins.