Formula for primes: Difference between revisions

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=wz+h+j-q$

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

$0=(16k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}$

$0=2n+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=16r^{2}y^{4}(a^{2}-1)+1-u^{2}$

$0=n+l+v-y$

$0=(a^{2}-1)l^{2}+1-m^{2}$

$0=ai+k+1-l-i$

$0=((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}$

$0=p+l(a-n-1)+b(2an+2a-n^{2}-2n-2)-m$

$0=q+y(a-p-1)+s(2ap+2p-p^{2}-2p-2)-x$

$0=z+pl(a-p)+t(2ap-p^{2}-1)-pm$

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$

and then

$p_{n}=1+\sum _{k=1}^{2(\lfloor n\ln(n)\rfloor +1)}\left(1-\left\lfloor {\pi (k) \over n}\right\rfloor \right)$