Topic · Chaos

The Collatz Conjecture

Halve if even. Triple-plus-one if odd. End at 1 — probably.

A four-word rule, eighty-eight years of silence. Pick any positive integer, halve it when it is even and otherwise replace it with 3n + 1, and the sequence eventually falls into the cycle 4 → 2 → 1. Computers have checked every integer up to roughly 2⁶⁸. Nobody has proved it must always happen.

Discover the story → Open the Explorer

First encounter

The simplest unsolved problem in mathematics.

The big idea

Pick any positive integer. If it is even, halve it. If it is odd, triple it and add one. Repeat. Every starting number we have ever tried eventually reaches 1. Probably. Nobody has proven it must. The whole rule fits in one breath and yet has resisted every attack for almost a century.

A concrete example

Start at 27 — a tiny seed. The orbit climbs and crashes and climbs again, peaking at 9 232 (about 340× its starting value) before finally falling back down to 1 in exactly 111 steps. Read the trajectory aloud and it sounds random; plotted on a log scale, it looks like hail in a thundercloud.

n = 27

111 steps · peak 9 232 · 340× the start

Why it matters

Verified by computer for every integer up to 2⁶⁸ — that is about 3 × 10²⁰ checks, no exceptions. Yet a proof is still missing. Collatz has become the shorthand for ‘easy to state, impossible to prove’. Paul Erdős shrugged and said: ‘Mathematics is not yet ripe for such problems.’ He offered $500. The prize is still unclaimed.

Below: drop any seed into the hailstorm and watch it fall — then grow the reverse coral that holds every integer at once.

Section 01 · The recipe

Two cases, one instruction

Pick any positive integer n. If n is even, replace it with n / 2. If n is odd, replace it with 3n + 1. Repeat. That is the whole rule. Try n = 7: 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1, and then 1 → 4 → 2 → 1 forever. The map T(n) is one of the smallest discrete dynamical systems anyone has ever written down. Children can iterate it. Computers can iterate it billions of times a second. Nobody knows whether every orbit really does come home.

Section 02 · The 27 trajectory

Hailstones over Syracuse

The orbits earned the nickname hailstone sequences because they rise and fall erratically before finally hitting the ground — like hail tossed inside a thundercloud. The most famous small case is n = 27. It looks too small to be interesting and yet it takes 111 steps to terminate, climbing as high as 9 232 along the way — over 340 times its starting value. Other small seeds with disproportionate orbits: 97 takes 118 steps, 871 takes 178, 6 171 takes 261, 77 031 takes 350. Tiny inputs, wildly oversized journeys. The trajectory plotter below lets you drop any of them — or any seed you like — into the hailstorm.

Interactive · trajectory plotter

Drop a seed, watch the hailstorm

Type any positive integer. The canvas draws the orbit on a log scale until it reaches 1 — marking the peak (cyan) and the landing point (amber). The famous seeds 27, 871, 6 171 and 77 031 are pre-set.

Interactive · trajectory plotter

Starting integer n

Famous seeds

Stopping time

111

Maximum height

9,232

Cyan ring = highest value reached along the orbit. Amber dot = the final 1. The y-axis is logarithmic so you can see the hailstones rise across orders of magnitude.

Section 03 · The conjecture

Every road leads to 4 → 2 → 1

Lothar Collatz wrote the rule down in 1937, two years after his doctorate in Berlin. The same beast was rediscovered independently by Kakutani, Ulam, and the Syracuse number theorists, which is why the literature also calls it the Syracuse problem, Kakutani's problem and the Ulam conjecture. The claim is the same in every name: for every positive integer n, the iteration T(n) eventually reaches 1, and then loops forever on the cycle 4 → 2 → 1. As of 2025 it has been verified by direct computation for every integer up to 2⁶⁸. No counterexample. No proof either.

Collatz · 1937

∀ n ∈ ℕ⁺ ∃ k ∈ ℕ : T^k(n) = 1

For every positive integer n there is a finite number of steps k after which T iterated k times lands on 1. Verified for n ≤ 2⁶⁸. Never proved.

Section 04 · Tao's 2019 result

Almost all orbits, almost all the way home

The deepest progress came in 2019 from Terence Tao. His paper ‘Almost all orbits of the Collatz map attain almost bounded values’ shows that for any function f(n) tending to infinity, the set of starting integers whose Collatz orbit eventually drops below f(n) has logarithmic density 1. In plain language: pick a random starting integer; almost certainly its orbit eventually shrinks below any target you set in advance. This is a probabilistic near-miss, not a proof. The remaining counterexamples — if they exist — would form a measure-zero exceptional set, but measure zero is not empty, and Tao's argument explicitly cannot rule them out.

Section 05 · The reverse coral

Run the rule backwards and the integers self-assemble

Forward Collatz is one number at a time. Reverse Collatz is the whole tree. Start at 1 and run the rule backwards: every node n has parent 2n (always — halving was its forward step), and additionally a parent (n − 1) / 3 whenever that number is a positive odd integer greater than 1. Sprout the tree breadth-first and the integers self-assemble into an infinite branching coral, rooted at 1, fanning outward. The Collatz conjecture is precisely the statement that every positive integer appears somewhere in this single tree — that the coral, eventually, contains them all.

Interactive · reverse coral tree

Run the rule backwards from 1

Every integer in the Collatz universe is somewhere in this tree — assuming the conjecture is true. Slide the depth knob and watch the coral fan outward from 1 at the centre. At depth 14 the tree already holds 79 integers.

Interactive · reverse coral tree

Reverse depth8

Integers reached17

Each node n branches to 2n always, and to (n − 1) / 3 when that yields an odd integer greater than 1. The colour cycles by depth — rose at the root, then amber, cyan, violet for finer detail.

Section 06 · What stops a proof

An invariant nobody has found

Why is this so hard? The deep reason is that no one has found a sufficient invariant. To prove every orbit terminates you need a quantity that strictly decreases along the iteration, or a Lyapunov function, or a clever potential — and nothing of the kind has surfaced in eighty-eight years of trying. John Conway proved in 1972 that a slightly generalised Collatz-like map is already undecidable; his later FRACTRAN system (1987) then realised full Turing-completeness in exactly this style of branching arithmetic. That suggests Collatz itself may live close to the boundary of undecidability: a problem that is not just hard but possibly outside the reach of any finite proof system. Erdős may have been right that mathematics is not yet ripe.

Erdős

“Mathematics is not yet ripe for such problems.”

Paul Erdős, offering $500 for a solution. Eighty-eight years after Collatz wrote down the rule, the prize is still unclaimed.

First encounter

Watch it fall.

The Explorer plots the hailstone trajectory of any starting number on a wider canvas and grows the same reverse coral beside a live stats panel. Everything you just read is one click away.

→ Open the Explorer

Where you meet it

How and where this technique lives in the world today.

Pure mathematics open problem

Listed as one of the most famous open problems in elementary number theory; verified by computer to 2.95×10²⁰ as of 2024.

Distributed computing

The BOINC / collatzconjecture.org project crowdsources the search for a counterexample using volunteer GPU time.

Pedagogy

Used in middle-school 'number tricks' demonstrations and in undergraduate research projects on integer sequences.