The question nobody can answer

Take a whole number. If it is even, halve it. If it is odd, triple it and add one. Repeat.

Starting from 6: $6, 3, 10, 5, 16, 8, 4, 2, 1$. Nine numbers, and then the cycle $1, 4, 2, 1$ forever.

Starting from 27 it takes rather longer.

The conjecture is that this always happens: every positive integer eventually reaches one. It has been checked for every number up to about $2^{68}$, which is around $3 \times 10^{20}$. Nobody has proved it.

Why it is hard to say anything #

The obstruction is easy to state. The rule does two incompatible things and they are not commensurable.

Halving is a shift in base two. Tripling and adding one is not — it interacts with a number’s binary structure in a way that does not simplify. So every tool that works well for one operation is useless for the other, and the sequence of choices between them is determined by parity information that changes unpredictably as the number evolves.

Put differently: the orbit of $n$ depends on the binary expansion of $n$ in a way that no known algebraic structure captures. There is no invariant, no monotone quantity, and no obvious induction.

That last absence is the fatal one. Almost every termination proof in mathematics works by finding a quantity that decreases at every step and cannot decrease forever — Euclid’s algorithm terminating is the model case, where the remainder shrinks. Collatz has no such quantity. The number goes up on odd steps and down on even ones, and there is no combination of them known to be monotone.

The heuristic, and why it is not a proof #

There is an argument that the conjecture is true, and understanding why it falls short is more instructive than the argument itself.

Consider what happens to an odd number $n$. It becomes $3n+1$, which is even, so the next step halves it. On average, half of the results are divisible by 4, a quarter by 8, and so on, so an odd step followed by its halvings multiplies $n$ by $3/2$ with probability $1/2$, by $3/4$ with probability $1/4$, by $3/8$ with probability $1/8$, and so forth.

The expected multiplier, in the geometric-mean sense that matters for repeated multiplication, is

$$\prod_{k \ge 1} \left(\frac{3}{2^k}\right)^{2^{-k}} = \frac{3}{4} < 1.$$

So a typical orbit shrinks by about a quarter per odd step, which is a decay rate, and a sequence decaying geometrically reaches one.

The argument is convincing and it is not a proof, for a reason worth being precise about. It treats the parity of successive values as though they were independent coin flips. They are not — they are determined, exactly, by the starting number. The heuristic computes what would happen for a random sequence with those statistics, and says nothing about whether any particular integer’s actual sequence behaves that way.

That is the same gap as between a chaotic orbit and a random one: the statistics agree, and the objects are entirely different.

The map that only sees odd numbers #

Most of the steps in the figures are halvings, which carry no information, and removing them makes the structure easier to talk about.

Define $T(n) = (3n+1)/2^k$, where $2^k$ is the largest power of two dividing $3n+1$. This sends an odd number straight to the next odd number in its orbit, skipping the run of halvings. The conjecture is unchanged — reaching one under $T$ is the same as reaching one under the original rule — and the sequence is now half as long and entirely made of odd numbers.

The value of the reformulation is that it isolates where the difficulty lives. Every step of $T$ is “multiply by three, add one, and divide out all the twos”, and the only thing that varies is $k$: how many factors of two happen to appear. The whole problem is the behaviour of that sequence of exponents.

And $k$ is determined by arithmetic modulo powers of two: $k = 1$ when $n \equiv 1 \pmod 4$, $k \ge 2$ when $n \equiv 3 \pmod 4$, with the finer cases decided by more bits. So the exponents are a function of the low-order binary digits of $n$ — perfectly definite, and shuffled by the multiplication by three in a way that has resisted every attempt to control.

The first $m$ exponents in an orbit form a parity vector, and here is the one clean structural theorem in the subject: every possible parity vector of length $m$ occurs, for exactly one residue class modulo $2^m$. The map from starting residues to parity vectors is a bijection. That is a strong and precise statement, and it says the exponent sequence is as unconstrained as it could possibly be — which is exactly why no argument gets a grip on it.

What is actually proved #

The known results are real and they are all of the same shape: statements about almost all numbers rather than all.

Almost all orbits get small. Terras, 1976, and sharpened by Tao in 2019: almost every starting value eventually drops below any prescribed slowly-growing function of itself. Tao’s version is close to the best that current methods allow and it still does not say “reaches one” or “all”.

There are no short cycles. Any cycle other than $1, 4, 2$ must have length at least $186$ billion, by a computation on continued-fraction approximations to $\log_2 3$. That rules out a small counterexample of one kind.

Divergence is possible in principle. A counterexample could be a number whose orbit grows forever without cycling. Nothing rules this out, and it is not known which of the two failure modes to look for.

Nearby problems are undecidable. Conway showed in 1972 that a natural generalisation — allowing the multiplier and offset to depend on $n$ modulo some fixed number — gives a family in which no algorithm decides termination. The generalised problem is Turing complete, in exactly the sense rule 110 is.

That last result is the one that changes how the problem looks. It does not say Collatz itself is undecidable; a single instance always has a definite answer. It says the problem sits inside a family with no general method, so any proof must use something specific to the numbers $3$ and $1$ rather than a general argument about maps of this kind.

Looking at all the orbits at once #

One orbit says little. Plotting how long every starting number takes says more, and what it says is mostly about how little structure there is.

Two features are visible and both are explicable.

The upward drift. Larger numbers take longer on average, roughly like $\log n$, which is what the heuristic predicts: a geometric decay from $n$ takes about $\log n$ steps to get to one. The constant of proportionality is predicted too, and it matches the measured slope — which is the strongest evidence the heuristic has, and still says nothing about any individual number.

