Problem 30 : A Formula for the nth prime

We will build the formula bottom up. So, let us begin!

Wilson’s Theorem ft. Quick Proof

If \(p\) is a prime number then we must have \((p-1)! \equiv -1 (mod p)\).

It is easy to see that by the definition of a prime number if \(p\) is not prime, it will be divisible by some number in between \(1\) and \(p-1\). This implies that for any non-prime number \(p\) we have, \((p-1)! \equiv 0 (mod p)\).

Now, if \(p\) is prime, we are sure to have a non-zero remainder in the congruence relation. Furthermore, note that for any number \(x\) in the range from \(2\) to \(p-2\) we must have another number \(y\) within the same range such that \(xy \equiv 1 (mod p)\). This can be understood by first noting that all numbers less than \(p\) are relatively prime to \(p\) i.e. \(gcd(q,p) = 1\) \(\forall q < p\). Furthermore, this fact combined with the Bezout’s Lemma (See Proof) which guarantees the existence of \(s,t\) such that \(qs + pt = 1\) gives us the result that \(qs \equiv 1\;(mod\;p)\) with \(s\) being the modulo inverse of \(q\).

Using Wilson’s Theorem to count primes

Now, we are in a position to use Wilson’s Theorem to count primes! All we need to do is plug it into a function that would gives us zeros/ones depending on the primality. To this end, we can utilize a the cosine function as follows,

\[\# \; of \; primes \; \leq i = \sum_{j=1}^i\left[\left(\cos \frac{(j-1) !+1}{j} \pi\right)^2\right]\]

where the argument of the cosine is going to be a multiple of \(\pi\) (thus, yielding a value of 1) if and only if \(j\) is a prime.

Using the prime counter to find the \(n^{th}\) prime

This is where the Willan’s formula uses an interesting approach. I will directly reveal what’s going on here..

The following function, \(f(x) = \left\lfloor{\left(\frac{x}{a}\right)}^{\frac{1}{x}}\right\rfloor\)

attains a value over \(1\) for all values of \(x\) greater than \(a\).

We can use this to our benefit! Instead of \(a\) we can have the squared cosine term in the denominator that counts the number of primes \(\leq i\) .

Then we can sum over all integers \(i\) for a fixed value of \(x\) so that we would know the value of \(i\) at which the value of the floor of the function changes from 0 to 1. A little thought will reveal that the value of \(i\) at which this cross-over from 0 to 1 happens as we increase \(i\) would be the \(x^{th}\) prime.

Bertrand’s Postulate

This is the final step. Based on the analysis so far we have the following the equation with an unknown quantity \(M\) that should be high enough so that we are able to reach the \(n^{th}\) prime,

\[P(n) =1+\sum_{i=1}^{M}\left\lfloor\left(\frac{n}{\sum_{j=1}^i\left\lfloor\left(\cos \frac{(j-1) !+1}{j} \pi\right)^2\right\rfloor}\right)^{1 / n}\right]\]

This is where we need Bertrand’s Postulate which states that there exists at least one prime number between \(m\) and \(2m\) \(\forall m \geq 2\).

Using the smallest value of \(m\) i.e. \(2\) and proceeding with the inequality iteratively we can see that \(n^{th}\) prime has to be less than \(2^n\) therefore, a value of \(M = 2^n\) would ensure that we get the right answer.

Final Formula – Willan’s Formula

Now we can stare at the final formula for the \(n^{th}\) prime which is pretty expensive and utilizes Wilson’s Theorem at its core.

\[P(n) =1+\sum_{i=1}^{2^n}\left\lfloor\left(\frac{n}{\sum_{j=1}^i\left\lfloor\left(\cos \frac{(j-1) !+1}{j} \pi\right)^2\right\rfloor}\right)^{1 / n}\right]\]