Mathematics Magazine for Grades 1-12  

Formulas for  and the th Prime

Sebastian Martin Ruiz and Jonathan Sondow

1. THE FORMULAS: In [3], [4] 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 [1]

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 [2], 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 [1] 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 [5] 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

smruiz@telefonica.net

209 West 97th St. New York, NY 10025

jsondow@alumni.princeton.edu