The horizontal bands. Many numbers share the same length, and the bands are spaced by a constant. That is because a number and its double have lengths differing by exactly one — the double’s first step is a halving that lands on the original — so whole families of orbits are copies of each other shifted.

What is not visible is any pattern that would suggest a proof. The scatter within each band is as irregular as anything in this field, and no known function of $n$ predicts its Collatz length.

What a counterexample would look like #

There are only two ways the conjecture can fail, and knowing what each would require is most of what constrains the search.

A second cycle. Some orbit could close up on itself somewhere other than $1, 4, 2$. The constraint here is arithmetic: a cycle with $a$ odd steps and $b$ even ones requires $2^b$ to be very close to $3^a$, since the multiplications by three and the divisions by two must cancel exactly. How close $2^b$ can get to $3^a$ is a question about how well $\log_2 3$ can be approximated by fractions, and that is answered by its continued fraction. The approximations are not good enough for any short cycle to work, which is where the 186-billion bound comes from — a statement about a Collatz cycle, proved by approximating an irrational number.

An orbit that runs away. Some number could grow forever, never cycling and never descending. Nothing at all rules this out. The heuristic says the expected growth factor is under one, so a runaway orbit would have to be atypical at every step forever — improbable, in the sense the heuristic can measure, and improbable is not impossible when the sequence is not actually random.

The second is the one to bet against and the harder to exclude. A cycle is a finite object and can in principle be ruled out by computation; a divergent orbit is an infinite object and no finite computation touches it. Verifying to $2^{68}$ rules out neither kind above the bound.

Why this is in a chapter about dynamics #

Collatz is a number-theory problem by reputation and a dynamical system by structure, and reading it as the second is what this field’s tools are for.

It is a map, iterated, with a fixed point at the end of every known orbit. The question “does every orbit reach the cycle $1, 4, 2$” is the question “is there exactly one attractor and is its basin everything”. Stated that way it is the same question asked of the logistic map, of Newton’s basins and of the Mandelbrot set — and in every one of those cases the answer required understanding the boundary between basins.

Here there is no known boundary, because as far as anyone can tell there is nothing on the other side of it. The suspicion is that the basin is everything and there is no boundary at all, which is a stronger and stranger claim than any of the others in this field.

The dynamical reading also explains why the length plot looks the way it does. A map with one attracting cycle and a violently irregular route to it produces exactly this — a drift set by the decay rate and a scatter set by how far each individual start happens to wander first. It is the shape the escape-time bands had around the Mandelbrot set, drawn against the integers instead of against the plane, and for the same reason: the quantity plotted is how long something takes, and that quantity is continuous nowhere.

What the tree looks like from the other end #

Running the rule backwards turns the conjecture into a statement about growing a tree rather than about descending one, and it is the form most attempted proofs take.

Reverse the rule: a number $m$ can be reached by doubling, from $2m$, and — when $(m-1)/3$ is an odd whole number — by the odd step, from $(m-1)/3$. Start at $1$ and apply the reverse rule repeatedly, and the result is a tree of everything that reaches one. The conjecture is that this tree contains every positive integer.

Stated that way it is a covering problem, and covering problems are usually approachable: show the tree’s density exceeds some threshold, apply a sieve, done. That is exactly what has been tried, and the difficulty is that the tree’s branching is irregular. Most nodes have one child, some have two, and which is which is decided by the same modulo-three condition that no argument controls. The tree grows at an average rate that is comfortably fast enough to cover everything, and unevenly enough that no counting argument closes.

There is one clean consequence of this direction, and it is the merging noted above. Two orbits that meet at any point share everything afterwards, so the entire structure is a tree rather than a tangle — no number has two different futures, because the forward rule is a function. What is unknown is only whether the tree is connected to every integer, not whether it is a tree.

Two records worth having #

The extreme cases are worth knowing because they show how badly the average behaviour describes individuals.

That merging is the structural fact behind the whole picture. Orbits that meet never separate, so the set of all orbits is a tree with one root, and the conjecture is the claim that every positive integer is on it. Verification to $2^{68}$ is a statement about how much of that tree has been enumerated, and enumerating more of a tree is not a route to proving it contains everything.

What the checking is worth #

The computation to $2^{68}$ took years of machine time and it has a specific, limited value.

It rules out counterexamples below that bound, which matters because plenty of conjectures fail at a first counterexample of moderate size. This collection has the cautionary case: a statement about prime-counting that held for every number anyone checked and is now known to fail somewhere past $10^{300}$, so agreement over any finite range is evidence and not much more than evidence. It has not turned up a pattern, and nobody expected it to.

What it does establish is the shape of the problem. A conjecture that survives $3 \times 10^{20}$ tests and has a heuristic argument in its favour is almost certainly true; the difficulty is not in believing it but in proving it, and the two have been separated for eighty years. Erdős’s assessment — that mathematics is not yet ready for such problems — remains the standard one, and it was made in the 1980s.

There is a last thing worth taking from it, and it is what this field has been about throughout. A rule of two lines, applied to whole numbers, with no randomness, no approximation and nothing hidden, produces a question that eighty years of work has not answered. The other rules in this field produced an undecidable prediction problem, an unknowable forecast and a set whose area nobody knows. None of them is complicated. The consistent finding of the whole subject is that the complexity of a rule says nothing about the difficulty of the questions it raises, and this is the shortest rule with the hardest question.