Prime Counter

Below is an example of a subordinate part of the Willans’ Formula responsible for calculating the primes within a given range, implemented as a function in R. Willans’ formula, introduced by Willan in 1964, is an elegant prime-generating formula that exploits the properties of prime numbers and certain mathematical functions to identify primes.

The formula is defined as follows:

The function F(j) is equal to the floor of the square of the cosine of the value pi((j-1)!+1)/j (where ! denotes the factorial operation, and pi is the constant Pi). Specifically:

• F(j) = ⌊cos²[π((j-1)!+1)/j]⌋, for j > 1 an integer.

The floor function ⌊x⌋ rounds x down to the greatest integer less than or equal to x. The values of F(j) are such that:

• F(j) = 1 for j = 1 or j prime,
• F(j) = 0 otherwise.

This part of the formula is a consequence of Wilson’s theorem, and it hides the prime numbers j as those for which F(j) = 1.

Then, the prime counting function π(x) is defined as:

• π(x) = -1 + ΣF(k), for k = 1 to x.

And the n-th prime number p_n is given by:

• p_n = 1 + Σ ⌊_n/(ΣF(j))⌋^(1/n)⌋, for m = 1 to 2^n, and j = 1 to m.

This can also be written as:

• p_n = 1 + Σ ⌊_n/(1 + π(m))⌋^(1/n)⌋.

Here, π(m) is the prime-counting function, Σ denotes the summation, and n is the number of primes.

Whilst this is not a particularly efficient or practical formula when considering scalability, it still manages to be a beautiful interplay of a variety of clever mathematical concepts.

Formula with sigma notation:

Willans’ formula in its entirety: