TOPICS
Search

Rosser's Theorem


RossersTheorem

The prime number theorem shows that the nth prime number p_n has the asymptotic value

 p_n∼nlnn
(1)

as n->infty (Havil 2003, p. 182). Rosser's theorem makes this a rigorous lower bound by stating that

 p_n>nlnn
(2)

for n>1 (Rosser 1938). This result was subsequently improved to

 p_n>n(lnn+lnlnn-c),
(3)

where c=3/2 (Rosser and Schoenfeld 1975). The constant c was subsequently reduced to c=1.0072629 (Robin 1983). Massias and Robin (1996) then showed that c=1 was admissible for 1<n<=exp(598) and n>=exp(1800). Finally, Dusart (1999) showed that c=1 holds for all n>1 (Havil 2003, p. 183). The plots above show p_n (black), nlnn (blue), and n(lnn+lnlnn-1) (red).

RossersTheoremDifference

The difference between p^^_n=n(lnn+lnlnn-1) and p_n is plotted above. The slope of the difference taken out to n=10^7 is approximately 0.46.


See also

Prime Formulas, Prime Number, Prime Number Theorem

Explore with Wolfram|Alpha

References

Dusart, P. "The k^(th) Prime is Greater than k(lnk+lnlnk-1) for k>=2." Math. Comput. 68, 411-415, 1999.Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, 2003.Massias, J.-P. and Robin, G. "Bornes effectives pour certaines fonctions concernant les nombres premiers." J. Théor. Nombres Bordeaux 8, 215-242, 1996.Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 56-57, 1994.Robin, G. "Estimation de la fonction de Tschebychef theta sur le k-iéme nombre premier et grandes valeurs de la fonction omega(n), nombres de diviseurs premiers de n." Acta Arith. 42, 367-389, 1983.Robin, G. "Permanence de relations de récurrence dans certains développements asymptotiques." Publ. Inst. Math., Nouv. Sér. 43, 17-25, 1988.Rosser, J. B. "The nth Prime is Greater than nlog(n)." Proc. London Math. Soc. 45, 21-44, 1938.Rosser, J. B. and Schoenfeld, L. "Sharper Bounds for Chebyshev Functions theta(x) and psi(x)." Math. Comput. 29, 243-269, 1975.Salvy, B. "Fast Computation of Some Asymptotic Functional Inverses." J. Symb. Comput. 17, 227-236, 1994.

Referenced on Wolfram|Alpha

Rosser's Theorem

Cite this as:

Weisstein, Eric W. "Rosser's Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RossersTheorem.html

Subject classifications