Take any positive integer. If it's even, divide it by 2. If it's odd, multiply by 3 and add 1. Repeat this process indefinitely. The Collatz Conjecture claims that no matter which positive integer you start with, you will always eventually reach 1. Despite being verified computationally for every starting number up to nearly 2βΆβΈ, and despite its almost childlike simplicity, no one has ever proven it true for all possible starting numbers β nor found a single counterexample.
Pick any positive whole number. If it's even, cut it in half. If it's odd, triple it and add 1. Keep repeating this simple process with whatever number you get. Try it with 6: 6β3β10β5β16β8β4β2β1. You reached 1! Try it with 27 (a notoriously long example): it takes 111 steps, climbing as high as 9,232 along the way, before finally reaching 1.
The rules are so simple a child could understand and apply them. Yet the resulting number sequences behave chaotically and unpredictably β sometimes shooting up to enormous heights before eventually coming back down to 1, with seemingly no way to predict in advance how long any particular starting number will take, or how high it will climb along the way. Paul ErdΕs, one of the most prolific mathematicians in history, reportedly said "mathematics is not yet ready for such problems," commenting on the Collatz Conjecture's surprising and stubborn difficulty despite its deceptively simple appearance.
Because the problem is so easy to state and understand, it has become notorious for repeatedly tempting talented students and even some professional mathematicians into spending far more time on it than is generally considered wise or professionally productive β earning it the semi-serious nickname of a mathematical "trap" among some working mathematicians, who often gently warn newcomers away from investing too much serious research time into it.
Define the Collatz function:
The conjecture states: for every positive integer n, repeatedly applying f eventually reaches the value 1 (after which the sequence cycles 1β4β2β1 forever).
The specific combination of rules is what makes the problem interesting: tripling-and-adding-1 for odd numbers tends to push numbers upward, while halving pushes them back down β but because odd numbers become even after the 3n+1 step (3 times an odd number, plus 1, is always even), the sequence alternates unpredictably between these two competing tendencies, with no simple, obvious pattern to when numbers will grow versus when they'll shrink.
The conjecture is named after German mathematician Lothar Collatz, who proposed it around 1937 while a student, though he didn't formally publish it. It has independently acquired numerous other names over the decades, including the 3n+1 problem, the Ulam conjecture (after StanisΕaw Ulam), the Kakutani problem, the Thwaites conjecture, and the Syracuse problem β a striking reflection of how many different mathematicians across different countries and eras independently rediscovered and separately studied essentially the same simple, tantalising problem.
As of recent verification efforts (Barina, 2020, and subsequent extensions), the conjecture has been checked and confirmed true by computer for every starting value up to approximately 2βΆβΈ β 2.95 Γ 10Β²β° β an astronomically large number of individually verified cases, yet still representing only a literally infinitesimal fraction of all the infinitely many positive integers that would need to be checked to constitute an actual, complete mathematical proof.
While a complete proof remains elusive, mathematicians have proven various partial and probabilistic results. Terence Tao (2019), one of the most prominent living mathematicians, proved that "almost all" Collatz sequences (in a precise, technical statistical density sense) attain almost-bounded values β a genuinely significant partial result representing meaningful progress, though notably still falling importantly short of a complete, fully general proof for every single starting integer without any possible exception.
Terence Tao's landmark 2019 paper showed that for "almost all" positive integers n (in a specific, carefully-defined logarithmic density sense), the Collatz sequence starting from n eventually reaches a value smaller than any arbitrarily slowly-growing function of n β a substantial, celebrated, and widely-discussed partial result. However, Tao himself has been explicitly and appropriately clear that this specific style of density-based argument, however powerful and clever, likely cannot straightforwardly be pushed all the way to a full, complete, unconditional proof covering literally every single starting positive integer without exception β the specific proof technique used has certain inherent, well-understood mathematical limitations of this particular kind.
The Collatz map exhibits behaviour with intriguing surface-level similarities to processes studied more generally in dynamical systems theory and chaos theory β sensitive, seemingly unpredictable dependence on the specific starting value, combined with an overall long-run statistical regularity in the aggregate behaviour of many different starting sequences considered together. Some researchers have specifically approached the problem using probabilistic heuristic models (treating each step's parity as if it were effectively a fair coin flip), which correctly and successfully predict the empirically observed general statistical behaviour extremely well, but such heuristic probabilistic arguments do not, and cannot in principle, constitute an actual rigorous mathematical proof of the conjecture itself.
Mathematicians have studied numerous natural variants and generalisations: different specific choices for the multiplier and additive constant (generalising beyond just "3n+1"), versions extended to the negative integers (where multiple distinct additional cycles, beyond just 1-4-2-1, are already known to exist), and versions applied to the Gaussian integers (see the Complex Number entry) and other, more exotic number systems. Studying these variants and how their behaviour differs from or resembles the original problem has yielded some limited additional mathematical insight into the core problem's specific underlying structure.
Given the close conceptual relationship between the Collatz function's behaviour and general computational processes, some mathematicians and logicians have speculated β though this remains firmly unproven and highly speculative rather than an established mathematical result β that certain natural and reasonable generalisations or variants of the Collatz problem might turn out to be formally undecidable within standard axiomatic systems, in a manner conceptually related to GΓΆdel's Incompleteness Theorems and the Halting Problem (see those entries). John Conway (1972) notably proved that a certain broader, more general class of "Collatz-like" functions does indeed contain provably undecidable problems, lending some genuine theoretical, if indirect, weight and plausibility to this speculation about the specific original Collatz problem itself, without in any way actually resolving the original conjecture.