When Euclid's number is itself prime

There is no last prime built Euclid’s argument from one number. Take the primes up to $p$, multiply them, and add one. The result, $p\# + 1$ in the usual notation, leaves remainder one on division by every prime up to $p$, so none of them divides it, and any prime factor it has is a prime beyond $p$. Euclid’s proof run as a machine followed that argument as a procedure, always taking the smallest new factor, and asked which primes the procedure eventually reaches.

There is a simpler question about the same numbers, and it is older than either essay. Sometimes $p\# + 1$ is not merely divisible by a new prime but is itself prime. $2 + 1 = 3$, $6 + 1 = 7$, $30 + 1 = 31$, $210 + 1 = 211$ and $2{,}310 + 1 = 2{,}311$ are all prime, and a reader meeting Euclid’s argument for the first time often concludes that the construction always produces a prime. The next one, $30{,}031 = 59 \times 509$, is the classic correction. The question here is how often the construction does produce a prime, for $p\# + 1$ and its twin $p\# - 1$, and what the answer says about a famous kind of open problem.

Testing numbers of four hundred digits #

The numbers grow quickly. $p\#$ has about $p/\ln 10$ digits, because the logarithm of the product of the primes up to $p$ is close to $p$ — a form of the prime number theorem. For $p = 1{,}097$, the largest prime in the figure, $p\# \pm 1$ have 464 digits. No number of that size can be factored by trial division, and none can be certified prime by checking divisors.

The figures use the Miller–Rabin test instead. For a candidate $N$, write $N - 1 = 2^s d$ with $d$ odd and compute $a^d, a^{2d}, \ldots$ modulo $N$ for a fixed base $a$. If $N$ is prime, the sequence either starts at 1 or reaches $N - 1$ before it reaches 1, because the only square roots of 1 modulo a prime are $\pm 1$. A composite number fails this for most bases, and a number that passes for twelve independent bases is called a probable prime. Every probable prime in the figures matches the published lists of primorial and factorial primes, found by searches that went on to prove primality with methods suited to numbers of these special forms.

The cost is a few thousand multiplications of 1,500-bit numbers per test, a few milliseconds each. Each multiplication is followed by a reduction modulo $N$, so the numbers never grow past twice the size of $N$ however large the exponent, which is what makes a test on a 464-digit number cheap even though the exponent itself has 464 digits. The whole of the hero figure, 368 numbers of up to 464 digits, takes a few seconds.

The test on two small cases #

The test is easiest to see on two of the table’s entries. For $2{,}311 = 11\# + 1$, $N - 1 = 2{,}310 = 2 \times 1{,}155$, so $s = 1$ and $d = 1{,}155$. Then $2^{1{,}155}$ modulo $2{,}311$ comes out exactly 1, the sequence starts at 1, and base 2 is consistent with $2{,}311$ being prime, as it is. For $30{,}031 = 13\# + 1$, $N - 1 = 30{,}030 = 2 \times 15{,}015$. Then $2^{15{,}015}$ modulo $30{,}031$ is $13{,}635$, which is neither 1 nor $30{,}030$, and since $s = 1$ there is no further squaring in which $-1$ could appear. One modular exponentiation proves that $30{,}031$ is composite, without finding its factors 59 and 509.

That asymmetry is the whole method. A failure is a proof of compositeness; a pass is only evidence of primality, since a composite number can pass for an unlucky base. Michael Rabin showed that at most a quarter of bases let a composite pass, so twelve independent passes leave a composite a chance below one in sixteen million. That is not a proof. For special forms like $p\# \pm 1$, where $N \mp 1$ is completely factored, the converse of Fermat’s theorem in the form an order that proves a prime used turns a pass into a certificate. That is how the published lists were proved rather than merely believed. For general numbers the row that proves a prime gave a deterministic polynomial-time test, too slow at these sizes to use in practice.

Nine of each, and where they stop #

Up to 1,100, $p\# + 1$ is prime for $p = 2, 3, 5, 7, 11, 31, 379, 1019$ and $1021$, and $p\# - 1$ is prime for $p = 3, 5, 11, 13, 41, 89, 317, 337$ and $991$. Below 1,100 there are nine of each kind. The distribution is the striking thing. Five of the nine with the plus sign occur at the first five primes; after $p = 11$ there is one at 31, then a gap of 348 to 379, then a pair at 1019 and 1021. The searches that produced the published lists have continued to $p$ in the millions. They have found a couple of dozen of each kind in all, each at a larger $p$ than the last, the largest with more than a million digits.

