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

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 (ie. 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 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

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