TOPICS
Search

Prime Counting Function


PrimeCountingFunction

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

The notation pi(n) for the prime counting function is slightly unfortunate because it has nothing whatsoever to do with the constant pi=3.1415.... 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 p_n denote the nth prime,p_n is a right inverse of pi(n) since

 pi(p_n)=n
(1)

for all positive integers. Also,

 p_(pi(n))=n
(2)

iff n is a prime number.

The first few values of pi(n) for n=1, 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 x is PrimePi[x], which works up to a maximum value of x approx 8×10^(13).

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

The following table gives the values of pi(n) 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 pi(10^9) was incorrectly computed as 50847478 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 pi(10^(20)) comes from Deleglise and Rivat (1996), and pi(10^(21)) was reported by X. Gourdon on Oct. 27, 2000. Oliveira e Silva and X. Gourdon independently computed values for pi(10^(22)) and pi(10^(23)), but an error was found in the computations of Gourdon. The value given for pi(10^(23)) 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 pi(x) computed independently by Oliveira e Silva and X. Gourdon already agree for all powers of 10 up to 10^(22).) pi(10^(25)) was computed by Büthe (2014), pi(10^(26)) by Staple in 2014 (Staple 2015), and pi(10^(27)) by D. Baugh and K. Walisch (2015) using the primecount fast prime counting function implementation (Walisch).

npi(10^n)reference
14antiquity
225L. Pisano (1202; Beiler)
3168F. van Schooten (1657; Beiler)
41229F. van Schooten (1657; Beiler)
59592T. Brancker (1668; Beiler)
678498A. Felkel (1785; Beiler)
7664579J. P. Kulik (1867; Beiler)
85761455Meissel (1871; corrected)
950847534Meissel (1886; corrected)
10455052511Lehmer (1959; corrected)
114118054813Bohmann (1972; corrected)
1237607912018
13346065536839
143204941750802Lagarias et al. (1985)
1529844570422669Lagarias et al. (1985)
16279238341033925Lagarias et al. (1985)
172623557157654233M. Deleglise and J. Rivat (1994)
1824739954287740860Deleglise and Rivat (1996)
19234057667276344607M. Deleglise (June 19, 1996)
202220819602560918840M. Deleglise (June 19, 1996)
2121127269486018731928pi(x) project (Dec. 2000)
22201467286689315906290P. Demichel and X. Gourdon (Feb. 2001)
231925320391606803968923T. Oliveira e Silva (pers. comm., Apr. 7, 2008)
2418435599767349200867866Platt
25176846309399143769411680Büthe (2014)
261699246750872437141327603Staple (2015)
2716352460426841680446427399D. Baugh and K. Walisch (2015)

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

 pi(n)∼Li(n),
(3)

where Li(x) 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).

PrimeCountingFunctions

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

SloaneA057794A057752
n[pi(10^n)-R(10^n)][pi(10^n)-Li(10^n)]
11-2
21-5
30-10
42-17
5-5-38
629-130
788-339
897-754
9-79-1701
10-1828-3104
11-2318-11588
12-1476-38263
13-5773-108971
14-19200-314890
1573218-1052619
16327052-3214632
17-598255-7956589
18-3501366-21949555
1923884333-99877775
20-4891825-222744644
21-86432204-597394254
22-127132665-1932355208

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 pi(n) is given by Berndt (1994). The following table is taken from Riesel (1994), where O(x) is asymptotic notation.

methodtime complexitystorage complexity
Lagarias-Miller-OdlyzkoO(x^(2/3+epsilon))O(x^(1/3+epsilon))
Lagarias-Odlyzko 1O(x^(3/5+epsilon))O(x^epsilon)
Lagarias-Odlyzko 2O(x^(1/2+epsilon))O(x^(1/4+epsilon))
Legendre's formulaO(x)O(x^(1/2))
LehmerO(x/(lnx)^4)O(x^(1/3)/lnx)
Mapes' methodO(x^(0.7))O(x^(0.7))
MeisselO(x/(lnx)^3)O(x^(1/2)/lnx)
PrimePiHarmonic

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

 pi(n) approx n/(h_n),
(4)

where h_n is related to the harmonic number H_n by h_n=H_n-3/2. This formula is within  approx 2 of the actual value for 50<=n<=1000. The values for which pi(n)-n/h_n>0 are 1, 109, 113, 114, 199, 200, 201, ... (OEIS A051046). Panaitopol (1999) shows that this quantity is positive for all n>=1429.

An upper bound for pi(n) is given by

 pi(n)<(1.25506n)/(lnn)
(5)

for n>1, and a lower bound by

 n/(lnn)<pi(n)
(6)

for n>=17 (Rosser and Schoenfeld 1962).

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

 pi(n)=-1+sum_(j=3)^n[(j-2)!-j|_((j-2)!)/j_|]
(7)

for n>3, where |_x_| is the floor function.

A modified version of the prime counting function is given by

 pi_0(p)={pi(p)   for p composite; pi(p)-1/2   for p prime
(8)
 pi_0(p)=sum_(n=1)^infty(mu(x)f(x^(1/n)))/n,
(9)

where mu(n) is the Möbius function and f(x) is the Riemann prime counting function.

Ramanujan also showed that

 (dpi(x))/(dx)∼1/(xlnx)sum_(n=1)^infty(mu(n))/nx^(1/n),
(10)

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

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

Ramanujan showed that for sufficiently large x,

 pi^2(x)<(ex)/(lnx)pi(x/e).
(11)

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

 [li(x)]^2<(ex)/(lnx)li(x/e)
(12)

where

 li(x)=int_0^x(dt)/(lnt),
(13)

is true for x>=2418 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 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 pi(x) 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 pi(x): 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 k-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 pi(x): The Meissel-Lehmer Method." Math. Comput. 44, 537-560, 1985.Lagarias, J. and Odlyzko, A. "Computing pi(x): 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 pi(x)." §16 in Introduction to Number Theory. New York: Wiley, pp. 54-57, 1951.Panaitopol, L. "Several Approximations of pi(x)." Math. Ineq. Appl. 2, 317-324, 1999.Platt, D. "Computing pi(x) 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 x." 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(x)." §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 pi(x)." 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 Web Resource. https://mathworld.wolfram.com/PrimeCountingFunction.html

Subject classifications