As some of you know, I was trained as a mathematician. I’ve always been a bit of a math nerd and read about mathematics even as a child. Long ago, probably when I was still in elementary school, I read that there was no closed form formula for calculating primes. That is, there was no formula that you could plug \(n\) into and get the nth prime as a result. That fact has been an article of faith for me for essentially my entire life. Except it isn’t true.
In 1964, C.P. Willans produced such a formula. Here it is:
\[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)^\frac{1}{n}\right\rfloor\]
where \(p_n\) is the nth prime.
There are a couple of things to notice about the formula:
- It uses only elementary mathematical operations. The most complicated one is the cos function.
- It’s hugely computationally expensive. That first sum has an upper limit of \(2^n\), which grows very quickly and the inner sum has a factorial which is also computationally expensive for large \(n\).
The second thing is why the formula isn’t really very useful. It just takes too long to make the calculation for even moderately large \(n\).
Even more interesting is why the formula works. Primes, after all, are distributed randomly so the existence of such a formula is a surprise. The reason it works is the most surprising thing of all: it’s essentially a program that tests each integer for primality, producing a 1 if so and a 0 if not. When the (outer) sum is \(n\), you’ve found the nth prime.
That sounds complicated but it’s really simple. Eric Rowland has a video that explains the formula in very simple terms that any Irreal reader will understand. It’s less than 15 minutes and definitely worth watching is you have even a little bit of interest in these things. If nothing else, it’s an example of a simple mathematical formula implementing a program.