The table shows the composite cases at small sizes. Every factor of every entry exceeds the $p$ in its row, which is Euclid’s argument working. But the factors can be anything above $p$. $510{,}511 = 19 \times 97 \times 277$ for $p = 17$ is a product of three new primes, and $304{,}250{,}263{,}527{,}211 = 61 \times 4{,}987{,}709{,}238{,}151$ for $p = 41$ splits into a small new prime and a large one. Euclid’s argument is satisfied every time. Only for the coloured entries is the whole number a single prime.

The chance a number with no small factor is prime #

Why are primes among these numbers so rare, and yet not so rare as to stop? A random number of size $N$ is prime with chance about $1/\ln N$, by the prime number theorem. For a 464-digit number that is about one in 1,070. But $p\# \pm 1$ is not a random number: by construction it has no prime factor up to $p$. That raises its chance considerably.

A random number avoids the prime $q$ with chance $1 - 1/q$. If those events were independent, a random number would avoid every prime up to $p$ with chance $\prod_{q \le p}(1 - 1/q)$. Franz Mertens proved in 1874 that this product is close to $e^{-\gamma}/\ln p$, where $\gamma = 0.5772\ldots$ is Euler’s constant — the “third theorem” that the primes are what is left over used to measure how much the sieve removes. So conditioning on having no factor up to $p$ multiplies the chance of being prime by about $e^\gamma \ln p$. For $p$ near 1,100 that is 12.5, and the chance that $p\# \pm 1$ is prime becomes about one in 86 rather than one in 1,070.

That gives an estimate for every $p$:

