The prime counting function is the function giving the number of primes less than or equal to a given number (Shanks 1993, p. 15). For example, there are no primes , so . There is a single prime (2) , so . There are two primes (2 and 3) , so . And so on.

The notation for the prime counting function is slightly unfortunate because it has nothing whatsoever to do with the constant . This notation was introduced by number theorist Edmund Landau in 1909 and has now become standard. In the words of Derbyshire (2004, p. 38), "I am sorry about this; it is not my fault. You'll just have to put up with it."

Letting denote the th prime, is a right inverse of since

for all positive integers. Also,

iff is a prime number.

The first few values of for , 2, ... are 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, ... (OEIS A000720). The Wolfram Language command giving the prime counting function for a number is PrimePi[x], which works up to a maximum value of .

The notation is used to denote the modular prime counting function, i.e., the number of primes of the form less than or equal to (Shanks 1993, pp. 21-22).

The following table gives the values of for powers of 10 (OEIS A006880), extending other printed tabulations (e.g., Hardy and Wright 1979, p. 4; Shanks 1993, pp. 242-243; Ribenboim 1996, p. 237; Derbyshire 2004, p. 35). Note that was incorrectly computed as by Meissel (1885), which is off by 56 (Havil 2003, p. 171), a result quoted by Hardy and Wright (1979) and Hardy (1999) and sometimes (erroneously) known as Bertelsen's number. The value for comes from Deleglise and Rivat (1996), and was reported by X. Gourdon on Oct. 27, 2000. Oliveira e Silva and X. Gourdon independently computed values for and , but an error was found in the computations of Gourdon. The value given for was computed by Tomás Oliveira e Silva, who verified this result using set sets of hardware and program parameters (pers. comm., Apr. 7, 2008). (Values of computed independently by Oliveira e Silva and X. Gourdon already agree for all powers of 10 up to .) was computed by Büthe (2014), by Staple in 2014 (Staple 2015), and by D. Baugh and K. Walisch (2015) using the primecount fast prime counting function implementation (Walisch).

One of the most fundamental and important results in number theory is the asymptotic form of as becomes large. This is given by the prime number theorem, which states that

where is the logarithmic integral and is asymptotic notation. This relation was first postulated by Gauss in 1792 (when he was 15 years old), although not revealed until an 1849 letter to Johann Encke and not published until 1863 (Gauss 1863; Havil 2003, pp. 176-177).

The following table compares the prime counting function , Riemann prime counting function , and logarithmic integral for powers of ten, i.e., . The corresponding differences are plotted above for small . Note that the values given by Hardy (1999, p. 26) for are incorrect. In the following table, denotes the nearest integer function. A similar table comparing and is given by Borwein and Bailey (2003, p. 65).

The prime counting function can be expressed by Legendre's formula, Lehmer's formula, Mapes' method, or Meissel's formula. A brief history of attempts to calculate is given by Berndt (1994). The following table is taken from Riesel (1994), where is asymptotic notation.

An approximate formula due to Locker-Ernst (Locker-Ernst 1959; Panaitopol 1999; Havil 2003, pp. 179-180), illustrated above, is given by

where is related to the harmonic number by . This formula is within of the actual value for . The values for which are 1, 109, 113, 114, 199, 200, 201, ... (OEIS A051046). Panaitopol (1999) shows that this quantity is positive for all .

An upper bound for is given by

for , and a lower bound by

for (Rosser and Schoenfeld 1962).

Hardy and Wright (1979, p. 414) give the formula

for , where is the floor function.

A modified version of the prime counting function is given by

where is the Möbius function and is the Riemann prime counting function.

Ramanujan also showed that

where is the Möbius function (Berndt 1994, p. 117; Havil 2003, p. 199).

The smallest such that for , 3, ... are 2, 27, 96, 330, 1008, ... (OEIS A038625), and the corresponding are 1, 9, 24, 66, 168, 437, ... (OEIS A038626). The number of solutions of for , 3, ... are 4, 3, 3, 6, 7, 6, ... (OEIS A038627).

Ramanujan showed that for sufficiently large ,

This holds for , 9, 10, 12, 14, 15, 16, 18, ... (OEIS A091886). The largest known prime for which the inequality fails is (Berndt 1994, pp. 112-113). The related inequality

where

is true for and no smaller number (Berndt 1994, p. 114).

See also

Bertelsen's Number, Chebyshev's Theorem, Equinumerous, Legendre's Constant, Legendre's Formula, Lehmer-Schur Method, Logarithmic Integral, Mapes' Method, Modular Prime Counting Function, Prime Arithmetic Progression, Prime-Counting Concatenation Constant, Prime Number, Prime Number Theorem, Riemann Prime Counting Function Explore this topic in the MathWorld classroom

