  Subscribe

Formulas for and the th Prime

Sebastian Martin Ruiz and Jonathan Sondow

1. THE FORMULAS: In ,  the first author gave a formula for the th prime number that involves only the elementary operations and the floor function . His conditional proof assumed certain inequalities based on the Prime Number Theorem. In this note, we use the inequalities of Rosser and Schoenfeld 

to give a complete proof of the slightly  modified formula

(1) , >1,

where , defined as the number of primes not exceeding , is given by the formula

(2) .

After the proof, we indicate various ways to modify and implement the formulas so that they operate in times and , respectively.

2. PROOF. For a positive integer, let

(3) denote the number of divisors of . In , the first author found the formula

(4) ,

which holds since the quantity in parentheses is 1 or 0 according as does or does not divide .

Let F be the characteristic function of the set of prime numbers

(5) From (3), we have if is prime, and >2 if is composite.

Since for >1, we have the formula

(6) , >1.

Using (5), we write the prime-counting function as the sum

(7) with the convention that any sum is zero if . From (7), (6), (4), we obtain the formula (2) for .

In order to derive formula (1) for from (2), we require the following lemma.

Lemma 1. For >1, we have the inequalities

(8) ,

(9) .

Proof:  Rosser and Schoenfeld  proved that

(10) ,   all ,

(11) , .

From (10), we have . Since , it follows that , which implies (8) if .

To prove (9) for , we verify it numerically for 2, 3, …, 20,

and note that (11) implies (9) for . This proves the lemma. For , Lemma 1 implies that The desired formula for the th prime number follows immediately. This completes the proof of (1) and (2). 3. IMPROVEMENTS. As they stand, the formulas for , and operate in times , and , respectively. We can improve these bounds by modifying the formulas as follows. If divides , so does , so to compute it suffices to consider only . This reduce the times for and to and ,respectively. For , compute (and thus ) for , then compute recursively as . This reduces the time for to .

We can also improve the computation times (but not the bounds) in the following two ways. First, instead of the floor of , use the integer quotient

of by . Second (as P. Sebah  has pointed out), in formulas (2) and (7) for , after we only need to sum over odd numbers, after only over numbers relatively prime to 6, and similarly for other moduli 30, 210, 2310,… .

This “sieving” cuts computation time by a factor of , where is the Euler’s totient function.

We thank P. Sebah for discussions on the bounds, C. Rivera for the square root optimization, and   J. McCranie for the quotient acceleration.

REFERENCES

1.   J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers. Ill. J. Math. 6 (1962) 64-94.

2.   S. M. Ruiz, A functional recurrence to obtain the prime numbers using the Smarandache Prime Function, Smarandache Notions Journal 11 (2000) 56.

3.   S. M. Ruiz, The general term of the prime number sequence and the Smarandache Prime Function. Smarandache Notions Journal 11 (2000) 59.

4.   S. M. Ruiz, Applications of Smarandache Functions and Prime and Coprime Functions, American Research Press, Rehoboth, 2002.

5.   P. Sebah, private communications, October- November, 2002.

Avda. de Regla, 43 Chipiona 11550 Spain

209 West 97th St. New York, NY 10025