An Exploration of Willans’ Formula: A Method of Computing The Nth Prime

1. Introduction

Willans’ formula [1] is an attempt to formulate a prime number counting function, meaning we can calculate the nth prime number. Already, its quite easy to list the first one, two, three; maybe even one-hundred. In fact, with a little thought it’s easy for most children to list a few; that is, after you define the primes of course. This article will explore the merit of the formula and critique it as other mathematicians have before, namely how slow and inefficient the formula is[2]. This article will follow the You Tube video by Eric Rowland titled ”An Exact Formula for the Primes: Willans’ Formula”[3] whilst providing further insight and interesting connections. Although inefficient, the formula does have some insight into the behaviour of primes and gives an idea of how to find them which can help us to make progress towards much harder questions regarding prime numbers like the Twin Prime Conjecture which we will touch on later.

2. Defining the primes

Defining the primes can sometimes seem quite challenging, however defining them is very important as, without a definition, we have no axioms upon which to build theorems and conjectures. The formal definition of a prime number is a natural number greater than 1 that cannot be written as the product of two smaller natural numbers. But what is meant by a natural number? You can think of natural numbers as counting numbers; the whole numbers that we are used to in our everyday lives.

{1, 2, 3, 4, 5, ..., n} ∈ N

You may be asking why is one not prime? Mathematicians have decided that one is not a prime number simply because if one was prime this would dismantle the fundamental theorem of arithmetic, which states that every number greater than one can be written uniquely as a product of primes disregarding the order of the products. Since we can write the number 1 as

1 = 1

or

1 = 1 x 1

or

1 = 1 x 1 x 1...

Mathematicians disregard one as prime due to its identity property. The natural numbers that are not prime and can be written as the product of two smaller natural numbers are called composite.

3.1 Introducing Willan's Formula

3.1 Wilson's Theoreom

We begin from the innermost section of the formula. Let

We will compute the first ten terms of Tj .

What do you notice about Tj when j is prime? Well, Tj is a positive integer for all primes p (and 1). Let’s prove this result.

Proof. If a number is its own multiplicative inverse modulo p ∈ P, then its square is congruent to 1 modulo p. Thus, we define a number x such that it is its own multiplicative inverse.

x^2 ≡ 1 (mod p)

=⇒ x^2 − 1 ≡ 0 (mod p)

=⇒ (x − 1)(x + 1) ≡ 0 (mod p)

=⇒ x − 1 ≡ 0 (mod p) or x + 1 ≡ 0 (mod p)

=⇒ x ≡ 1 (mod p) or x ≡ −1 (mod p)

We can rewrite x ≡ −1 (mod p) as x ≡ p − 1 (mod p), since adding the modulus does not change the congruence. Thus, we have proven that 1 and p − 1 are their own multiplicative inverses modulo p.

Let the set {2, 3, ...,(p − 2)} ∈ S.

∀a ∈ S, ∃b ∈ S such that ab = 1

We can pair each element in S to its own inverse. Here a−1 denotes the inverse of a (not 1/a).

(p − 1)! ≡ 1(2 × 2^−1)(3 × 3^−1)...((p − 2) × (p − 2)^-1)(p − 1) (mod p)

=⇒ (p − 1)! ≡ 1(1)(1)...(1)(p − 1) (mod p)

=⇒ (p − 1)! ≡ (p − 1) (mod p) =⇒ (p − 1)! ≡ −1 (mod p) by our earlier result.

It follows that (p − 1)! + 1 ≡ 0 (mod p) which means that

((p − 1)! + 1)/p is a whole number precisely when p ∈ P i.e. p divides (p − 1)! + 1 ∀p ∈ P

Now we have built a test for primality which will come in handy when trying to build a prime number counter.

3.2 Making Wilsons’ theorem useful

Now that we have a test for primality it is useful to try and compute a statement of true or false, a 1 or a 0, that our prime counter can use to keep track of what numbers are prime or not. To do this Wilan made use of the trigonometric function cosine.

We make use of the fact that

cos kπ = ±1, ∀k ∈ Z

Remember, (j−1)!+1/j∈ Z+, ∀j ∈ P, thus it follows that the cosine of (j−1)!+1/j is either 1 or -1 when j is prime and in the interval (-1,1) if j is composite. Let’s make the output strictly 1 if j is prime.

The new graph has been truncated to a smaller value so that we can clearly see the x-axis. Notice now that for all of the positive integer multiples of π the output is 1. Now we need all of the values between 1 and 0 that are not 1 to be a zero. This is where we make use of the floor function.

The floor function takes care of this problem. Now we can output a 1 if j is prime and a 0 if j is composite.

3.3 Counting the Primes

The summation

counts the number of primes up to i inclusive plus 1. The summation will add a 1 to the ”counter” when j is prime or one and add a 0 when j is composite.

For example, consider i = 5, the result when we want to compute the third prime

