The Collatz Conjecture

Pick any whole number you like. Now follow two rules. If it is even, cut it in half. If it is odd, triple it and add one (the famous 3n+1). Apply the rules again to whatever you get, and again, and again.

Try 6: it goes 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1. Try 27 and you climb past 9,000 before crashing back down — 111 steps later you also reach 1. The numbers bounce up and down like hailstones in a storm cloud, which is why they are called hailstone sequences.

The Collatz conjecture, posed by Lothar Collatz around 1937, says the same thing happens for every starting number: sooner or later you always fall into the loop 4 → 2 → 1. It has been checked by computer for every number up to roughly $2^{68}$ (about 295 quintillion). Not one escapes. And yet, nearly ninety years on, nobody has proved it must always work.

Type any starting number and run it. Watch the sequence shoot up, plunge, and eventually hit 1 — and see its peak (the highest value reached) and its stopping time (how many steps it took).

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>{{label_start}} <input id="seed" type="number" min="1" value="27"></label>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="lucky" type="button" class="ghost">{{btn_random}}</button>
  <button id="scan" type="button" class="ghost">{{btn_scan}}</button>
</div>
<div class="stats" id="stats">{{stats_initial}}</div>
<canvas id="plot" width="460" height="180"></canvas>
<div class="seq" id="seq"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .6rem; }
label { font-size: .9rem; font-weight: 600; }
input { width: 90px; font: 600 14px system-ui; padding: .35rem .5rem; border: 1px solid #adb1b8; border-radius: 8px; margin-left: .3rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.stats { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; color: #1d3557; }
.stats.ok { color: #0a7d33; }
canvas { width: 100%; max-width: 460px; height: auto; background: #f3f6f9; border: 1px solid #cdd9e3; border-radius: 8px; display: block; }
.seq { font: 600 12px ui-monospace, monospace; color: #45586a; margin-top: .5rem; word-break: break-word; line-height: 1.5; }

// Code not found

Notice the asymmetry. Checking one number is effortless: the computer just applies the rules until it reaches 1, and it always does — quickly. But proving that every number behaves this way is something no chain of single checks can ever finish. Try the Scan 1–10000 button: thousands of starts, every one lands on 1. That is overwhelming evidence — and still not a proof.

How hard is Collatz, really? Not running it — proving it.

• Checking one number is easy: apply the rules until you hit 1. For everything tested so far this halts fast, and verifying a single trajectory is cheap.
• Proving it for all numbers is an open problem — unsolved since Lothar Collatz first posed it around 1937. The legendary Paul Erdős offered $500 for a solution and remarked, "Mathematics is not yet ready for such problems."
• It may be more than just hard. In 1972 John Conway studied generalized Collatz-style maps and proved that deciding their behavior is undecidable — there is no algorithm that settles every such problem, a direct cousin of the halting problem. The classic 3n+1 case isn't proven undecidable, but it lives in that dangerous neighborhood.
• The best partial result: in 2019 Terence Tao proved that almost all Collatz orbits reach values that are almost bounded — astonishingly close, yet still short of "all numbers reach 1."

That is the punchline: a rule a ten-year-old can apply has defeated the finest minds for nine decades. The gap between "we checked $2^{68}$ numbers" and "we proved it for all of them" is the same gap that separates evidence from certainty — the heart of why some questions, like P vs NP, stay open.

A problem with no obvious "use" has quietly shaped a lot of mathematics and computing:

• Dynamical systems: Collatz is the cleanest example of a simple deterministic rule whose long-term behavior is wildly unpredictable — a toy model for chaos and ergodic theory.
• Undecidability research: Conway's generalized version connects elementary arithmetic to the halting problem, showing how easily "harmless" rules become unsolvable.
• Number theory: attacks on Collatz have spawned new tools in analytic and probabilistic number theory, including Tao's near-miss result.
• Computing stress tests: the worldwide hunt verifying numbers past $2^{68}$ is a benchmark for big-integer arithmetic, GPU search and distributed volunteer computing.

Understand Collatz and you understand a deeper truth: simplicity of statement says nothing about difficulty of proof — the same lesson behind the hardest questions in computability and complexity.

The Collatz conjecture is mathematics at its most humbling. The rule fits on a napkin. A computer confirms it for hundreds of quintillions of numbers without a single exception. Verifying any one case takes a heartbeat. And still, no proof exists that it works for all numbers — and there may be a deep reason it resists us, given how its generalizations slide into undecidability.

So the next time someone tells you a problem is "obviously true," remember the hailstones. Easy to state, easy to check, brutally hard to prove — that chasm is exactly where the deepest questions in computation, from P vs NP to the halting problem, make their home.