Simple Formula Makes Prime Numbers Easy, but a Million-Dollar Mystery Remains

Would you like to be a millionaire? There are several ways to fulfill this dream. For two decades the U.S. edition of Who Wants to Be a Millionaire? promised a million dollars if you could answer 15 challenging questions correctly. Today you could win that prize by answering just one question: How are prime numbers distributed on the number line? In doing so, you would solve the so-called Riemann hypothesis, one of seven “Millennium Problems,” the solutions of which are rewarded with $1 million each.

In fact, the Riemann hypothesis is not the only important mathematical problem related to prime numbers. For example, the Goldbach conjecture states that any even number greater than 2 can be expressed by the sum of two prime numbers (4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, and so on). Solving this conjecture would not be rewarded with a million dollars or euros but with fame and honor in the math community. That so many puzzles about prime numbers still remain seems astonishing—after all, several formulas for calculating prime numbers exist.

One such “prime number generator” is the formula for the nth prime number by C. P. Willans. This function, p(n), spits out the nth prime number for any value of n. For example, for n = 5, this formula returns p(5) = 11 because 11 is the fifth prime number.

On supporting science journalism

If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.

That formula should be able to solve all the mysteries about prime numbers, right? Not quite.

The idea behind Willans’s formula is to first find a function that detects prime numbers—we’ll call that function f(x). If the detector works, the function will give you a 1 every time it detects a prime number (whenever you input a number or equation equal to a prime number value). Otherwise the function will give you a 0, meaning that no prime number is detected.

[Read more about the search for prime numbers]

Once you have this prime-number-detecting function, you can convert it into a prime number generator.

Building a Generator from a Detector

Let’s assume you have found your prime number detector function, f(x). With its help, you can infer the quantity of prime numbers within a given interval. If, for instance, you add the values f(1) + f(2) + f(3) + ... + f(10), the result will be the number of all prime numbers between 0 and 10—namely, 4. (If you are curious, the prime numbers in that interval are 2, 3, 5 and 7).

You can take a closer look at the individual summands over f:

f(1) = 0,
f(1) + f(2) = 1,
f(1) + f(2) + f(3) = 2,
f(1) + f(2) + f(3) + f(4) = 2,
f(1) + f(2) + f(3) + f(4) + f(5) = 3,
f(1) + f(2) + f(3) + f(4) + f(5) + f(6) = 3,
f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) = 4...

Already there’s a pattern here. If you want to determine the fourth prime number, say, you have to find the smallest number x for which the sum f(1) + f(2) + ... + f(x) = 4. In the example above, x = 7.

This principle can be generalized. The nth prime number is the smallest natural number x for which f(1) + f(2) + ... + f(x) = n. What all of this means is that if you can express this procedure with a function that will deliver the searched value x, you will have created a prime number generator.

Let’s do that together. First, it’s helpful to introduce another auxiliary function g(x) corresponding to the sum f(1) + ... + f(x). Thus:

g(1) = f(1) = 0,
g(2) = f(1) + f(2) = 1,
g(3) = f(1) + f(2) + f(3) = 2,
g(4) = f(1) + f(2) + f(3) + f(4) = 2,
g(5) = f(1) + f(2) + f(3) + f(4) + f(5) = 3,
g(6) = f(1) + f(2) + f(3) + f(4) + f(5) + f(6) = 3,
g(7) = f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) = 4 ...

So going back to the search for the fourth (or more generally the nth) prime, you would have to count how many values of x there are for which g(x) is smaller than 4 (or n). In this way, you will obtain the value of the fourth (or nth) prime number you are looking for.

Indeed, there is a function that does exactly that. Do not be alarmed—it looks complicated, but it is quite harmless:

Let’s break that down a bit. The square brackets ⌊ and ⌋ indicate that you should round down the value inside them. So, for example, ⌊ 1.7 ⌋ = 1 and ⌊ 1.12111167545 ⌋ = 1.

In this case, the term inside the square brackets seems a bit more complex. To better understand it, look at this corresponding figure that graphs that term, assuming a fixed value for i, in this case 4, and the variable n:

What you can now see is that, regardless of how large or small n is, the term inside the square brackets

takes a value between either 0 and 1 or 1 and 2. So with the surrounding square rounding brackets, the expression returns to either 0 or 1.

In fact, 1 will always be the result so long as g(i) is less than n. On the other hand, as soon as g(i) equals n or exceeds n, the result will be 0. The outer total is only used to add up the contributions.

So if you evaluate the formula for n = 4 to get the fourth prime number, the following comes out:

This works not only for n = 4 but also for any n. By using this formula, you can always get the nth prime number.

But so far I have suppressed one piece of information. We have assumed that a prime number detector f exists—without my telling you what that function looks like or how it works.

Here’s the big reveal. It, too, seems daunting at first sight but is not that complicated:

We already know about the square brackets. Because the squared cosine only returns values between 0 and 1, this guarantees that f(x) can only be 0 or 1—which is what we want in a detector function. But for which values of x does f(x) = 0, and for which values will the function equal 1?

To answer that question, one must consider the argument of the cosine function: π x [(x-1)! + 1]⁄x. The exclamation point denotes an arithmetic operation known as a factorial, which multiplies all natural numbers up to the number before the factorial. That is, 5! = 1 x 2 x 3 x 4 x 5 = 120.

Now if you plug in different values for x and evaluate the fraction π x [(x-1)! + 1]⁄x, you get the following results:

Notice the pattern? If x is a prime number, the result is an integer multiple of π; otherwise it is not. This is true for all values of x.

It turns out this has been demonstrated several times in history. Though it’s known as Wilson’s theorem—named for mathematician John Wilson, who presented this connection in the 18th century as a conjecture—it was also proved by Joseph-Louis Lagrange in 1771. But he was far from the first to demonstrate it. In fact, the Arab scholar Abu Ali al-Hasan ibn al-Haytham formulated a corresponding conjecture around the year 1000.

The Million Dollars Remains Unclaimed

Wilson’s theorem can be used to build a detector: the cosine of an integer multiple of π always yields 1 or -1, while all other arguments of the cosine function, on the other hand, yield a result smaller than 1. This completes the prime number detector. By rounding off the squared cosine function (through the square brackets), f(x) returns the value 1 as desired if x is a prime and 0 otherwise.

By putting all the information obtained so far together, a practical formula for calculating prime numbers can be given:

Feel free to try it yourself. If you want to calculate the fifth prime, all you have to do is substitute n = 5 into the formula, and you will get the correct result, 11.

In fact, this equation was published back in 1964 by a certain C. P. Willans. Details of Willans’s identity remain unknown. He authored no other technical articles. But we can assume that Willans did not became a millionaire with this formula. Not only did the Millennium prizes not yet exist, but also his formula cannot answer any of the major mathematical questions connected to prime numbers.

You have probably noticed the main problem with the equation if you’ve tried to use it. These calculations are quite involved. Even computers have a hard time evaluating the formula, especially for large values of n. Among other things, the factorial is part of the problem: the values quickly become extremely large, and the calculations require a lot of computing power.

If you wanted to calculate enormous prime numbers, you would overtax every supercomputer in the world. So to become a millionaire, you will need to find a different path. Maybe it’s time to hit the game shows.

This article originally appeared in Spektrum der Wissenschaft and was reproduced with permission.