Fourteen fractions that list the primes

The Collatz rule looks at one thing about a number — whether it is even or odd — and chooses one of two affine maps accordingly. The first essay on it mentioned in a single paragraph that the obvious generalisation is not merely hard but impossible: John Conway showed in 1972 that for rules which look at the remainder modulo some fixed number, and multiply and add accordingly, no algorithm can decide in general whether the orbits reach 1.

This essay unpacks that paragraph. The way Conway proved it is by showing that these maps can compute — that a suitably chosen rule of the Collatz kind is a computer — and the most vivid demonstration is a list of fourteen fractions that, applied by a rule of one sentence, produces the prime numbers in order.

The result changes what kind of problem the Collatz conjecture is. Before Conway it was possible to hope that some general theory of maps like $3n + 1$ — a theory of affine rules on remainders — would settle it along with all its relatives. After him, no such theory can exist, because some relatives are computers, and a theory that decided all of them would decide the halting problem. Whatever proves the Collatz conjecture, if anything does, must exploit something that distinguishes this one rule from the rules that compute.

A rule that looks at more than the last digit #

A generalised Collatz map fixes a modulus $m$ and, for each remainder $r$ from $0$ to $m - 1$, a rational number $a_r$ and another $b_r$; it sends $n$ to $a_r n + b_r$ when $n$ leaves remainder $r$ on division by $m$. The numbers are chosen so that the result is always a whole number. The Collatz map is the case $m = 2$: remainder $0$ gives $n/2$, remainder $1$ gives $(3n + 1)/2$.

Nothing about the definition suggests anything more than more of the same — a larger table of affine pieces — and for small moduli that is roughly what they look like: orbits that wander, fall into cycles, or grow, with no visible structure. Conway’s observation was that a table of affine pieces can be arranged to do bookkeeping. With a large enough modulus, a single number can hold the contents of several counters at once, and the remainder can say which counter is to be changed next.

The cleanest way to see this is in a notation Conway published in 1987, in which the whole map is a list of fractions.

FRACTRAN: a program is a list of fractions #

A FRACTRAN program is a finite list of positive fractions $f_1, f_2, \ldots, f_k$. To run it on a whole number $n$, find the first fraction $f_i$ in the list for which $n f_i$ is a whole number, and replace $n$ by $n f_i$. Repeat. If no fraction works, stop.

That is a generalised Collatz map. Whether $n f_i$ is a whole number depends only on the remainder of $n$ modulo the denominators of the fractions, so the choice of fraction — and therefore the map — is decided by the remainder of $n$ modulo the least common multiple of all the denominators. The whole program is one row of multiplications, indexed by remainders.

What makes the notation readable is prime factorisation. Write $n = 2^{e_2} 3^{e_3} 5^{e_5} \cdots$ and think of each exponent as a register holding a whole number. Multiplying by a fraction adds to the registers of the numerator’s primes and subtracts from the registers of the denominator’s primes, and “$n f_i$ is a whole number” means exactly that the registers being subtracted from are large enough. A fraction is an instruction: if registers 7 and 11 are both non-zero, take one from each and add one to register 2.

A machine that multiplies #

The six fractions $455/33$, $11/13$, $1/11$, $3/7$, $11/2$, $1/3$ multiply two numbers. Start with $2^a 3^b$ — the two inputs in registers 2 and 3 — and the program halts at $5^{ab}$.

Written out as numbers, the first steps look like nothing at all. The program starts at $648 = 2^3 \cdot 3^4$. No fraction but $11/2$ gives a whole number, so the next number is $3564 = 2^2 \cdot 3^4 \cdot 11$. Now $455/33$ applies, giving $49140 = 2^2 \cdot 3^3 \cdot 5 \cdot 7 \cdot 13$; then $11/13$ gives $41580$; then $455/33$ again gives $573300 = 2^2 \cdot 3^2 \cdot 5^2 \cdot 7^2 \cdot 13$. As a sequence of whole numbers — $648, 3564, 49140, 41580, 573300, \ldots$ — it is as opaque as a Collatz orbit. Factored, it is a loop moving units from one register to two others, one at a time.

That contrast is the heart of the matter. A generalised Collatz map is a rule about remainders and multiplication, and on the face of it the numbers it produces are just numbers. The computation is visible only in a coordinate system — prime exponents — that the rule never mentions. Nothing forbids the ordinary Collatz orbits from carrying hidden bookkeeping of the same kind in some other coordinate system; nobody has found one, and nobody can rule it out.

