Euclid's proof run as a machine

There is no last prime drew Euclid’s argument as it is usually given. Take any finite list of primes, multiply them together, add 1. The result leaves remainder 1 when divided by each prime on the list, so none of them divides it; but it has some prime factor, and that factor is a prime not on the list. So no finite list contains every prime.

The argument is a procedure as well as a proof, and nothing stops it being run. Start with the list $\{2\}$. Multiply, add one: 3, prime. The list is now $\{2, 3\}$; multiply, add one: 7. Then 43. Then $2 \cdot 3 \cdot 7 \cdot 43 + 1 = 1807 = 13 \cdot 139$ — not prime, and the argument only promises some new prime factor, so the machine needs a rule. The rule Albert Mullin proposed in 1963 is the simplest: take the smallest. The sequence it produces is a strange object, defined by the oldest argument in number theory and as resistant to understanding as anything in it.

Twenty terms, and what each one costs #

The sequence begins

$$2,\ 3,\ 7,\ 43,\ 13,\ 53,\ 5,$$

$$6221671,\ 38709183810571,\ 139,$$

$$2801,\ 11,\ 17,\ 5471,\ 52662739,\ 23003,\ \dots$$

and every term in the table is certified in the same way. The number $N_k$ = 1 + (product of the first $k - 1$ terms) is formed exactly. A complete factorisation of it, found by computation when the table was made, is multiplied back together and must reproduce $N_k$; every factor must be at least the claimed term; and every factor must pass the Miller–Rabin test to the first twelve prime bases. A product of primes all at least $p$, one of them equal to $p$, has $p$ as its smallest prime factor — so each term is the smallest prime factor of its number, as the definition requires.

The Miller–Rabin test with those twelve bases is a proof of primality for numbers below about $3.3 \times 10^{24}$, and the table says “proved” for the twelve terms whose factors all lie below that bound. Beyond it the test makes a factor a strong probable prime: it has passed twelve independent tests that a composite number passes with probability at most one in four each, and no composite number is known to pass them all, but the passing is evidence rather than proof. Every factor in the table could be proved prime by slower methods; for the purpose here, the distinction is kept visible rather than hidden.

The cost of a term is the cost of factoring its number, and the numbers grow quickly: the eighth term required factoring a seven-digit number, the twentieth a seventy-digit one. Factoring is the hard step, and a collision that finds a factor showed why: the general methods take time growing faster than any power of the number of digits. Only about fifty terms of the sequence are known, and the next unknown term is stuck behind a number of several hundred digits that nobody has been able to factor.

The first steps by hand #

The early terms can be followed without a computer, and doing so shows the rule at work. After $2, 3, 7, 43$ the product is $1806$ and the next number is $1807 = 13 \cdot 139$: the machine takes 13. The product becomes $23478$, and $23479 = 53 \cdot 443$, so the next term is 53 — a prime larger than the one before it, because nothing smaller divides 23479. Then $1244334 + 1 = 1244335 = 5 \cdot 248867$, and 5 finally appears, at the seventh step, after being skipped six times. The product is now $6221670$, and $6221671$ is itself prime, so the eighth term is a seven-digit number.

Two features of the procedure are already visible. Each new number is coprime to everything before it, so its factorisation never reuses a prime; and the size of the next term has nothing to do with the size of the last. Five follows 53, and a seven-digit prime follows 5. By hand the steps stop being practical at the ninth term, whose number has fourteen digits and turns out to be prime — checking that by trial division means dividing by every prime up to its square root, about six million, some four hundred thousand primes in all — and from then on the sequence belongs to computers and to the methods of factorisation they run.

Euclid’s column of 1s #

The machine’s guarantee — that no prime repeats — is Euclid’s argument, and it can be seen directly.

Every number $N_k$ is one more than a multiple of every earlier term, so dividing it by an earlier term leaves remainder 1. In the figure those cells form columns of 1s that begin as soon as a prime enters the sequence and never end. The new term is the first prime, reading left to right, whose remainder is 0: at the second step it is 3, at the third 7, at the fifth 13, at the seventh 5 — which had been passed over at every earlier step because $N_k$ happened not to be a multiple of 5. A prime enters the sequence when, for the first time, it divides $N_k$ and nothing smaller does.

For the primes not yet in the sequence the remainders wander. The column for 19 reads 3, 7, 5, 2, 14, 6, 7, 5, 2, 7, 11, 16, 9, 12, 4, 2, 5, 16: no visible pattern, and no zero yet. Whether that column ever reaches 0 — whether 19 ever enters — is the question the sequence is famous for.

