Formula for primes

In mathematics, it is known that no non-constant polynomial function P(n) exists that evaluates to a prime number for all integers n (or even almost all n). Using algebraic number theory one can make that quite precise.

The quadratic polynomial

P(n) = n² + n + 41

is prime for all non-negative integers less than 40. The primes for n = 0, 1, 2, 3... are 41, 43, 47, 53, 61, 71... The differences between the terms are 2, 4, 6, 8, 10... For n = 40, it produces a square number, 1681, which is equal to 41×41, the smallest composite number for this formula. In fact if 41 divides n it divides P(n) too. The phenomenon is related to the Ulam spiral, which is also implicitly quadratic, and the class number.

A set of diophantine equations in 26 variables can be used to obtain primes: A given number k + 2 is prime iff the following system of diophantine equations has a solution in the natural numbers (Riesel, 1994):

<math>0 = wz + h + j - q<math>

<math>0 = (gk + 2g + k + 1)(h + j) + h - z<math>

<math>0 = (16k + 1)^3(k + 2)(n + 1)^2 + 1 - f^2<math>

<math>0 = 2n + p + q + z - e<math>

<math>0 = e^3(e + 2)(a + 1)^2 + 1 - o^2<math>

<math>0 = (a^2 - 1)y^2 + 1 - x^2<math>

<math>0 = 16r^2y^4(a^2 - 1) + 1 - u^2<math>

<math>0 = n + l + v - y<math>

<math>0 = (a^2 - 1)l^2 + 1 - m^2<math>

<math>0 = ai + k + 1 - l - i<math>

<math>0 = ((a + u^2(u^2 - a))^2 - 1)(n + 4dy)^2 + 1 - (x + cu)^2<math>

<math>0 = p + l(a - n - 1) + b(2an + 2a - n^2 - 2n - 2) - m<math>

<math>0 = q + y(a - p - 1) + s(2ap + 2p - p^2 - 2p - 2) - x<math>

<math>0 = z + pl(a - p) + t(2ap - p^2 - 1) - pm<math>

The following function yields all the primes, and only primes, for non-negative integers n:

<math>f(n) = 2 + (2(n!) \operatorname{mod} (n+1))<math>

This formula is based on Wilson's theorem; the number two is generated many times and all other primes are generated exactly once by this function. (In fact a prime p is generated for n = (p − 1) and 2 otherwise (ie. when n + 1 is composite))

Using the floor function <math>\lfloor x\rfloor<math> (defined to be the largest integer less than or equal to the real number x), one can construct several formulas for the n-th prime. These formulas are also based on Wilson's theorem and have little practical value: the methods mentioned above under "Finding prime numbers" are much more efficient.

Define

<math>\pi(m) = \sum_{j=2}^m \frac

{ \sin^2 ( {\pi \over j} (j-1)!^2 ) } { \sin^2( {\pi \over j} ) } <math> or, alternatively,

<math> \pi(m) = \sum_{j=2}^m \left\lfloor {(j-1)! + 1 \over j} - \left\lfloor{(j-1)! \over j}\right\rfloor \right\rfloor <math>

These definitions are equivalent; π(m) is the number of primes less than or equal to m. The n-th prime number p_n can then be written as

<math>p_n = 1 + \sum_{m=1}^{2^n} \left\lfloor \left\lfloor { n \over 1 + \pi(m) } \right\rfloor^{1 \over n} \right\rfloor<math>

Another approach does not use factorials and Wilson's theorem, but also heavily employs the floor function (S. M. Ruiz 2000): first define

<math>\pi(k) = k - 1 + \sum_{j=2}^k \left\lfloor {2 \over j} \left(1 + \sum_{s=1}^{\left\lfloor\sqrt{j}\right\rfloor} \left(\left\lfloor{ j-1 \over s}\right\rfloor - \left\lfloor{j \over s}\right\rfloor\right) \right)\right\rfloor <math>

and then

<math>p_n = 1 + \sum_{k=1}^{2(\lfloor n \ln(n)\rfloor+1)} \left(1 - \left\lfloor{\pi(k) \over n} \right\rfloor\right) <math>

External links

• Prime-Generating Polynomial (http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html)

• Mill's Constant (http://mathworld.wolfram.com/MillsConstant.html)

• FRACTRAN (http://mathworld.wolfram.com/FRACTRAN.html)

• Formula for Primes, Twinprimes, Number of Primes, and Number of Twinprimes (http://www.ias.ac.in//jarch/mathsci/92/00000050.pdf) page 2 (http://www.ias.ac.in//jarch/mathsci/92/00000051.pdf) page 3 (http://www.ias.ac.in//jarch/mathsci/92/00000052.pdf) page 4 (http://www.ias.ac.in//jarch/mathsci/92/00000053.pdf) Erratum (http://www.ias.ac.in/jarch/mathsci/93/00000068.pdf)