A Formula for the Nth Prime Number

SCANALYZER Tracking with Closeups
, , , ,
1

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:

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

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.

Here is Willans’ original paper “On Formulæ for the Nth Prime Number” [PDF]. Wikipedia has a wrap-up of other dodgy ways to create a “Formula for primes”.

6 Likes
2

The implications for Cryptography are obvious. Though currently—randomness and random numbers have a great allure for me. Especially for Cryptology.

It’s always: how to simply and securely share a key

3

I ran across BBP-type formulas yesterday while chasing down some algorithmic probability cites. I had not previously been aware of them or of “spigot functions” based on BBP-type formulas.

Today I found this very recently published paper (like 2 months ago) that generalizes the search for BBP-type formulas. The thing about BBP-type formulas that fascinates me is the potential they may hold for short programs that represent arbitrary precision numbers – wishfully thinking arithmetic coding of datasets here.

BBP-TYPE FORMULAS — AN ELEMENTARY APPROACH SIMON KRISTENSEN AND OSKAR MATHIASEN

Abstract. We provide a simple way of searching for formulas of
the Bailey–Borwein–Plouffe type together with an algorithm and
an implementation in sage. Aside from rediscovering some already
known formulas, the method has been used in the discovery of a
new BBP-type formula for √3π. In addition, the implementation
is very flexible and allows us to look for BBP-type formulas to
irrational bases but with integer coefficients. As an example of
this, searching in various Pisot bases, we have discovered a formula
for π in base 1 + √3, along with additional formulas.

1 Like