The numbers and the primes they yield #

The numbers’ sizes are predictable: $N_{k+1} - 1 = (N_k - 1) \cdot p_k$, so the number of digits grows by the number of digits of each new term. The primes found are not predictable at all. The eighth and ninth terms are a seven-digit and a fourteen-digit prime, because $N_8$ and $N_9$ happen to be prime themselves, so their smallest prime factor is the whole number. The tenth term is 139 and the twelfth is 11. A large number’s smallest prime factor is usually small — a random number is even half the time, a multiple of 3 a third of the time — and occasionally enormous, when the number has no small factors, and nothing about the construction tilts the odds.

That erratic behaviour is what makes the sequence hard. It reaches 11 only at the twelfth step and 17 at the thirteenth, after primes with seven and fourteen digits; it has not reached 19 after twenty steps. The figure below shows how sparsely the small primes are covered.

Other proofs, other machines #

Euclid’s is not the only proof of infinitude that can be run. Infinitely many of one kind used a variant to show that there are infinitely many primes leaving remainder 3 on division by 4: multiply such primes, multiply by 4 and subtract 1, and the result must have a factor of the same kind. Run as a machine from 3, it produces primes of that form one after another, and the same question arises — does it produce all of them? — with the same answer: nobody knows. The general theorem that every residue class contains infinitely many primes, every class and in equal shares, was proved by Dirichlet with analysis precisely because no Euclid-style machine is known for most classes.

Christian Goldbach’s proof uses the Fermat numbers $2^{2^n} + 1$, any two of which are coprime, so each contributes a prime the others lack; as a machine it is fixed in advance, needing no factorisation to define, but which primes it reaches depends on factoring Fermat numbers, a task that has stalled at the twelfth. Filip Saidak’s proof of 2006 iterates $n \mapsto n(n+1)$, each step gaining at least one new prime factor; as a machine it produces numbers with more and more distinct prime factors, and again says nothing about which.

So every elementary infinitude proof is a machine of this kind: it manufactures a number guaranteed to contain a new prime, and leaves the prime’s identity to factorisation. The sieve that cannot finish found the analytic side of the same limitation — the sieve can bound how many primes there are and cannot name them — and the Euclid–Mullin sequence is the most transparent instance of it, because its machine is the oldest and its question the simplest.

How small is a smallest factor #

Why does the sequence keep producing small primes, and occasionally a huge one? The answer is a fact about typical numbers. A number chosen at random has a smallest prime factor below $y$ with probability $1 - \prod_{q \le y}(1 - 1/q)$, which for large $y$ is close to $1 - e^{-\gamma}/\ln y$ by Mertens’ theorem — so the chance that a large number has no prime factor below a million is only about $1/(1.78 \cdot 13.8) \approx 4\%$, and below a billion about $2.7\%$. Most numbers have a small smallest factor; a few percent have none below any bound one cares to name, and among those are the primes themselves.

The Euclid–Mullin numbers are not random — they are coprime to every earlier term, which removes those primes as possible factors — but the observed terms behave as the heuristic suggests: mostly small, with occasional giants at the steps where $N_k$ is prime or has only large factors. How many primes a typical number has described the matching statistics for the number of prime factors; for the smallest factor, the same probabilistic model of the integers predicts the erratic bars in the growth figure, and nothing in it can be turned into a proof about this particular sequence.

The same heuristic explains why the machine stalls rather than slows. Each step needs only the smallest prime factor of $N_k$, and when that factor is small it is found at once by trial division. When it is not — when $N_k$ is prime, or a product of large primes — the step needs either a proof that $N_k$ is prime or a complete factorisation of a number with hundreds of digits, and the cost of the second grows faster than any power of the number of digits by every known method. Because the numbers grow doubly exponentially, the chance of meeting such a step rises with every term, and one of them is enough to stop everything after it: there is no way to compute the next term without the current one. The twenty terms certified here include eight whose primality rests on probabilistic tests rather than proofs, which is the same wall seen from the near side.

Mullin’s question #

Mullin asked whether every prime appears. Among the roughly fifty known terms, many small primes have appeared and some have not, and for every prime not yet seen it is unknown whether it ever will be. Daniel Shanks conjectured in 1991 that every prime does appear, with a heuristic: if the remainders $N_k \bmod p$ for an unseen prime $p$ behave like independent random numbers — and the residue figure suggests nothing to the contrary — then each step has about a $1/p$ chance of hitting 0, and an infinite sequence of such chances hits 0 eventually with probability one.

