How to read this page. Throughout, n is a positive integer (n ∈ ℕ, n ≥ 1). The central object is the Collatz map T, which sends an even number to its half and an odd number to 3n+1. Applying T over and over produces the orbit (or trajectory) of n: the sequence n, T(n), T(T(n)), …. We write Tk(n) for the k-fold iterate. "Reaches 1" means some iterate equals 1, after which the orbit falls into the cycle 1 → 4 → 2 → 1 forever. v2(m) denotes the 2-adic valuation: the exponent of the highest power of 2 dividing m. "Density" statements count how common a property is among integers up to a bound; they are statements about almost all integers, not all. Keep that distinction in mind: it is the fault line this whole subject runs along. Nothing on this page is a proof of the conjecture; it is an honest map of what is known and precisely where the knowing stops.
0 · The claim, in one line
Iterate "halve if even, else triple and add one" from any positive integer, and you will always land on 1.
T(n) = n⁄2 if n ≡ 0 (mod 2), T(n) = 3n+1 if n ≡ 1 (mod 2)The Collatz map. The conjecture asserts: for every n ≥ 1 there is some k with Tk(n) = 1.
That is the entire statement. A child can compute it; no one on Earth can prove it. Take n = 6: 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1. Take n = 27 and the orbit climbs to 9232 and wanders through 111 steps before collapsing to 1. The rule is deterministic and trivial; the behavior is, as far as anyone can prove, wild.
1 · The object: what it is and why anyone cares
The Collatz conjecture is the simplest-looking open problem in mathematics that resists every serious tool we have. That is the whole point of caring about it. It is not deep because it is useful; it is deep because it exposes, with almost insulting clarity, how little we understand about the interaction between the two most basic operations we teach children: multiplication and addition living inside divisibility.
Chase the "why" to its root and you arrive here: the map mixes a multiplicative structure (tripling, and the powers of 2 you divide out) with an additive perturbation (the "+1"). Pure multiplication by 3 and pure division by 2 are perfectly understood: they are just arithmetic in the exponents of primes. It is the +1 that destroys everything. It couples the base-2 structure of n to the base-3 structure of 3n in a way that scrambles the prime factorization completely at every odd step. There is no known algebraic invariant, no conserved quantity, no modular obstruction, no monotone measure that survives iteration. The orbit of n is, operationally, a pseudo-random walk that we nonetheless believe is secretly tame.
Why anyone cares, stated plainly: if a problem this short can be this impervious, then our theory of how arithmetic operations interact is missing something structural, not merely technical. Paul Erdős put it with his usual economy: "Mathematics may not be ready for such problems." He attached a $500 prize, which has never been collected. The conjecture is a diagnostic, a canary: it tells us a whole class of "iterate a simple arithmetic rule" questions (what dynamicists now call arithmetic dynamics) sits beyond the current frontier.
It has accumulated names because it was reinvented repeatedly: the 3n+1 problem, the Syracuse problem, Hasse's algorithm, Kakutani's problem, the Ulam conjecture. Lothar Collatz is generally credited with conceiving it around 1937 as a young researcher, though he never formally published the problem itself.
2 · The precise statement / the mathematical setup
Define the Collatz map T : ℕ → ℕ as above. The conjecture is:
∀ n ∈ ℕ, ∃ k ∈ ℕ such that Tk(n) = 1.Every positive integer has some iterate equal to 1: equivalently, the only cycle is {1, 2, 4} and no orbit escapes to infinity.
It is cleaner to work with the accelerated (Syracuse) map, which compresses each odd step with the deterministic run of halvings that must follow it. For odd n, note 3n+1 is always even, so define
Syr(n) = (3n + 1) ⁄ 2v₂(3n+1), for odd nThe Syracuse map sends one odd number directly to the next odd number in the orbit, stripping out all intervening factors of 2.
The Syracuse map acts only on odd integers, and the full conjecture is equivalent to: every odd n is eventually sent to 1 by Syr. This reformulation isolates the real content, because the even steps are forced bookkeeping: the drama is entirely in which power of 2 divides 3n+1.
Two sub-claims package the conjecture into its natural halves:
- No divergent orbit. No n has an orbit that grows without bound, i.e. limsupk Tk(n) = ∞ for no n.
- No other cycle. The only periodic orbit among positive integers is 1 → 4 → 2 → 1; there is no nontrivial cycle.
Proving both, for all n, is the whole problem. Every partial result below attacks one of these two and gets agonizingly close without touching the universal quantifier.
The probabilistic heuristic: why we believe it is true
Model the orbit as random. Starting from an odd number, 3n+1 is even; it is divisible by exactly 2j with "probability" 2−j (the valuations behave like a geometric distribution). The expected number of halvings after each odd step is therefore ∑j≥1 j·2−j = 2. So a typical odd step multiplies by 3, adds a negligible 1, then divides by about 22 = 4: a net multiplier of
expected growth per odd step ≈ 3 ⁄ 4 < 1, equivalently each step changes log n by E[log(3/2) − v₂·log 2] = log 3 − 2 log 2 < 0On average, orbits shrink geometrically. This makes the conjecture overwhelmingly plausible: it does not prove it.
This is why essentially every mathematician believes the conjecture is true. It is also exactly why it is so dangerous: an average contraction does not forbid a single lucky orbit from drifting upward forever, nor one rare cycle from closing on itself. The gap between "almost surely shrinks" and "always reaches 1" is the entire unsolved problem.
3 · Every connection: what it touches and what it would unlock
- 2-adic dynamics. The map extends naturally to the 2-adic integers ℤ2. Lagarias showed the parity sequence of an orbit (the record of even/odd at each step) gives a conjugacy between the Collatz map on ℤ2 and the shift map on sequences: making the dynamics, on ℤ2, measurably as chaotic as a coin-flip process. The integers sit inside ℤ2 as a measure-zero set, which is precisely why the chaotic 2-adic picture says nothing directly about them.
- Undecidability of generalizations. John Conway (1972) showed that natural generalizations of the Collatz map (piecewise-linear maps with more residue classes) can simulate arbitrary computation, so no algorithm can decide the behavior of the whole family. He later distilled this into FRACTRAN (1987), an explicitly Turing-complete arithmetic programming language built from exactly such iterations. This connects Collatz to computability theory and is the deepest structural hint we have about its difficulty.
- Ergodic theory and equidistribution. The valuations v2(3n+1) along orbits are conjectured to equidistribute like an i.i.d. geometric sequence; Tao's breakthrough is essentially a rigorous partial version of this for almost all starting points.
- Diophantine approximation. Ruling out nontrivial cycles reduces to how well log23 can be approximated by rationals: a cycle of a given shape forces a continued-fraction coincidence for log 3 ⁄ log 2 that is known not to occur below astronomical sizes.
- What it unlocks. Honestly: no major theorem is known to depend on Collatz. Nothing in the rest of mathematics collapses if it is false, and little is proven assuming it is true. Its value is diagnostic, not load-bearing: a settled proof would almost certainly arrive bundled with a genuinely new technique for controlling multiplicative–additive iterations, and that technique is the prize, not the corollary.
4 · Every serious attack: and exactly how far each got
Density results: "almost all" orbits descend
Riho Terras (1976) and, independently, C. J. Everett (1977) proved the first real theorem: almost every integer eventually drops below its starting value. Precisely, the set of n whose orbit never goes below n has natural density 0. This nails the "typical orbit shrinks" heuristic into a theorem: for almost all starting points, measured by density.
Counting integers that reach 1
Krasikov & Lagarias (2003), building on Applegate–Lagarias, proved a lower bound on how many integers below x are known to reach 1:
#{ n ≤ x : orbit of n reaches 1 } ≥ x0.84 (for large x)At least ~x^0.84 of the integers up to x provably reach 1: strong, but a vanishing fraction of all of them as x grows.
Cycle exclusion
If a nontrivial cycle exists it must be enormous and of a very constrained shape. R. P. Steiner (1977) ruled out the simplest "circuit" structure. Simons & de Weger (2005), using sharp estimates on the continued-fraction expansion of log23 combined with the computational verification, proved there is no nontrivial cycle consisting of at most 68 circuits: so any hypothetical cycle must have more than 68 circuits, forcing it to have length on the order of 1010 or more and a smallest element far beyond any tested range.
Computation
Tomás Oliveira e Silva verified the conjecture to around 260, and David Barina (published 2020–2021) pushed convergence verification beyond 268 ≈ 2.95 × 1020, with distributed efforts continuing past it. Every single integer tested reaches 1. This is overwhelming evidence and, formally, worth nothing toward the universal statement: the unchecked integers remain infinite.
Tao's theorem: the current high-water mark
Terence Tao (2019, published in Forum of Mathematics, Pi, 2022) proved the strongest result to date: "Almost all orbits of the Collatz map attain almost bounded values." Formally, for any function f(n) → ∞ however slowly, the set of n whose orbit minimum exceeds f(n) has logarithmic density 0.
For almost all n (log density), mink Tk(n) < f(n) for any f → ∞Almost every orbit dips below any slowly growing threshold. This is as close to "reaches 1" as current technique gets: and the gap is structural, not incremental.
Tao's method treats the Syracuse valuations as an approximately random process and transports a well-behaved probability distribution forward under the dynamics, controlling it with entropy/Fourier estimates. It is a tour de force: and it still cannot close the problem, for the reasons in the next section.
5 · Why it breaks down: the honest crux
Wall 1: There is no decreasing invariant, and the map actively grows. Almost every technique for proving an iteration terminates relies on a monotone quantity (a Lyapunov function, a well-ordering, a potential that strictly drops). The Collatz map has none. On odd inputs it increases the value by a factor of roughly 3. Any candidate measure that decreases on average is defeated by individual odd steps that spike upward: 27 climbing to 9232 is the small-scale symptom. With no quantity that provably decreases at every step, the standard termination machinery has nothing to grip. This is the root wall from which the others grow.
Wall 2: "Almost all" is not "all," and the exceptional set can be infinite. Terras, Everett, Krasikov–Lagarias and Tao all deliver statements about integers of full density (natural or logarithmic). But a set of density 0 can still be infinite: the primes have density 0 and there are infinitely many. The conjecture is destroyed by a single divergent orbit or one nontrivial cycle. Density arguments are, by their nature, blind to individual exceptional trajectories; they average the bad cases away, and a counterexample is exactly the case that refuses to be averaged. Tao's result dips almost every orbit almost to the floor: "almost bounded," not bounded, and "almost all," not all. Pushing from log-density-0 exceptional sets to the empty exceptional set would require controlling every orbit uniformly, which no known method on a measure-zero set of integers can do.
Wall 3: Cycle exclusion needs a finiteness no bound supplies. Steiner and Simons–de Weger can forbid cycles of any bounded complexity, because a short cycle forces an impossibly good rational approximation to log23. But the argument degrades as the hypothetical cycle grows: longer cycles permit the Diophantine coincidence to be satisfied less precisely, and the irrationality measure of log23 is not known to be strong enough to rule out all lengths at once. The method caps the complexity it can exclude; it cannot reach infinity. So "no small cycle" never upgrades to "no cycle."
Wall 4: The 2-adic conjugacy proves chaos on the wrong set. Lagarias's conjugacy shows the map is genuinely as unpredictable as a Bernoulli shift on ℤ2, where almost every 2-adic integer has a divergent, aperiodic orbit. The integers ℕ ⊆ ℤ2 are a measure-zero exceptional set within that chaos: exactly the set the ergodic theory cannot see. The dynamical picture therefore explains why the problem feels random without giving any leverage on the one subset we care about. Every measure-theoretic argument hands you full-measure statements; ℕ is where measure theory is silent.
Wall 5 (FRINGE / speculative): "It is undecidable, so stop trying." Clearly labelled speculation. Because Conway (1972) proved that the family of Collatz-like maps is Turing-complete and hence algorithmically undecidable, a recurring fringe claim is that the specific 3n+1 problem is itself formally undecidable (independent of the usual axioms), which would explain the universal failure. This is not established and is almost certainly a category error: Conway's result is about a parametrized family rich enough to encode computation, not about the single fixed map. A single concrete statement like "every n reaches 1" is a Π2 arithmetic sentence; undecidability of a family does not transfer to one member, and there is no evidence the fixed map encodes a halting problem. Equally fringe are the recurring "elementary proofs" posted online: typically built on a reverse-tree or an averaged-contraction argument that silently swaps "almost all" for "all" (Wall 2) or assumes the very no-cycle / no-divergence fact to be proven. They have not closed the problem for the same reason the serious attacks have not: the universal quantifier survives untouched, and the average contraction is not a per-orbit guarantee. The honest residue of the undecidability speculation is a real warning, not a theorem: the problem may simply sit in a zone our current logic of arithmetic cannot yet reach, which is Erdős's point stated formally.
6 · Status: confirmed
OPEN. The Collatz conjecture is unproven and undisproven as of this writing. Every integer ever tested (past 268) reaches 1; no counterexample is known; and essentially the entire mathematical community expects it is true. None of that is a proof.
A genuine resolution would require one of two things, and nothing less:
- A proof that simultaneously (a) rules out every divergent orbit and (b) rules out every nontrivial cycle, for all positive integers: upgrading today's density/"almost all" results (Terras, Everett, Krasikov–Lagarias, Tao) to a universal statement by controlling the measure-zero exceptional set that all current methods cannot see, or
- A disproof exhibiting a single explicit counterexample: either one integer whose orbit provably diverges, or one nontrivial cycle: which by Simons–de Weger must be astronomically large and would itself be a landmark discovery.
The realistic verdict is that no existing technique is within reach of either. Closing it will almost certainly demand a new way to control the coupling between multiplication, the "+1," and 2-adic valuation along a single orbit: the exact thing Walls 1–4 each name from a different direction. Until such a method exists, the one-line claim at the top of this page remains exactly that: a claim.
Credit where it is due. The problem is attributed to Lothar Collatz (c. 1937). The decisive partial results belong to Riho Terras and C. J. Everett (density of descent, 1976–77), R. P. Steiner (1977) and John Simons & Benne de Weger (2005) on cycles, Ilia Krasikov & Jeffrey Lagarias (2003) on counting, and Terence Tao (2019/2022) for the current high-water mark. John Conway supplied the undecidability of generalizations (1972) and later the FRACTRAN language (1987). Jeffrey Lagarias wrote the definitive surveys and the 2010 volume The Ultimate Challenge: The 3x+1 Problem; the computational frontier is owed to Tomás Oliveira e Silva and David Barina. Paul Erdős gave the problem its most honest epitaph ("mathematics may not be ready for such problems") and a $500 prize no one has claimed. The unsolved problem is claimed by no one here: if it is ever solved, that proof is offered freely to the world.
← back to SOLUTION