Mathematics Magazine for Grades 112 



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 primecounting 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)
6494. 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

