I had always heard that there was no formula for a function, p(n), which would, for any n, give the nth prime number. For example, p(1)=2, p(2)=3, p(5)=11, etc. For example, here is a Mathematics Stack Exchange item, “Is there a known mathematical equation to find the nth prime?”, which answers in the negative and has been viewed 60,000 times.
But, in 1964, one C. P. Willans, about whom little or nothing is known other than his giving his address as “The University, Birmingham”, published the following formula:
which, if you experiment with it, you’ll find does for all values of n, compute the nth prime number.
What is going on? And what does the cosine function, \pi, and factorials have to do with the prime numbers?
Well, it turns out that while you can prove that there is no polynomial function that will compute the nth prime, that doesn’t mean there aren’t other functions that will. Finding the nth prime is a simple job of computer programming, especially if you don’t care how efficient your program is. What the redoubtable C. P. Willans has done is figure out a way to use the mathematical operation of summation combined with a prime-testing identity and the floor of the cosine function to flag primes, as a
for loop with an
if statement inside it, then wrap the whole thing with another iteration-simulating summation to create a hideously inefficient yet perfectly correct function that computes the nth prime. The final bit of magic is the Bertrand–Chebyshev theorem which we discussed here on 2022-05-22, that provides the upper bound on the outermost summation, guaranteeing that the nth prime is within the range tested by the inner loop.
All of the pieces of this formula: summations, factorials, exponentiation, the cosine, and the floor function, are regular mathematical operations which appear in myriad other mathematical theorems, but here they’ve been used as a programming language to implement a program to iteratively find the nth prime.