FAQ: Is there a formula for the nth Prime?

By Chris Caldwell

Here we address the following frequently asked question.

Is there a formula for producing a specific prime number? Let me give you an example. The formula is given the number 52. In return, the formula produces 239, the fifty-second prime number (I think).

Yes, there are many such formulas--but they are of recreational use only because they are very inefficient. Most are either ways of encoding the list of primes or very clever counting arguments. I will give a couple example below, but for more information start with chapter three "Are There Functions Defining Prime Numbers?" of Ribenboim's text [Ribenboim95pp. 179-212].

Method One: Encoding Primes

Let pn be the nth prime. In 1952 Sierpinski suggested we define a constant A as follows:

A = sum 1 to infinity of p_n times 10^-2^n = 0.02030005000000070...
Then using the floor function [x] (the greatest integer less than or equal to x) we have

pn = ugly

Hardy and Wright [HW79p345] give a variant of this: Let r be an integer greater than one and define a constant B as follows:

B = ugly


pn = ugly

This type formula would only be of value if the necessary constant could be found without first finding the primes--this may be possible, but it seems unlikely.

Method Two: Counting Primes with Wilson's Theorem

First use one of these three methods to define π(x). Willans (1964) used

π(n) = (sum from j=2 to n) sin2(pi*(j-1)!2/j) / sin2(pi/j).

Minác (unpublished, proof in [Ribenboim95, p181]) set

π(n) = (sum from j=2 to n) [ ((j-1)! + 1)/j - [(j-1)!/j] ].

Hardy and Wright set π(1) = 0, π(2) = 1, and then [HW79p414]

π(n) = 1 + (sum from j=3 to n) ( (j-2)! - j[(j-2)!/j] ).

(for all n > 2). Then we have (still using the floor function [x]):

nth prime = 1 + (sum from m=1 to j=2n) [ [ n/(1 + π(m)) ]1/n ]
Printed from the PrimePages <t5k.org> © Reginald McLean.