The Collatz Conjecture: The 3n + 1 Problem

The rule, stated precisely

Define the Collatz function T: ℕ → ℕ on the positive integers by a single branch on parity:

T(n) = n/2  if n is even,    T(n) = 3n + 1  if n is odd.

Starting from a seed n₀, iterate: n₁ = T(n₀), n₂ = T(n₁), and so on, producing the Collatz orbit (or hailstone sequence) n₀, n₁, n₂, … . The conjecture is the single sentence:

For every n ∈ ℕ, there exists a k with Tᵏ(n) = 1.

Once you hit 1 the orbit is trapped in the cycle 1 → 4 → 2 → 1 → 4 → … forever, so "reaching 1" is the same as "falling into the only known cycle." The conjecture goes by many names — the 3n + 1 problem, the Ulam conjecture, the Syracuse problem, Kakutani's problem, or Thwaites' conjecture — because it was rediscovered independently many times. Notice the whole thing lives in exact integer arithmetic: there is no rounding, no approximation, no ε anywhere. That is precisely what makes its stubbornness so unsettling.

A worked example: the orbit of 27

Small seeds fall to 1 almost immediately (n = 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1, done in 8 steps). But the modest-looking seed n = 27 is the classic showpiece. Watch it climb before it crashes:

27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → …

It keeps rising, peaking at the value 9232 — over 340 times its starting value — before finally tumbling all the way down. The total stopping time (steps to reach 1) is 111. This is the whole drama of the problem in one number: a tiny odd seed launches a long, erratic ascent, yet still lands on 1. Every odd step 3n + 1 pushes upward, every even step n/2 pulls down, and — mysteriously — the pulls always win in the end.

Why it (probably) works: the heuristic drift

Here is the intuition that makes almost every mathematician believe the conjecture even without a proof. Track only the odd numbers, using the Syracuse map: when n is odd, 3n + 1 is even, so we can immediately divide out all factors of 2 at once. The next odd number is (3n + 1)/2ᵛ, where 2ᵛ exactly divides 3n + 1.

How big is v typically? A "random" even number is divisible by 2 with probability ½, by 4 with probability ¼, by 8 with probability ⅛, … so the expected number of halvings is ∑ k·2⁻ᵏ = 2. In other words, each odd step multiplies by 3, adds a negligible 1, and then on average divides by 4. The expected multiplicative change per odd step is therefore about

(geometric mean) ≈ 3¹ · 2⁻² = 3/4 < 1.

Since 3/4 < 1, orbits shrink on average by a constant factor per odd step — they drift geometrically downward. A random walk with negative drift returns to the bottom with probability 1, which is exactly why we expect every orbit to reach 1. The precise version of "downward on average" uses ∑ (log 3 − k·log 2)·2⁻ᵏ = log 3 − 2·log 2 = log(3/4) < 0. This is a heuristic, not a proof: the integers are not actually random, and a single unlucky orbit that never came back down would sink the whole conjecture.

The reverse tree: growing every number from 1

Flip the picture. Instead of asking where n goes, ask what maps into n. Running T backwards, m ↦ 2m always works (doubling is the inverse of halving), and additionally m ↦ (m − 1)/3 works precisely when m ≡ 4 (mod 6), i.e. when (m − 1)/3 is a positive odd integer. Applying these two rules starting from 1 grows the Collatz graph:

• 1 comes from 2 (double)
• 2 comes from 4
• 4 comes from 8 — and also from 1, but 1 is the root, so we branch elsewhere
• 16 comes from 32 and from 5 (since (16 − 1)/3 = 5)

Because doubling always applies and the 3n+1 inverse applies only sometimes, this reverse structure is an infinite tree — every node has one "double" child and occasionally a second "odd" child. The Collatz conjecture is exactly the statement that this single tree, rooted at 1, contains every positive integer — that nothing is left orphaned in a separate cycle or a runaway branch to infinity. Restated this way, the problem becomes a question about reachability in one enormous connected graph.

What is actually known (and what is not)

Progress is real but partial. The headline results:

• No other cycles are small. Any nontrivial cycle besides 1 → 4 → 2 → 1 must be astronomically long — Eliahou (1993) proved the minimum cycle length exceeds ≈ 17 million, and later computation has pushed that bound above ≈ 10 billion, yet no such cycle has ever been found.
• No divergence up to huge bounds. Direct computation has verified that every seed up to about 2.95 × 10²⁰ eventually reaches 1 (Barina, 2020). That is roughly 295 quintillion starting values, all confirmed.
• Almost every orbit gets small. Terence Tao proved in 2019 that for almost all n (in a strong logarithmic-density sense), the orbit of n eventually drops below any prescribed slowly-growing function f(n) → ∞. This is the closest anyone has come — but "almost all" still leaves a measure-zero set of possible counterexamples uncontrolled.
• Undecidability of relatives. John Conway showed that natural generalizations of the 3n+1 map (his FRACTRAN-style systems) are Turing-complete and their reachability questions are undecidable. This hints at why the specific 3n+1 case is so slippery: it sits right at the edge of computational chaos.

What remains open is the whole thing: a proof that no seed diverges to ∞ and no seed enters a cycle other than the trivial one. Both must be ruled out for all of ℕ.

Why it matters, and a common trap

Why care about a rule with no application? First, because it exposes a fault line in mathematics: it connects the additive world (adding 1) with the multiplicative world (dividing by 2, tripling), and we have almost no tools that respect both at once. The same tension underlies deep open problems throughout number theory. Second, it is a proving ground for dynamics, ergodic theory, and heuristic-vs-rigorous reasoning — Tao's partial result imported serious machinery from probability and analysis.

The common misconception is that heavy computer verification — 2.95 × 10²⁰ seeds and counting — somehow "almost proves" it. It does not, and the gap is not a technicality. Sequences in number theory can behave perfectly for astronomically long stretches and then fail: the Pólya conjecture held until a counterexample near 906,150,257, and Skewes' number shows a sign change in π(x) − li(x) that computation could never have reached. A single divergent Collatz orbit, or one hidden high cycle, anywhere in the infinite tail of ℕ would falsify the conjecture — and no finite search can ever certify infinitely many integers. That is exactly why, after nearly 90 years, the honest last line remains: nobody has proved it always terminates.

Two ways to describe the same iteration: the raw Collatz map T vs the accelerated Syracuse map that skips over the forced halving after every odd step.

Aspect	Collatz map T(n)	Syracuse map (odds only)
Rule	n/2 if even; 3n + 1 if odd	(3n + 1)/2ᵛ where 2ᵛ ‖ 3n+1
Domain	all n ∈ ℕ	odd n ∈ ℕ only
Fate of 3n+1	written out, then halved next step	halving folded in immediately
Terminal fixed point	1 (via 4 → 2 → 1)	1
Best for	hailstone plots, stopping times	heuristics, average-drift arguments