Formula for primes

From Exampleproblems

A formula for primes in mathematics would be a mathematical formula generating the prime numbers, exactly and without exception. A great deal is known about what, more precisely, such a 'formula' can and cannot be.

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):

0 = w z + h + j - q

0 = (g k + 2 g + k + 1)(h + j) + h - z

0 = (16 k + 1) 3 (k + 2)(n + 1) 2 + 1 - f 2

0 = 2 n + p + q + z - e

0 = e 3 (e + 2)(a + 1) 2 + 1 - o 2

0 = (a 2 - 1) y 2 + 1 - x 2

0 = 16 r 2 y 4 (a 2 - 1) + 1 - u 2

0 = n + l + v - y

0 = (a 2 - 1) l 2 + 1 - m 2

0 = a i + k + 1 - l - i

0 = ((a + u 2 (u 2 - a)) 2 - 1)(n + 4 d y) 2 + 1 - (x + c u) 2

0 = p + l (a - n - 1) + b (2 a n + 2 a - n 2 - 2 n - 2) - m

0 = q + y (a - p - 1) + s (2 a p + 2 p - p 2 - 2 p - 2) - x

0 = z + p l (a - p) + t (2 a p - p 2 - 1) - p m .

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

$f(n) = 2 + (2(n!) \operatorname{mod} (n+1)).$

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; that is, when n + 1 is composite.)

Using the floor function $\lfloor x\rfloor$ (defined to be the largest integer less than or equal to the real number x), one can construct several formulas for the nth 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

$\pi(m) = \sum_{j=2}^m \frac { \sin^2 ( {\pi \over j} (j-1)!^2 ) } { \sin^2( {\pi \over j} ) }$

or, alternatively,

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

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

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

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

$\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$