Formulas for calculating primes do exist; however, they are computationally very slow.
is the floor function, which rounds down to the nearest integer.
[1] This formula is not an efficient way to generate prime numbers because evaluating
Jones et al. (1976) found an explicit set of 14 Diophantine equations in 26 variables, such that a given number k + 2 is prime if and only if that system has a solution in nonnegative integers:[7] The 14 equations α0, …, α13 can be used to produce a prime-generating polynomial inequality in 26 variables: That is, is a polynomial inequality in 26 variables, and the set of prime numbers is identical to the set of positive values taken on by the left-hand side as the variables a, b, …, z range over the nonnegative integers.
A general theorem of Matiyasevich says that if a set is defined by a system of Diophantine equations, it can also be defined by a system of Diophantine equations in only 9 variables.
On the other hand, there also exists such a set of equations of degree only 4, but in 58 variables.
[9] The first such formula known was established by W. H. Mills (1947), who proved that there exists a real number A such that, if then is a prime number for all positive integers n.[10] If the Riemann hypothesis is true, then the smallest such A has a value of around 1.3063778838630806904686144926... (sequence A051021 in the OEIS) and is known as Mills' constant.
This formula has no practical value, because there is no known way of calculating the constant without finding primes in the first place.
The first few primes generated are: Without assuming the Riemann hypothesis, Elsholtz developed several prime-representing functions similar to those of Mills.
[13] Another tetrationally growing prime-generating formula similar to Mills' comes from a theorem of E. M. Wright.
He proved that there exists a real number α such that, if then is prime for all
[14] Wright gives the first seven decimal places of such a constant:
given in the article is precise enough for equation (1) to generate the primes through 37, the
As with Mills' formula and Wright's formula above, in order to generate a longer list of primes, we need to start by knowing more digits of the initial constant,
, which in this case requires a longer list of primes in its calculation.
In 2018 Simon Plouffe conjectured a set of formulas for primes.
a certain number between 0 and one half, Plouffe found that he could generate a sequence of 50 probable primes (with high probability of being prime).
Presumably there exists an ε such that this formula will give an infinite sequence of actual prime numbers.
The number of digits starts at 501 and increases by about 1% each time.
[17][18] It is known that no non-constant polynomial function P(n) with integer coefficients exists that evaluates to a prime number for all integers n. The proof is as follows: suppose that such a polynomial existed.
The same reasoning shows an even stronger result: no non-constant polynomial function P(n) exists that evaluates to a prime number for almost all integers n. Euler first noticed (in 1772) that the quadratic polynomial is prime for the 40 integers n = 0, 1, 2, ..., 39, with corresponding primes 41, 43, 47, 53, 61, 71, ..., 1601.
The phenomenon is related to the Ulam spiral, which is also implicitly quadratic, and the class number; this polynomial is related to the Heegner number
It is known, based on Dirichlet's theorem on arithmetic progressions, that linear polynomial functions
[19] It is not even known whether there exists a univariate polynomial of degree at least 2, that assumes an infinite number of values that are prime; see Bunyakovsky conjecture.
Another prime generator is defined by the recurrence relation where gcd(x, y) denotes the greatest common divisor of x and y.
Rowland (2008) proved that this sequence contains only ones and prime numbers.
However, it does not contain all the prime numbers, since the terms gcd(n + 1, an) are always odd and so never equal to 2.
587 is the smallest prime (other than 2) not appearing in the first 10,000 outcomes that are different from 1.
Nevertheless, in the same paper it was conjectured to contain all odd primes, even though it is rather inefficient.
[20] Note that there is a trivial program that enumerates all and only the prime numbers, as well as more efficient ones, so such recurrence relations are more a matter of curiosity than of any practical use.