The heuristic is reasonable and proves nothing. The remainders are not random: $N_{k+1} \equiv (N_k - 1) p_k + 1 \pmod p$, a deterministic recurrence driven by the terms themselves, which are themselves determined by factorisations nobody can predict. Showing that the recurrence eventually hits 0 for every $p$ would need control over the smallest prime factors of a sequence of numbers growing doubly exponentially, and no method gives control of that kind. It is a cousin of the problems which infinitudes are proved surveyed, where a simple argument proves that a set is infinite and says nothing about which members it contains.

The machine with the other rule #

Taking the largest prime factor instead of the smallest gives a second sequence, and for it something can be proved.

The two sequences agree for four terms and then part at 1807 = 13 · 139, where one takes 13 and the other 139. The largest-factor sequence then runs through 50207, 340999, 2365347734339 and on into primes of sixteen digits, passing over 5, 13, 17, 23 and others as smaller factors it does not keep. Andrew Booker proved in 2012 that it misses infinitely many primes: some primes can never be its largest factor at the moment they would be needed, and he showed there are infinitely many such. So of the two natural rules, the one that seems wasteful provably misses infinitely much, and the one that seems thorough is open — very likely complete, and unproved.

The contrast is instructive. The largest-factor rule has a structural weakness that can be exploited: once a small prime is passed over, the sequence’s numbers grow so fast that the small prime’s chance of being the largest factor later is negligible, and Booker turned that into a proof. The smallest-factor rule has no such weakness, and the absence of a weakness is not something one can prove.

What the table certifies and what it does not #

Each term in the table is a theorem: the factorisation is checked exactly, every factor is shown to be at least the term, and every factor below $3.3 \times 10^{24}$ is proved prime. For the eight terms whose numbers have larger factors, the table certifies the term only as the smallest factor of a product of strong probable primes; if one of those large factors were composite — which no known number passing all twelve tests is — its own factors could in principle be smaller than the term. Standard primality proofs, by elliptic curves for instance, would close the gap in seconds per factor — methods descended from the certificate that an order that proves a prime described — and the table shows the gap rather than closing it.

The certificates also have a direction worth noticing: they were found once, slowly, and can be checked quickly by anyone. Finding the factorisation of the twentieth number took a minute and a half of computation; multiplying it back and running the twelve tests on each factor takes a fraction of a second. That asymmetry between finding and checking is the same one that makes factorisation useful in cryptography, and it is why the table can carry proofs rather than bare claims.

The residue figure and the coverage figure are finite. They show what twenty steps do, and nothing in them bears on Mullin’s question, which concerns all steps. The appearance of randomness in the residues is an observation, not a theorem, and the whole difficulty of the problem is that it might be misleading.

Still open: every prime, and even one more #

The central question is open: does every prime appear in the Euclid–Mullin sequence? It is not even known for any specific prime that has not already appeared. A positive answer for a single unseen prime would require either computing far enough to find it — impossible beyond a few more terms, because the numbers to be factored are too large — or a theoretical argument, and none exists.

There are related questions with partial answers. Variants that start from a different prime, or take the smallest factor among those in a given residue class, have been studied, and for some of them computations reach further; for none is completeness proved. Booker and others have proved, for certain variants of the construction, that every prime appears — by modifying the rule so that a prime that has been passed over is given a way back in — which shows what kind of argument is needed and that Mullin’s own rule does not provide it. And the computation itself is a frontier: the next terms wait on the factorisation of numbers of several hundred digits, which is beyond the general-purpose methods available today.

A proof that cannot answer its own question #

Euclid’s argument is usually admired for its economy: it shows that the primes are infinite without saying anything about where they are. Run as a machine, that economy becomes a limitation. The argument guarantees a new prime at every step and is silent about which, and the sequence of its outputs — determined completely, computable term by term while factoring allows — turns out to encode a question nobody can answer about the very primes the argument was designed to produce.

That is a recurring pattern in number theory: a construction simple enough to explain in a sentence, generating a sequence whose behaviour depends on factorisations no theory predicts. The Euclid–Mullin sequence is its purest example, because its construction is the most famous proof in the subject, and its open question — whether the proof, run forever, eventually names every prime — is the question the proof itself was too economical to answer.