Essentially,

and for a general case

But why are we counting primes and not computing them? Well to compute the nth prime we ask is the number of primes up through n less than i. If we stay with our example of i = 5, We ask

What we have done is determined that there are 3 primes less than or equal to 6. The tabular above, gives us a hint as to why the formula works so slowly. I want to make a note that when we use the formula we do not choose a value for i instead the summation loops through j ∈ Z + asking the question is the number of primes less than or equal to i plus one less than n?

3.4 Introducing n

So far, we have not seen n in Wilans’ formula at all, yet we want to determine the nth prime; that’s where the next layer of clever ingenuity comes in. A reminder of the next layer,

When we evaluate Wilans’ formula we are going to be fixing n and varying i but for the next part of this section we will be doing the opposite for ease of understanding. Consider i = 5 again, we know there are 3 primes up to and including 5; thus we have

At first, the function might appear to be increasing, however if we increase the domain of our truncated graph we see that y approaches a value.

This fact is useful, as since we take the floor of this function we can return 0 when x ≤ 4 and 1 when x ≥ 4. This is as the graphs intersect at (4, 1)

We can represent the output of the floor by the following piecewise function

In general we have

We can rewrite this expression for a more appropriate meaning as we are varying i and fixing n

3.5 Bertrand’s Postulate and the final summation

Bertrand’s Postulate (now a theorem), which for the purpose of this article can be assumed without proof, states that

∀n ∈ N ≥ 2, ∃p ∈ P such that n < p < 2n

A brief history lesson, Paul Erd ̋os, a mathematician that provided a more neat and simplified proof[5] for Bertrand’s Postulate did so at the age of 19! He is famously known for his ”Erd ̋os number” a way of describing a mathematician’s collaborative distance from him. A reminder of the final summation

The summation is from i to 2^n in order to guarantee a sufficiently large enough number for the summation to count up to that includes the nth prime as guaranteed by Bertrand’s Postulate. Since 2 is prime itself, Bertrand’s postulate guarantees n primes between 1 and 2^n. Although, the true value of n is way less than 2^n (which raises an issue of efficiency which will be discussed further on in the article). Continuing the example for when n = 3 we have

Thus, the final step is to add 1.

∴ (3rd prime) = 5

And there we have it, a method of computing the nth prime as proposed by Wilans, a truly remarkable method that only uses some elementary modular arithmetic; or do we?

4 Wilans’ Formula under a microscope; how useful is it really?

4.1 Factorials Factorials Factorials!

The function f(n) = n! grows incredibly rapidly, which explains why using a computer to compute factorials requires an extremely long run time. The run time complexity of n! is O(n) meaning it requires a number of operations proportional to n since to compute n! we need n multiplications; technically n−1 multiplications, however for the formal definition of a factorial we require n multiplications, and for large n the constant subtraction of 1 yields no substantial difference in the run time. However, this is only for the factorial part of the formula.

If we consider the summation to 2^n the runtime now increases, giving a runtime complexity of O(2^n × n). Furthermore, computers have limitations on the size of numbers they can accurately represent, highlighting an issue of precision. Even for the most advanced computer processors, the calculation becomes redundant quite quickly.

5 The Verdict

5.1 Is it really about counting primes?

The formula is clever, but very inefficient. Although, I believe Wilans’ formula is not really about computing primes, instead I believe it’s about using simple mathematical tools to build tests for numbers using only arithmetic. To me, the merit of the formula doesn’t lie in it’s usefulness (or rather lack thereof) but it’s clever ingenuity.

At the start I briefly mentioned the Twin Prime Conjecture which conjectures that there are infinitely many primes p that differ by 2. For example 3 and 5 are twin primes, so are 17 and 19, the list goes on, forever? What i love about Number Theory is that although the questions we ask are easy for even those who have not studied mathematics formally to understand, they require a level of mathematics that can only be described as genius to be solved. I doubt Wilans’ formula will have any direct link with proving or disproving the Twin Prime Conjecture, but like many times in Mathematics the answer could be right under your nose.

6 References

[1]Willans, C.P. (1964). On Formulae for the Nth Prime Number. The Mathematical Gazette, 48(366), pp.413–415. doi:https://doi.org/10.2307/3611701.

[2]Wilf, H.S. (1982). What is an Answer? The American Mathematical Monthly, 89(5), pp.289–292. doi:https://doi.org/10.1080/00029890.1982.11995435.

[3]www.youtube.com. (n.d.). An Exact Formula for the Primes: Willans’ Formula. [online] Available at: https://www.youtube.com/watch?v=j5s0h42GfvM [Accessed 6 Oct. 2023].

[4]Waring, E. (1782). Meditationes Algebraicae.

[5] Erd ̋os, P. (1932). Beweis eines Satzes von Tschebyschef. Acta Scientiarum Mathematicarum (Szeged),5, 194–198.