In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number x. It is denoted by (x) (unrelated to the number ).
Growth rate
Of great interest in number theory is the growth rate of the prime-counting function. It was conjectured in the end of the 18th century by Gauss and by Legendre to be approximately
where log is the natural logarithm, in the sense that
This statement is the prime number theorem. An equivalent statement is
where li is the logarithmic integral function. The prime number theorem was first proved in 1896 by Jacques Hadamard and by Charles de la Vallée Poussin independently, using properties of the Riemann zeta function introduced by Riemann in 1859. Proofs of the prime number theorem not using the zeta function or complex analysis were found around 1948 by Atle Selberg and by Paul Erdős (for the most part independently).
More precise estimates
In 1899, de la Vallée Poussin proved that
for some positive constant . Here, is the big notation.
More precise estimates of are now known. For example, in 2002, Kevin Ford proved that
Mossinghoff and Trudgian proved an explicit upper bound for the difference between and :
for .
For values of that are not unreasonably large, is greater than . However, is known to change sign infinitely many times. For a discussion of this, see Skewes' number.
Exact form
For let when is a prime number, and otherwise. Bernhard Riemann, in his work On the Number of Primes Less Than a Given Magnitude, proved that is equal to
where
is the Möbius function, is the logarithmic integral function, ρ indexes every zero of the Riemann zeta function, and is not evaluated with a branch cut but instead considered as where is the exponential integral. If the trivial zeros are collected and the sum is taken only over the non-trivial zeros ρ of the Riemann zeta function, then may be approximated by
The Riemann hypothesis suggests that every such non-trivial zero lies along .
Table of (x), x / log x, and li(x)
The table shows how the three functions (x), x / log x and li(x) compare at powers of 10. See also, and
{ | class="wikitable" style="text-align: right" ! x ! (x) ! ! ! ! |- | 10 | 4 | 0 | 2 | 2.500 | -8.57% |- | 102 | 25 | 3 | 5 | 4.000 |13.14% |- | 103 | 168 | 23 | 10 | 5.952 |13.83% |- | 104 | 1,229 | 143 | 17 | 8.137 |11.66% |- | 105 | 9,592 | 906 | 38 | 10.425 |9.45% |- | 106 | 78,498 | 6,116 | 130 | 12.739 |7.79% |- | 107 | 664,579 | 44,158 | 339 | 15.047 |6.64% |- | 108 | 5,761,455 | 332,774 | 754 | 17.357 |5.78% |- | 109 | 50,847,534 | 2,592,592 | 1,701 | 19.667 |5.10% |- | 1010 | 455,052,511 | 20,758,029 | 3,104 | 21.975 |4.56% |- | 1011 | 4,118,054,813 | 169,923,159 | 11,588 | 24.283 |4.13% |- | 1012 | 37,607,912,018 | 1,416,705,193 | 38,263 | 26.590 |3.77% |- | 1013 | 346,065,536,839 | 11,992,858,452 | 108,971 | 28.896 |3.47% |- | 1014 | 3,204,941,750,802 | 102,838,308,636 | 314,890 | 31.202 |3.21% |- | 1015 | 29,844,570,422,669 | 891,604,962,452 | 1,052,619 | 33.507 |2.99% |- | 1016 | 279,238,341,033,925 | 7,804,289,844,393 | 3,214,632 | 35.812 |2.79% |- | 1017 | 2,623,557,157,654,233 | 68,883,734,693,928 | 7,956,589 | 38.116 |2.63% |- | 1018 | 24,739,954,287,740,860 | 612,483,070,893,536 | 21,949,555 | 40.420 |2.48% |- | 1019 | 234,057,667,276,344,607 | 5,481,624,169,369,961 | 99,877,775 | 42.725 |2.34% |- | 1020 | 2,220,819,602,560,918,840 | 49,347,193,044,659,702 | 222,744,644 | 45.028 |2.22% |- | 1021 | 21,127,269,486,018,731,928 | 446,579,871,578,168,707 | 597,394,254 | 47.332 |2.11% |- | 1022 | 201,467,286,689,315,906,290 | 4,060,704,006,019,620,994 | 1,932,355,208 | 49.636 |2.02% |- | 1023 | 1,925,320,391,606,803,968,923 | 37,083,513,766,578,631,309 | 7,250,186,216 | 51.939 |1.93% |- | 1024 | 18,435,599,767,349,200,867,866 | 339,996,354,713,708,049,069 | 17,146,907,278 | 54.243 |1.84% |- | 1025 | 176,846,309,399,143,769,411,680 | 3,128,516,637,843,038,351,228 | 55,160,980,939 | 56.546 |1.77% |- | 1026 | 1,699,246,750,872,437,141,327,603 | 28,883,358,936,853,188,823,261 | 155,891,678,121 | 58.850 |1.70% |- |1027 |16,352,460,426,841,680,446,427,399 |267,479,615,610,131,274,163,365 |508,666,658,006 |61.153 |1.64% |- |1028 |157,589,269,275,973,410,412,739,598 |2,484,097,167,669,186,251,622,127 |1,427,745,660,374 |63.456 |1.58% |- |1029 |1,520,698,109,714,272,166,094,258,063 |23,130,930,737,541,725,917,951,446 |4,551,193,622,464 |65.759 |1.52% |}
In the On-Line Encyclopedia of Integer Sequences, the (x) column is sequence , is sequence , and is sequence .