Related Wolfram sites

http://functions.wolfram.com/NumberTheoryFunctions/PrimePi/

Explore with Wolfram|Alpha

References

Baugh, D. and Walisch, K. "New Confirmed pi(1027) Prime Counting Function Record." https://www.mersenneforum.org/showthread.php?t=20473. Sep. 6, 2015.Beiler, A. H. Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. New York: Dover, p. 218, 1966.Berndt, B. C. Ramanujan's Notebooks, Part IV. New York: Springer-Verlag, pp. 134-135, 1994.Booker, A. "The Nth Prime Page." http://primes.utm.edu/nthprime/.Borwein, J. and Bailey, D. "Prime Numbers and the Zeta Function." Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, pp. 63-72, 2003.Brent, R. P. "Irregularities in the Distribution of Primes and Twin Primes." Math. Comput. 29, 43-56, 1975.Büthe, J. "A Practical Analytic Method for Calculating II." 26 Oct 2014. http://arxiv.org/abs/1410.7008.Caldwell, C. "How Many Primes Are There?" http://primes.utm.edu/howmany.shtml.Deleglise, M. and Rivat, J. "Computing : The Meissel, Lehmer, Lagarias, Miller, Odlyzko Method." Math. Comput. 65, 235-245, 1996.Derbyshire, J. Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. New York: Penguin, 2004.Finch, S. R. "Hardy-Littlewood Constants." §2.1 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 84-94, 2003.Forbes, T. "Prime -tuplets." http://anthony.d.forbes.googlepages.com/ktuplets.htm.Gauss, C. F. Werke, Band 10, Teil I. p. 10, 1863.Gourdon, X. "New Record Computation for pi(x), x=10^21." 27 Oct 2000. http://listserv.nodak.edu/scripts/wa.exe?A2=ind0010&L=nmbrthry&P=2988.Guiasu, S. "Is There Any Regularity in the Distribution of Prime Numbers at the Beginning of the Sequence of Positive Integers?" Math. Mag. 68, 110-121, 1995.Hardy, G. H. Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, 1999.Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, pp. 164-188, 2003.Lagarias, J.; Miller, V. S.; and Odlyzko, A. "Computing : The Meissel-Lehmer Method." Math. Comput. 44, 537-560, 1985.Lagarias, J. and Odlyzko, A. "Computing : An Analytic Method." J. Algorithms 8, 173-191, 1987.Locker-Ernst, L. "Bemerkung über die Verteilung der Primzahlen." Elemente Math. (Basel) 14, 1-5, 1959.Mapes, D. C. "Fast Method for Computing the Number of Primes Less than a Given Limit." Math. Comput. 17, 179-185, 1963.Meissel, E. D. F. "Über die Bestimmung der Primzahlmenge innerhalb gegebener Grenzen." Math. Ann. 2, 636-642, 1870.Meissel, E. D. F. "Berechnung der Menge von Primzahlen, welche innerhalb der ersten Milliarde naturlicher Zahlen vorkommen." Math. Ann. 25, 251-257, 1885.Nagell, T. "The Function ." §16 in Introduction to Number Theory. New York: Wiley, pp. 54-57, 1951.Panaitopol, L. "Several Approximations of ." Math. Ineq. Appl. 2, 317-324, 1999.Platt, D. "Computing Analytically." To appear in Math. Comput.Ribenboim, P. The New Book of Prime Number Records, 3rd ed. New York: Springer-Verlag, 1996.Riesel, H. "The Number of Primes Below ." Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 10-12, 1994.Rosser, J. B. and Schoenfeld, L. "Approximate Formulas for Some Functions of Prime Numbers." Illinois J. Math. 6, 64-97, 1962.Séroul, R. "The Function pi()." §8.7 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 175-181, 2000.Shallit, J. http://www.math.uwaterloo.ca/~shallit/bib/pi.bib.Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, 1993.Sloane, N. J. A. Sequences A000720/M0256, A006880/M3608, A038625, A038626, A038627, A052434, A052435, A057752, A057794, and A091886 in "The On-Line Encyclopedia of Integer Sequences."Staple, D. B. "The Combinatorial Algorithm for Computing ." https://arxiv.org/abs/1503.01839. 28 May 2015.Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 74-76, 1991.Walisch, K. "Fast Prime Counting Function Implementations." https://github.com/kimwalisch/primecount.Wolf, M. "Unexpected Regularities in the Distribution of Prime Numbers." http://www.ift.uni.wroc.pl/~mwolf/.

Referenced on Wolfram|Alpha

Prime Counting Function

Cite this as:

Weisstein, Eric W. "Prime Counting Function." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PrimeCountingFunction.html

Subject classifications