The Collatz Conjecture: A Simple Rule Nobody Can Prove

The rule everyone can compute and nobody can prove

Take any positive integer n. If it is even, halve it. If it is odd, triple it and add one. Repeat. The Collatz conjecture — proposed by Lothar Collatz in 1937, and also known as the 3n+1 problem or the hailstone sequence — claims that no matter what number you start with, this process always eventually reaches 1:

n → n/2         if n is even
n → 3n + 1      if n is odd

Start at 27 and the sequence climbs to 9,232 before it ever comes back down, bouncing up and down like a hailstone caught in a storm cloud — hence the name — before finally landing on the repeating tail 4, 2, 1. Every integer ever tested, up into the range of roughly 2⁶⁸, eventually reaches 1. Nobody has found a counterexample, and nobody has proved there isn't one.

Why it's deceptively hard

The rule mixes multiplication and division in a way that resists the usual tools of number theory. Odd steps (3n+1) always produce an even number next, so you can fold the two rules together into one "accelerated" step for odd n: (3n+1)/2. Over many iterations the sequence behaves, on average, like it multiplies by roughly 3/4 each pair of steps — which suggests a downward drift toward 1 — but "on average" is not a proof, because any individual sequence could in principle defy the average for arbitrarily long, or diverge to infinity, or fall into some other repeating loop entirely that never touches 1. Paul Erdős reportedly said mathematics was not ready for this problem; it remains open today.

Stopping time and peak value

Two statistics describe a hailstone path: its stopping time, the number of steps to first reach 1, and its peak value, the highest number the sequence touches before descending. Neither is monotonic in the starting number — a small starting value can have a surprisingly long stopping time or a huge peak, and there is no known closed-form way to predict either without simply running the sequence. 27, a small number, takes 111 steps and peaks near 9,232; many larger starting numbers finish in far fewer steps. This unpredictability from such a simple rule is a large part of what makes the sequence visually striking to trace and mathematically resistant to attack.

The tree, run backward

Run the map in reverse and every number that reaches 1 forms a tree rooted at 1, branching outward: each node n has a child 2n always (undoing the halving step), and a second child (n-1)/3 whenever that value is a positive integer not divisible by 3 (undoing 3n+1 exactly when it applies). Visualizing this reverse tree is one of the standard ways to explore the conjecture, because a proof that the tree eventually contains every positive integer would be a proof of the conjecture itself — and, so far, nobody has found either that proof or a number missing from the tree.

What has actually been proven

Full generality remains open, but real progress exists. Every starting value up to about 2⁶⁸ has been exhaustively checked by distributed computing projects and reaches 1. Terence Tao proved in 2019 that "almost all" Collatz orbits (in a precise density sense) attain almost bounded values — a major partial result, though it stops short of a full proof for every integer. The conjecture also generalizes in ways that are provably false: variants of the 3n+1 rule with different multipliers can be shown to have starting numbers that diverge or fall into loops other than 4-2-1, which is a reminder that the truth of the original conjecture is a specific, delicate fact about the number 3, not a generic feature of this style of rule.

Frequently asked questions

Try it live

Everything above runs in your browser — open Collatz Conjecture and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.