Reading the grid shows how a list of fractions becomes an algorithm. The factor $455/33 = (5 \cdot 7 \cdot 13)/(3 \cdot 11)$ is the inner loop: while registers 3 and 11 are both non-zero, it moves one unit from register 3 into registers 5 and 7, and flips a control register from 11 to 13; $11/13$ flips it back. When register 3 runs out, $1/11$ clears the control flag, and $3/7$ pours register 7 back into register 3 — restoring the second input. Then $11/2$ takes one from register 2 and restarts the loop. The primes 11 and 13 are not data at all; they are the program’s state, the line of code it is on.

That is the whole idea behind the universality proof. A machine with a handful of counters, each of which can be incremented, decremented, and tested for zero, can compute anything a computer can — Marvin Minsky showed in the 1960s that two counters are already enough, given a suitable encoding. Every such machine translates into a FRACTRAN program by giving each counter a prime and each state a prime, and every FRACTRAN program is a generalised Collatz map.

The primes, from fourteen fractions #

Conway’s PRIMEGAME is the fourteen fractions

$$\tfrac{17}{91}, \tfrac{78}{85}, \tfrac{19}{51}, \tfrac{23}{38}, \tfrac{29}{33}, \tfrac{77}{29}, \tfrac{95}{23}, \tfrac{77}{19}, \tfrac{1}{17}, \tfrac{11}{13}, \tfrac{13}{11}, \tfrac{15}{14}, \tfrac{15}{2}, \tfrac{55}{1}.$$

Run it from $2$. The numbers it produces grow and shrink erratically, and every so often one of them is a pure power of two. The exponents of those powers of two are exactly the prime numbers, in order, and no power of two with a composite exponent ever appears.

Inside, PRIMEGAME is a machine testing each whole number $n$ in turn for divisibility by every smaller number, by repeated subtraction — the sieve’s question answered the slowest way possible. The registers of 2, 3, 5 and 7 hold the candidate, the trial divisor and working copies; the primes 11 to 29 are its states. When a candidate survives every trial division, the machine clears all its working registers except the one holding the candidate, and that is the moment the number is a pure power of two. The step counts grow fast — the tenth prime, 29, arrives after more than 36,000 steps — because every trial division is carried out by counting down one unit at a time.

The run in the opening figure checks what the program claims, prime by prime, for ten primes. It proves nothing about the eleventh. That PRIMEGAME lists every prime is a theorem about what its fourteen fractions compute, proved by reading them as a program, and a simulation can only illustrate it. Richard Guy, who popularised the program, described the proof as exactly that reading: identify which primes are states and which are registers, and check each fraction does what its line of the program should.

Why this makes the general question undecidable #

Put the pieces together. Any computer program can be written as a counter machine; any counter machine as a FRACTRAN program; any FRACTRAN program as a generalised Collatz map. A program halts exactly when the map reaches a number that no fraction applies to — and a small change turns “stops” into “reaches 1”. So a method that decided, for every generalised Collatz map and every starting number, whether the orbit reaches 1 would decide whether every program halts. The diagonal argument shows that nothing can decide that.

Conway’s theorem is therefore that the generalised Collatz problem is undecidable: there is no algorithm that takes a map of this kind and a starting number and correctly says whether the orbit reaches 1. Stuart Kurtz and Janos Simon sharpened it in 2007: the question of whether every starting number reaches 1, for a given map, sits exactly at the level of logical complexity of statements of the form “for every input there is a halting computation” — as hard as questions of that shape can be.

It is the same phenomenon as the cellular automaton that computes: a rule too simple to look like a computer turns out to be one, and the undecidability of the general question is inherited from computation itself. And it is worth being exact about what it says. It does not say the ordinary Collatz problem is undecidable. That is one particular map with modulus two, and a single yes-or-no question about a single map is always decidable in the trivial sense that one of the two programs “print yes” and “print no” is correct. What Conway’s theorem says is that no general method for the family exists — so any proof of the Collatz conjecture must use something special about $3n + 1$ that fails for the maps that compute.

When a small machine meets a Collatz question #

The connection runs in the other direction too, and recently it has become concrete. The busy beaver problem asks, for each number of states, how long a Turing machine with that many states can run before halting, starting on a blank tape — the fastest-growing function a computer can be made to define, and a cousin of the growth rates that ordinals measure. To know its value for five states, every five-state machine that does not obviously halt or obviously loop has to be analysed by hand or by proof assistant, and a large online collaboration completed that in 2024: the answer is 47,176,870 steps.

