The Collatz conjecture

Pick any whole number, say 6, and follow two rules. If the number is even, cut it in half. If it is odd, triple it and add one. Then repeat. Starting from 6 you get 6, 3, 10, 5, 16, 8, 4, 2, 1. You land on 1. The Collatz conjecture says this always happens: whatever number you start with, you eventually fall to 1.

The numbers bounce around wildly on the way, climbing and dropping like hailstones tossed in a storm cloud before they finally fall. Start at 27 and the sequence shoots up past nine thousand and takes 111 steps to come home. There is no way to tell from a number where it will go. You just have to run it and watch.

Here is the twist. This may be the simplest unsolved problem in all of mathematics. A child can do the steps, and computers have tested every starting number up to a 2 followed by twenty-one zeros, with every single one falling to 1. Yet nobody has ever proved that some number, somewhere, could not climb forever or get stuck in a different loop. The famous mathematician Paul Erdős looked at it and said mathematics may simply not be ready for such a problem.

The rule is as simple as mathematics gets. Take any positive integer. If it is even, divide by 2; if it is odd, multiply by 3 and add 1. Repeat. The Collatz conjecture, posed by Lothar Collatz around 1937, claims that every starting number eventually reaches 1, after which it falls into the short loop 4, 2, 1.

The journey there is erratic. The values rise and fall so unpredictably they are called hailstone numbers, and the count of steps to reach 1 follows no formula. Starting from 27, the sequence climbs above 9000 and takes 111 steps to come down. Despite this wildness, computers have verified the conjecture for every starting value up to 2 to the 71st power, about 2.36 times 10 to the 21st, without a single number failing.

There is a good heuristic for why it should be true. Each odd step, 3n plus 1, always lands on an even number, so it is immediately followed by at least one halving. Treating the numbers as effectively random, each step multiplies the value by 3/2 about half the time and by 1/2 the rest, and the long-run average works out to a shrinking factor below 1. On average, then, sequences should drift downward and collapse to 1. But an average is not a guarantee. Nothing in that argument rules out a single stubborn number that climbs forever, or one that settles into some other repeating loop we have never seen.

The strongest real progress is a 2019 result by Terence Tao, who proved that almost all starting numbers eventually reach a value very close to their smallest possible, in a precise statistical sense. It is the closest anyone has come, and it still falls short of the full conjecture, because almost all is not all.

The deepest surprise is the mismatch between how trivial the rule looks and how immovable the problem is. Paul Erdős, one of the most prolific mathematicians who ever lived, offered a prize for a solution and remarked that mathematics may not be ready for such problems. He may have been right in a deeper way than he knew.

State it as a dynamical system and the structure clarifies. Define T on the positive integers by \(T(n) = n/2\) for even n and \((3n + 1)/2\) for odd n, folding the forced halving into the odd step. The conjecture asserts that the orbit of every n under iteration of T eventually reaches 1. Equivalently, two things must hold for all starting values: no orbit diverges to infinity, and no orbit falls into a nontrivial cycle other than the one through 1.

Stochastic heuristics predict convergence with probability one. Model the parity of successive iterates as fair independent coin flips. An odd step multiplies by \(3/2\) after the forced division, an even step by \(1/2\), so the expected change in log per step is one half of \(\log(3/4)\), which is negative. Orbits therefore drift downward geometrically on average, and the Lagarias-Weiss stochastic models make this precise, predicting a definite distribution of stopping times. None of this constrains any individual orbit, where the actual powers of 2 dividing each term are deterministic, not random.

Density results prove the conjecture for almost all integers. Riho Terras showed in 1976 that almost all n, in natural density, reach a value below n. Refinements by Allouche, Korec, and others sharpened how far almost all orbits descend. The current high point is Terence Tao's 2019 theorem that almost all Collatz orbits, in the sense of logarithmic density, attain almost bounded values: for any function f tending to infinity, the orbit minimum of n lies below \(f(n)\) for almost all n. This is the strongest evidence short of a proof, but density one is not all, and a sparse exceptional set could still misbehave.

Cycles and divergence are constrained but not excluded. Direct computation has verified convergence for every n up to \(2^{71}\), and theoretical work bounds any hypothetical cycle severely: results in the tradition of Eliahou give large lower bounds on cycle length, and recent work rules out nontrivial cycles with few enough runs, showing there are no Collatz m-cycles with m at most 91. Yet no argument forbids a single divergent trajectory or an astronomically long cycle above the searched range.

Generalizations are provably undecidable. John Conway showed in 1972 that natural generalizations of the Collatz map, piecewise-linear maps with different moduli, are Turing-complete; his FRACTRAN language encodes arbitrary computation in exactly this style. For such generalized 3n + 1 functions there is no algorithm to decide whether all orbits reach 1, since the question is equivalent to the halting problem. The specific Collatz map is not known to be undecidable, but it sits inside a family that is, a strong hint about why elementary techniques fail.

The orbits are deterministic yet statistically random. There is no closed form for the stopping time and no shortcut to an orbit's fate other than running it. Empirically the trajectories pass standard tests of randomness, and the stopping-time data show fractal, modular structure rather than simplicity. The problem pits an expanding map, 3n + 1, against a contracting one, division by 2, and the conjecture is the claim that contraction always wins in the end, despite excursions like 27's climb above 9000.

And here is what the Collatz conjecture really exposes. The rule is small enough to teach in a sentence, yet it generates behavior indistinguishable from chaos, governed by no formula and predictable only by brute simulation, and every one of the more than two sextillion numbers tested still drains to 1. The trouble is that simplicity of statement says nothing about depth of difficulty. The map's own generalizations are equivalent to the halting problem, so the wildness may be essential rather than incidental, a shadow of undecidability falling across a problem a child can pose. Paul Erdős offered money for a proof and judged that mathematics was not ready for such questions. Decades later, the tiny rule that triples and halves sits exactly where he left it, simple, relentless, and unproven.