Prime Generating Formulae

The prime numbers have challenged and perplexed the greatest mathematicians for millennia. Shortly before he died, the brilliant Hungarian number theorist Paul Erdös said “it will be another million years, at least, before we understand the primes”.

A remarkable polynomial: Theorem 1 from Jones et al., 1976.

The primes are scattered through the natural numbers in a manner that exhibits both order and chaos. For example, the probability of a number chosen at random in the interval from 1 to ${N}$ is about ${1/\log N}$ (this is the essence of the Prime Number Theorem). There is a systematic thinning out, with primes becoming relatively fewer as ${N}$ increases. In contrast, given some prime ${p_n}$ , we have no means of predicting where the next one will occur. It could be as close as ${p_n+2}$ , but it could also be arbitrarily far removed from ${p_n}$ .

Many efforts to find a formula for generating primes have ended in failure. The ultimate aim would be a function

$\displaystyle f(n) = p_n$

where we evaluate ${f}$ with argument ${n}$ to produce the ${n}$ -th prime number. This would enable us to generate primes of arbitrarily large values by evaluating the function with a sufficiently large argument. But no-one has ever found such a formula and no-one is hopeful of finding one soon.

Euler found a beautiful and simple polynomial formula

$\displaystyle n^2 + n + 41$

that takes a prime value for every integer argument ${n}$ from 0 to 39. Thus, it produces 40 primes before yielding a composite result ${1681 = 41^2}$ when ${n=40}$ . Many more complicated polynomials have since been found that produce longer sequences of primes. But in all cases the formulae eventually generate composite outputs.

A Formula that generates all the Primes

It was a great surprise when, in the 1970s, a formula was found that generates all the prime numbers. It is a polynomial with many variables and, whenever its value is positive, it is a prime number. As the inputs range through all positive integer values, every prime number is produced by the formula.

The origin of this solution lies in Hilbert’s Decision Problem: Is there an algorithm that can determine whether or not a mathematical proposition is true or false? Alan Turing, using a version of Cantor’s diagonal argument showing that the real numbers are uncountable, proved that no such algorithm is possible.

Turing devised a marvellous conceptual model that foreshadowed modern computers. It could follow a set of simple instructions (an algorithm) and produce a sequence of outputs. The American mathematician Julia Robinson showed that any list of numbers that could be generated by a Turing machine could also be described as the solution set of an equation. Since the prime numbers could be listed in this way using, for example, the Sieve of Eratosthenes, there must exist an equation generating them. The missing link in Robinson’s argument was supplied in 1970 by Yuri Matiyasevich. In technical language, the result may be stated thus: Every recursively enumerable set of numbers can be represented by a Diophantine polynomial.

Shortly afterwards, a 25-th order polynomial in 26 variables ${\{a, b, \dots , z\}}$ was constructed by Jones et al. (1976) [See figure at the head of this post]. Note that the second factor comprises a number of squares subtracted from unity. Thus, the values are mostly negative numbers, which we must discount. However, the positive values are all prime and, ultimately, include all prime values. While the formula is of interest it is of no practical value for generating primes.

Other Prime-generating Formulas

In 1947 William H Mills showed that there exists a real number ${\theta}$ such that

$\displaystyle \left\lfloor \theta^{3^n} \right\rfloor$

is prime for all ${n}$ . Assuming the Riemann Hypothesis, the value of Mills’ constant is

$\displaystyle \theta = 1.306\,377\,883\,863 \dots$

The largest known Mills prime has over a half-million digits. However, since the precise value of ${\theta}$ is unknown, or even its rationality or otherwise, the formula is of no practical use in finding large primes.

In 1958 Edward Wright showed that there is a number ${\omega \approx 1.9287800}$ such that

$\displaystyle \left\lfloor 2^{2^{\dots^{2^\omega}}}\right\rfloor$

is prime. In 1964, Willans produced the formula

$\displaystyle p_n = 1 + \sum_{k=1}^{2^n} \left\lfloor \sqrt[n]{ \frac{n}{1+\pi(k)} } \right\rfloor$

for which the first few values are 2, 11 and 1361. Here ${\pi(k)}$ is the prime counting function. These are amongst several prime generators that are astonishing in form but of little practical value for finding primes.

Sources

${\bullet}$ Jones, J. P., Sato, D., Wada, H. & Wiens, D., 1976: Diophantine representation of the set of prime numbers, Amer. Math. Monthly, 83, (6) 449-464. doi:10.2307/2318339.

${\bullet}$ Wikipedia article: Formula for primes.

ThatsMaths