Along the way, some of the hardest machines to classify turned out to be running Collatz-like maps. Their tapes, read in the right way, hold a single number, and each pass of the head applies a rule of the form “multiply by three and halve, or halve, according to the remainder” — a generalised Collatz map with a tiny modulus, encoded in a handful of states. For six states the obstruction is sharper still: among the six-state machines is one whose halting is equivalent to a question about the orbit of a specific number under a Collatz-like map, a question with the same flavour as the orbit of 8 and no better prospects of an answer.

So the smallest machines that are hard to understand are hard for a Collatz reason, and the simplest Collatz-like maps may be hard for a computing reason. Conway’s theorem is the formal link between the two, and the busy beaver search is where it has stopped being formal.

A permutation that nobody can finish #

Conway’s 1972 paper also contains a map that is not a computer, as far as anyone knows, and is not understood either. Send an even $n$ to $3n/2$; send $n$ with remainder $1$ on division by four to $(3n + 1)/4$; send $n$ with remainder $3$ to $(3n - 1)/4$. This is a generalised Collatz map with modulus four, and unlike the Collatz map it is a permutation: every whole number is sent somewhere and is reached from exactly one number, so every orbit runs backwards as well as forwards.

It has a few short cycles, found by following each small number until it returns. Conway called it amusical because a step of $3/2$ is a musical fifth and a step of $3/4$ a fourth, and the map wanders up and down by fifths and fourths.

The orbit of 8 is the famous one. Forwards it goes $8, 12, 18, 27, 20, 30, 45, 34, 51, 38, 57, 43, 32, \ldots$ and backwards $8, 11, 15, 10, 13, \ldots$, and it has been followed for enormous numbers of steps in both directions without closing. A heuristic like the one that cannot be a proof predicts that it should not close: on average a step multiplies by about $3/2$ half the time and $3/4$ the other half, a net factor of $\sqrt{9/8} > 1$ forwards, so the orbit should drift upward and escape. Nobody can prove it. The question “is the orbit of 8 infinite?” is as simple to state as the Collatz problem and as far from being settled. The cycles it does have are constrained in the same way the Collatz cycles are, and the same argument applies: a cycle with $a$ steps of $3/2$ and $b$ steps of $3/4$ must bring the product of its factors back to one, up to the small additive corrections, which forces a relation between powers of two and three — the equation that bounds how short a Collatz cycle could be — and rules out cycles of many lengths without ruling out the orbit of 8 closing at some enormous one.

What the machines cannot show #

Every figure runs a program for finitely many steps. The PRIMEGAME figure shows ten primes; the multiplication figure one product; the permutation figure twelve hundred steps of one orbit. None of them shows the thing the essay is about, which is a statement about all programs, and undecidability in particular has no picture: it says a certain method does not exist, and a figure can only show methods that do.

The pictures also hide how the encodings work in detail. PRIMEGAME’s fourteen fractions implement a program that a person can read, with effort, and the universality construction implements any program, but the translation from a counter machine to fractions involves bookkeeping that a picture of registers flashes past in a few dozen columns. Reading the grid as an algorithm, as above, is the most the figure can support. And the heuristics quoted for the permutation are exactly that. The average multiplier per step predicts drift; it does not account for the correlations between successive remainders, which are what a map that computes would exploit, and nothing in a plot of twelve hundred steps can tell a drifting orbit from one that will turn round after a million.

Still open: the orbit of 8, and which simple maps compute #

The general question is closed — undecidable — and the particular ones are open. Whether the Collatz map itself sends every number to 1 is unknown; whether the amusical permutation’s orbit of 8 is infinite is unknown; whether the $5n + 1$ map, which behaves like a coin tilted toward growth, has any orbit that grows for ever is unknown.

Between the general theorem and the particular questions sits a question about thresholds: how small can the modulus, or the number of fractions, be for a map of this kind to be universal? Constructions with fairly small moduli are known, and it is known that some very small maps are not universal, but the boundary is not located — and whether the Collatz map itself lies on the computing side of it, which would make its individual orbits as unpredictable as programs, is not known either. What is known is that the modulus-two case is special in one clean respect: on the 2-adic integers it is exactly a coin, with no room in its dynamics for the bookkeeping a computer needs — a hint, and no more than a hint, that it lies on the simple side.