Prime Counting Function

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

(1)

for all positive integers. Also,

(2)

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

		reference
1	4	antiquity
2		L. Pisano (1202; Beiler)
3		F. van Schooten (1657; Beiler)
4		F. van Schooten (1657; Beiler)
5		T. Brancker (1668; Beiler)
6		A. Felkel (1785; Beiler)
7		J. P. Kulik (1867; Beiler)
8		Meissel (1871; corrected)
9		Meissel (1886; corrected)
10		Lehmer (1959; corrected)
11		Bohmann (1972; corrected)
12
13
14		Lagarias et al. (1985)
15		Lagarias et al. (1985)
16		Lagarias et al. (1985)
17		M. Deleglise and J. Rivat (1994)
18		Deleglise and Rivat (1996)
19		M. Deleglise (June 19, 1996)
20		M. Deleglise (June 19, 1996)
21		project (Dec. 2000)
22		P. Demichel and X. Gourdon (Feb. 2001)
23		T. Oliveira e Silva (pers. comm., Apr. 7, 2008)
24		Platt
25		Büthe (2014)
26		Staple (2015)
27		D. Baugh and K. Walisch (2015)

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

(3)

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

Sloane	A057794	A057752
1	1
2	1
3	0
4	2
5
6	29
7	88
8	97
9
10
11
12
13
14
15	73218
16	327052
17
18
19	23884333
20
21
22

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.

method	time complexity	storage complexity
Lagarias-Miller-Odlyzko
Lagarias-Odlyzko 1
Lagarias-Odlyzko 2
Legendre's formula
Lehmer
Mapes' method
Meissel

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

(4)

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

(5)

for , and a lower bound by

(6)

for (Rosser and Schoenfeld 1962).

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

(7)

for , where is the floor function.

A modified version of the prime counting function is given by

(8)

(9)

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

Ramanujan also showed that

(10)

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 ,

(11)

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

(12)

where

(13)

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