$$\Pr(p\# \pm 1 \text{ is prime}) \approx \frac{e^\gamma \ln p}{\ln(p\#)} \approx \frac{e^\gamma \ln p}{p}.$$

It is a heuristic, not a theorem. It treats a specific number as if it were random apart from the one property that is known about it, and there is no proof that $p\# + 1$ is “random” in any sense. But the same kind of estimate predicts the counts of primes of many special forms accurately, and it is the only guide available.

Found against expected #

Summing the estimate over the primes gives an expected count.

The sum of $e^\gamma \ln p / p$ over primes up to $x$ grows like $e^\gamma \ln x$, by Mertens’ first theorem. At $x = 1{,}100$ it is 13.3 for each sign. Nine of each were found, somewhat fewer than expected, but within the variation that a count of rare events of this size allows: a Poisson count with mean 13 is nine or fewer about one time in six. The early excess is the small primes, where the heuristic is too crude; the later shortfall is a long stretch with none.

The more important feature is the growth rate. The expectation grows without bound, so the heuristic predicts infinitely many primorial primes of each sign. It grows extremely slowly, by $e^\gamma \approx 1.78$ for every factor of $e$ in $x$. Multiplying $x$ by a million adds only about 25 to the expected count. That matches the record of the searches, which have pushed $p$ into the millions and found only a couple of dozen of each kind in total. Each new one is a prime of hundreds of thousands or millions of digits, found after testing thousands of candidates that failed.

The factors Euclid’s argument finds #

When $p\# \pm 1$ is not prime, its prime factors are the new primes Euclid’s argument promises, and the smallest of them can be found by a cheaper computation than factoring.

The computation keeps $p\#$ modulo each small prime $q$ as a running remainder, multiplying by each new $p$ in turn. Then $q$ divides $p\# + 1$ exactly when the remainder is $q - 1$, and $p\# - 1$ when it is 1. That finds the smallest factor below 200,000 for 198 of the composite Euclid numbers. The other 151 have no factor that small, and their smallest factors are unknown here.

Every point is above the line $f = p$, as it must be. Above the line there is no visible structure: the smallest factor is sometimes just above $p$, sometimes a hundred times larger, sometimes beyond 200,000. That is the gap between Euclid’s argument and any description of the primes it finds. The argument guarantees a prime above $p$ and says nothing about where. Euclid’s proof run as a machine met the same gap from the other side, asking which primes the smallest-factor procedure eventually reaches, and there too the answer is unknown.

Factorials, for comparison #

There is a second family built the same way: $n! \pm 1$. Since $n!$ is divisible by every prime up to $n$, the numbers $n! \pm 1$ have no prime factor up to $n$, and Euclid’s argument works with them too. They are larger than primorials at the same $n$, but there is a candidate at every $n$ rather than only at the primes.

Up to $n = 170$, where $n!$ has 307 digits, $n! + 1$ is prime for $n = 1, 2, 3, 11, 27, 37, 41, 73, 77, 116$ and $154$, and $n! - 1$ for $n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94$ and $166$. The expected count is again of order $e^\gamma \ln x$, since each $n$ contributes about $e^\gamma \ln n / \ln n! \approx e^\gamma / n$. The two effects — larger numbers, more candidates — cancel almost exactly. The found counts, eleven and twelve, sit close to the expectation of 12.8. Two unrelated families, built on the same idea, agree with the same heuristic, which is some evidence that the heuristic captures something real about how primes fall among numbers with no small factor.

Why nobody can prove there are infinitely many #

That primorial primes are infinite is believed for the reason the figures show and proved by no one, and the reason it is hard is instructive. Euclid’s argument proves that there are infinitely many primes; it does not prove that any particular number in a sequence is prime. To show that infinitely many $p\# + 1$ are prime would require controlling the factorisation of an explicit sequence of numbers, and no method exists for doing that for any sequence that grows this fast.

The situation is the same for the other famous special forms. Whether there are infinitely many Mersenne primes $2^p - 1$, infinitely many Fermat primes $2^{2^k} + 1$, or infinitely many primes of the form $n^2 + 1$ is open. The heuristics predict infinitely many for the first and third and only finitely many for the second. That is the difference between a sum of chances that diverges and one that converges, and which infinitudes are proved set it out in general. Even the converse is out of reach here. It is not known that infinitely many $p\# + 1$ are composite, although nobody doubts it, because proving that a specific number is composite also needs an argument about its factors.

The heuristic is also the reason the problem attracts searches. A diverging expectation means there is always another one to find. A slowly diverging expectation means each one costs far more than the last. The searches have become exercises in distributed computing and specialised primality proving, and each new record is a measurement of the heuristic at a size no theory reaches.

What the figures cannot show #

Every figure here is exact for its range or a stated estimate. The probable-prime tests agree with published lists that were certified by other means, the counts are exact, and the factors are verified by division. What the figures cannot show is any trend beyond their range. Nine primorial primes of each sign up to 1,100 is a fact; the expectation of 13.3 is a model; the agreement between them at this size says nothing about whether there is a largest primorial prime.

The figures also show only one way of being prime among many that the numbers could have. Whether $p\# + 1$ and $p\# - 1$ can both be prime for the same $p$ — as for $p = 3, 5$ and $11$ — and whether that happens infinitely often, is a twin-prime question about this sequence. Up to 1,100 it happens only at those three small primes, and the heuristic suggests a reason. If the two events were independent, both would happen at $p$ with chance about $(e^\gamma \ln p / p)^2$, and the sum of that over all primes converges. So the estimate predicts only finitely many $p$ at which both $p\# + 1$ and $p\# - 1$ are prime — perhaps just the three already known. That is the opposite of its prediction for either sign alone, and it is just as unprovable.

Still open: infinitely many, of either kind #

Whether infinitely many $p\# + 1$ are prime is open, and so is the same question for $p\# - 1$, for $n! + 1$ and for $n! - 1$. The heuristic predicts infinitely many of each, about $e^\gamma \ln x$ up to $x$, and the searches agree with it as far as they reach. For the composite Euclid numbers, whether the smallest prime factor of $p\# + 1$ can be bounded in terms of $p$ is open too, which is part of why the Euclid–Mullin sequence resists analysis.

A related question with a partial answer concerns whether every prime divides some $p\# + 1$. The answer is no in a strong sense. A prime $q$ divides some $p\# + 1$ only if a product of the primes below $q$ is $-1$ modulo $q$, and that condition fails for many $q$. The question of which $q$ appear as factors of Euclid numbers is a question about the multiplicative structure of the primes modulo $q$, the territory of Wilson’s theorem and its refinements, where much is understood one prime at a time and little uniformly.

A construction that almost never does more than it promises #

Euclid’s number is guaranteed to bring a new prime, and that is all it is guaranteed to do. It is the new prime itself only nine times among the first 184 primes for each sign, and the times thin out like a slowly diverging sum. The thinning has a precise form: a number with no prime factor up to $p$ is $e^\gamma \ln p$ times likelier to be prime, and summing that over the primes gives $e^\gamma \ln x$. The factorial numbers follow the same estimate and the same thin record. Both families are believed to be infinite on this evidence. Neither has a proof, and the obstacle is the one this site meets wherever a specific sequence’s primality is in question: that $p\# + 1$ cannot be divided by small primes says nothing about its large factors.