Editing Prime-counting function

{{short description|Function representing the number of primes less than or equal to a given number}}
{{Redirect|Π(x)|the variant of the gamma function|Gamma function#Pi function}} 
{{log(x)}}
{{Duplication|dupe=Prime number theorem|discuss=Talk:Prime number theorem#Too much duplication in Prime number theorem and Prime-counting function|date=December 2024}}
[[Image:PrimePi.svg|thumb|right|400px|The values of {{math|''π''(''n'')}} for the first 60 positive integers]]

In [[mathematics]], the '''prime-counting function''' is the [[Function (mathematics)|function]] counting the number of [[prime number]]s less than or equal to some [[real number]] {{mvar|x}}.<ref name="Bach">{{cite book |first=Eric |last=Bach |author2=Shallit, Jeffrey |year=1996 |title=Algorithmic Number Theory |publisher=MIT Press |isbn=0-262-02405-5 |pages=volume 1 page 234 section 8.8 |no-pp=true}}</ref><ref name="mathworld_pcf">{{MathWorld |title=Prime Counting Function |urlname=PrimeCountingFunction}}</ref> It is denoted by {{math|''π''(''x'')}} (unrelated to the [[pi|number {{pi}}]]).

A symmetric variant seen sometimes is {{math|''π''<sub>0</sub>(''x'')}}, which is equal to {{math|''π''(''x'') − {{frac|1|2}}}} if {{mvar|x}} is exactly a prime number, and equal to {{math|''π''(''x'')}} otherwise.  That is, the number of prime numbers less than {{mvar|x}}, plus half if {{mvar|x}} equals a prime.

==Growth rate==
{{main|Prime number theorem}}
Of great interest in [[number theory]] is the [[Asymptotic analysis|growth rate]] of the prime-counting function.<ref name="Caldwell">{{cite web | publisher=Chris K. Caldwell | title=How many primes are there? | url=http://primes.utm.edu/howmany.shtml | access-date=2008-12-02 | archive-date=2012-10-15 | archive-url=https://web.archive.org/web/20121015002415/http://primes.utm.edu/howmany.shtml | url-status=dead }}</ref><ref name="Dickson">{{cite book |author-link=L. E. Dickson| first=Leonard Eugene | last=Dickson | year=2005 | title=History of the Theory of Numbers, Vol. I: Divisibility and Primality | publisher=Dover Publications | isbn=0-486-44232-2}}</ref> It was [[conjecture]]d in the end of the 18th century by [[Carl Friedrich Gauss|Gauss]] and by [[Adrien-Marie Legendre|Legendre]] to be approximately
<math display=block> \frac{x}{\log x} </math>
where {{math|log}} is the [[natural logarithm]], in the sense that
<math display=block>\lim_{x\rightarrow\infty} \frac{\pi(x)}{x/\log x}=1. </math>
This statement is the [[prime number theorem]]. An equivalent statement is
<math display=block>\lim_{x\rightarrow\infty}\frac{\pi(x)}{\operatorname{li}(x)}=1</math>
where {{math|li}} is the [[logarithmic integral]] function. The prime number theorem was first proved in 1896 by [[Jacques Hadamard]] and by [[Charles Jean de la Vallée-Poussin|Charles de la Vallée Poussin]] independently, using properties of the [[Riemann zeta function]] introduced by [[Bernhard Riemann|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).<ref name="Ireland">{{cite book | first=Kenneth | last=Ireland |author2=Rosen, Michael | year=1998 | title=A Classical Introduction to Modern Number Theory  | edition=Second | publisher=Springer | isbn=0-387-97329-X }}</ref>

===More precise estimates===
In 1899, [[Charles Jean de la Vallée Poussin|de la Vallée Poussin]] proved that
<ref>See also Theorem 23 of {{cite book |author = A. E. Ingham |author-link = Albert Ingham |title = The Distribution of Prime Numbers |date=2000 |publisher = Cambridge University Press |isbn=0-521-39789-8}}</ref>
<math display=block>\pi(x) = \operatorname{li} (x) + O \left(x e^{-a\sqrt{\log x}}\right) \quad\text{as } x \to \infty</math>
for some positive constant {{mvar|a}}. Here, {{math|''O''(...)}} is the [[big O notation|big {{mvar|O}} notation]].

More precise estimates of {{math|''π''(''x'')}} are now known. For example, in 2002, [[Kevin Ford (mathematician)|Kevin Ford]] proved that<ref name="Ford">{{cite journal |author = Kevin Ford |title=Vinogradov's Integral and Bounds for the Riemann Zeta Function |journal=Proc. London Math. Soc. |date=November 2002 |volume=85 |issue=3 |pages=565–633 |url=https://faculty.math.illinois.edu/~ford/wwwpapers/zetabd.pdf |doi=10.1112/S0024611502013655 |arxiv=1910.08209 |s2cid=121144007 }}</ref>
<math display=block>\pi(x) = \operatorname{li} (x) + O \left(x \exp \left( -0.2098(\log x)^{3/5} (\log \log x)^{-1/5} \right) \right).</math>

Mossinghoff and [[Timothy Trudgian|Trudgian]] proved<ref>{{cite journal | first1 = Michael J. | last1 = Mossinghoff  | first2 = Timothy S. | last2 = Trudgian | author2-link=Timothy Trudgian| title = Nonnegative trigonometric polynomials and a zero-free region for the Riemann zeta-function | journal = J. Number Theory | volume = 157 | year = 2015 | pages = 329–349 | arxiv = 1410.3926 | doi = 10.1016/J.JNT.2015.05.010| s2cid = 117968965 }}</ref> an explicit upper bound for the difference between {{math|''π''(''x'')}} and {{math|li(''x'')}}:
<math display=block>\bigl| \pi(x) - \operatorname{li}(x) \bigr| \le 0.2593 \frac{x}{(\log x)^{3/4}} \exp \left( -\sqrt{ \frac{\log x}{6.315} } \right) \quad \text{for } x \ge 229.</math>

For values of {{mvar|x}} that are not unreasonably large, {{math|li(''x'')}} is greater than {{math|''π''(''x'')}}. However, {{math|''π''(''x'') − li(''x'')}} is known to change sign infinitely many times. For a discussion of this, see [[Skewes' number]].

===Exact form===

For {{math|''x'' > 1}} let {{math|''π''<sub>0</sub>(''x'') {{=}} ''π''(''x'') − {{sfrac|1|2}}}} when {{mvar|x}} is a prime number, and {{math|''π''<sub>0</sub>(''x'') {{=}} ''π''(''x'')}} otherwise. [[Bernhard Riemann]], in his work ''[[On the Number of Primes Less Than a Given Magnitude]]'', proved that {{math|''π''<sub>0</sub>(''x'')}} is equal to<ref>{{Cite web|url=http://ism.uqam.ca/~ism/pdf/Hutama-scientific%20report.pdf|title=Implementation of Riemann's Explicit Formula for Rational and Gaussian Primes in Sage|last=Hutama|first=Daniel|date=2017|website=Institut des sciences mathématiques}}</ref>[[File:Riemann Explicit Formula.gif|thumb|Riemann's explicit formula using the first 200 non-trivial zeros of the zeta function|402x402px]]
<math display="block">\pi_0(x) = \operatorname{R}(x) - \sum_{\rho}\operatorname{R}(x^\rho),</math>
where
<math display=block>\operatorname{R}(x) = \sum_{n=1}^{\infty} \frac{\mu(n)}{n} \operatorname{li}\left(x^{1/n}\right),</math>
{{math|''μ''(''n'')}} is the [[Möbius function]], {{math|li(''x'')}} is the [[logarithmic integral function]], {{mvar|ρ}} indexes every zero of the Riemann zeta function, and {{math|li(''x''<sup>{{sfrac|''ρ''|''n''}}</sup>)}} is not evaluated with a [[branch cut]] but instead considered as {{math|Ei({{sfrac|''ρ''|''n''}} log ''x'')}} where {{math|Ei(''x'')}} is the [[exponential integral]]. If the trivial zeros are collected and the sum is taken ''only'' over the non-trivial zeros {{mvar|ρ}} of the Riemann zeta function, then {{math|''π''<sub>0</sub>(''x'')}} may be approximated by<ref name="RieselGohl">{{Cite journal | author1-link=Hans Riesel | last1=Riesel | first1=Hans | last2=Göhl | first2=Gunnar | title=Some calculations related to Riemann's prime number formula | doi=10.2307/2004630 | mr=0277489  | year=1970 | journal=[[Mathematics of Computation]] | issn=0025-5718 | volume=24 | issue=112 | pages=969–983 | jstor=2004630 | publisher=American Mathematical Society |url=https://www.ams.org/journals/mcom/1970-24-112/S0025-5718-1970-0277489-3/S0025-5718-1970-0277489-3.pdf }}</ref>
<math display=block>\pi_0(x) \approx \operatorname{R}(x) - \sum_{\rho}\operatorname{R}\left(x^\rho\right) - \frac{1}{\log x} + \frac{1}{\pi} \arctan{\frac{\pi}{\log x}} .</math>

The [[Riemann hypothesis]] suggests that every such non-trivial zero lies along {{math|1=Re(''s'') = {{sfrac|1|2}}}}.

==Table of {{math|''π''(''x'')}}, {{math|{{sfrac|''x''|log ''x'' }}}}, and {{math|li(''x'')}}==

The table shows how the three functions {{math|''π''(''x'')}}, {{math|{{sfrac|''x''|log ''x''}}}}, and {{math|li(''x'')}} compared at powers of 10. See also,<ref name="Caldwell" /><ref name="Silva">{{cite web |title=Tables of values of {{math|''π''(''x'')}} and of {{math|''π''<sub>2</sub>(''x'')}} |url=https://sweet.ua.pt/tos/primes.html |publisher=Tomás Oliveira e Silva |access-date=2024-03-31}}</ref> and<ref name="Gourdon">{{cite web |title=A table of values of {{math|''π''(''x'')}} |url=http://numbers.computation.free.fr/Constants/Primes/pixtable.html |publisher=Xavier Gourdon, Pascal Sebah, Patrick Demichel |access-date=2008-09-14}}</ref>

:{| class="wikitable" style="text-align: right"
! {{mvar|x}}
! {{math|''π''(''x'')}}
! {{math|''π''(''x'') − {{sfrac|''x''|log ''x''}}}}
! {{math|li(''x'') − ''π''(''x'')}}
! {{math|{{sfrac|''x''|''π''(''x'')}}}}
!{{math|{{sfrac|''x''|log ''x''}}}}<br> % error
|-
| 10
| 4
| 0
| 2
| 2.500
| −8.57%
|-
| 10<sup>2</sup>
| 25
| 3
| 5
| 4.000
| +13.14%
|-
| 10<sup>3</sup>
| 168
| 23
| 10
| 5.952
| +13.83%
|-
| 10<sup>4</sup>
| 1,229
| 143
| 17
| 8.137
| +11.66%
|-
| 10<sup>5</sup>
| 9,592
| 906
| 38
| 10.425
| +9.45%
|-
| 10<sup>6</sup>
| 78,498
| 6,116
| 130
| 12.739
| +7.79%
|-
| 10<sup>7</sup>
| 664,579
| 44,158
| 339
| 15.047
| +6.64%
|-
| 10<sup>8</sup>
| 5,761,455
| 332,774
| 754
| 17.357
| +5.78%
|-
| 10<sup>9</sup>
| 50,847,534
| 2,592,592
| 1,701
| 19.667
| +5.10%
|-
| 10<sup>10</sup>
| 455,052,511
| 20,758,029
| 3,104
| 21.975
| +4.56%
|-
| 10<sup>11</sup>
| 4,118,054,813
| 169,923,159
| 11,588
| 24.283
| +4.13%
|-
| 10<sup>12</sup>
| 37,607,912,018
| 1,416,705,193
| 38,263
| 26.590
| +3.77%
|-
| 10<sup>13</sup>
| 346,065,536,839
| 11,992,858,452
| 108,971
| 28.896
| +3.47%
|-
| 10<sup>14</sup>
| 3,204,941,750,802
| 102,838,308,636
| 314,890
| 31.202
| +3.21%
|-
| 10<sup>15</sup>
| 29,844,570,422,669
| 891,604,962,452
| 1,052,619
| 33.507
| +2.99%
|-
| 10<sup>16</sup>
| 279,238,341,033,925
| 7,804,289,844,393
| 3,214,632
| 35.812
| +2.79%
|-
| 10<sup>17</sup>
| 2,623,557,157,654,233
| 68,883,734,693,928
| 7,956,589
| 38.116
| +2.63%
|-
| 10<sup>18</sup>
| 24,739,954,287,740,860
| 612,483,070,893,536
| 21,949,555
| 40.420
| +2.48%
|-
| 10<sup>19</sup>
| 234,057,667,276,344,607
| 5,481,624,169,369,961
| 99,877,775
| 42.725
| +2.34%
|-
| 10<sup>20</sup>
| 2,220,819,602,560,918,840
| 49,347,193,044,659,702
| 222,744,644
| 45.028
| +2.22%
|-
| 10<sup>21</sup>
| 21,127,269,486,018,731,928
| 446,579,871,578,168,707
| 597,394,254
| 47.332
| +2.11%
|-
| 10<sup>22</sup>
| 201,467,286,689,315,906,290
| 4,060,704,006,019,620,994
| 1,932,355,208
| 49.636
| +2.02%
|-
| 10<sup>23</sup>
| 1,925,320,391,606,803,968,923
| 37,083,513,766,578,631,309
| 7,250,186,216
| 51.939
| +1.93%
|-
| 10<sup>24</sup>
| 18,435,599,767,349,200,867,866
| 339,996,354,713,708,049,069
| 17,146,907,278
| 54.243
| +1.84%
|-
| 10<sup>25</sup>
| 176,846,309,399,143,769,411,680
| 3,128,516,637,843,038,351,228
| 55,160,980,939
| 56.546
| +1.77%
|-
| 10<sup>26</sup>
| 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%
|-
| 10<sup>27</sup>
| 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%
|-
| 10<sup>28</sup>
| 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%
|-
| 10<sup>29</sup>
| 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%
|}
[[File:Prime number theorem ratio convergence.svg|thumb|300px|Graph showing ratio of the prime-counting function {{math|''π''(''x'')}} to two of its approximations, {{math|{{sfrac|''x''|log ''x''}}}} and {{math|Li(''x'')}}. As {{mvar|x}} increases (note {{mvar|x}}-axis is logarithmic), both ratios tend towards 1. The ratio for {{math|{{sfrac|''x''|log ''x''}}}} converges from above very slowly, while the ratio for {{math|Li(''x'')}} converges more quickly from below.]]
In the [[On-Line Encyclopedia of Integer Sequences]], the {{math|''π''(''x'')}} column is sequence {{OEIS2C|id=A006880}}, {{math| ''π''(''x'') − {{sfrac|''x''|log ''x''}}}} is sequence {{OEIS2C|id=A057835}}, and {{math|li(''x'') − ''π''(''x'')}} is sequence {{OEIS2C|id=A057752}}.

The value for {{math|''π''(10<sup>24</sup>)}} was originally computed by J. Buethe, [[Jens Franke|J. Franke]], A. Jost, and T. Kleinjung assuming the [[Riemann hypothesis]].<ref name="Franke">{{cite web |title=Conditional Calculation of π(10<sup>24</sup>) |first=Jens |last=Franke |author-link=Jens Franke |date=2010-07-29 |url=https://t5k.org/notes/pi(10to24).html |publisher=Chris K. Caldwell |access-date=2024-03-30}}</ref>
It was later verified unconditionally in a computation by D. J. Platt.<ref name="Platt2012">{{cite journal |title=Computing {{math|''π''(''x'')}} Analytically |arxiv=1203.5712 |last1=Platt |first1=David J. |journal=Mathematics of Computation |volume=84 |issue=293 |date=May 2015 |orig-date=March 2012 |pages=1521–1535 |doi=10.1090/S0025-5718-2014-02884-6 |doi-access=free}}</ref>
The value for {{math|''π''(10<sup>25</sup>)}} is by the same four authors.<ref name="Buethe">{{cite web |title=Analytic Computation of the prime-counting Function |url=http://www.math.uni-bonn.de/people/jbuethe/topics/AnalyticPiX.html |publisher=J. Buethe |date=27 May 2014 |access-date=2015-09-01}}  Includes 600,000 value of {{math|''π''(''x'')}} for {{math|10<sup>14</sup> ≤ ''x'' ≤ 1.6×10<sup>18</sup>}}</ref> 
The value for {{math|''π''(10<sup>26</sup>)}} was computed by D. B. Staple.<ref name="Staple">{{cite thesis |title=The combinatorial algorithm for computing π(x) |date=19 August 2015 |url=http://dalspace.library.dal.ca/handle/10222/60524 |publisher=Dalhousie University |access-date=2015-09-01|type=Thesis |last1=Staple |first1=Douglas }}</ref> All other prior entries in this table were also verified as part of that work.

The values for 10<sup>27</sup>, 10<sup>28</sup>, and 10<sup>29</sup> were announced by David Baugh and Kim Walisch in 2015,<ref>{{cite web|website=Mersenne Forum|first=Kim |last=Walisch|title=New confirmed π(10<sup>27</sup>) prime counting function record |date=September 6, 2015|url=http://www.mersenneforum.org/showthread.php?t=20473}}</ref> 2020,<ref>{{cite web |last=Baugh |first=David |date=August 30, 2020 |title=New prime counting function record, pi(10^28) |url=https://www.mersenneforum.org/showpost.php?p=555434&postcount=28 |website=Mersenne Forum}}</ref> and 2022,<ref>{{cite web |first=Kim |last=Walisch |date=March 4, 2022 |title=New prime counting function record: PrimePi(10^29) |url=https://www.mersenneforum.org/showpost.php?p=601061&postcount=38 |website=Mersenne Forum}}</ref> respectively.

== Algorithms for evaluating {{math|''π''(''x'')}} ==

A simple way to find {{math|''π''(''x'')}}, if {{mvar|x}} is not too large, is to use the [[sieve of Eratosthenes]] to produce the primes less than or equal to {{mvar|x}} and then to count them.

A more elaborate way of finding {{math|''π''(''x'')}} is due to [[Adrien-Marie Legendre|Legendre]] (using the [[inclusion–exclusion principle]]): given {{mvar|x}}, if {{math|''p''<sub>1</sub>, ''p''<sub>2</sub>,…, ''p<sub>n</sub>''}} are distinct prime numbers, then the number of integers less than or equal to {{mvar|x}} which are divisible by no {{mvar|p<sub>i</sub>}} is

:<math>\lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i<j} \left\lfloor\frac{x}{p_ip_j}\right\rfloor - \sum_{i<j<k}\left\lfloor\frac{x}{p_ip_jp_k}\right\rfloor + \cdots</math>

(where {{math|⌊''x''⌋}} denotes the [[floor function]]). This number is therefore equal to

:<math>\pi(x)-\pi\left(\sqrt{x}\right)+1</math>

when the numbers {{math|''p''<sub>1</sub>, ''p''<sub>2</sub>,…, ''p<sub>n</sub>''}} are the prime numbers less than or equal to the square root of {{mvar|x}}.

=== The Meissel–Lehmer algorithm ===

{{main|Meissel–Lehmer algorithm}}

In a series of articles published between 1870 and 1885, [[Ernst Meissel]] described (and used) a practical combinatorial way of evaluating {{math|''π''(''x'')}}: Let {{math|''p''<sub>1</sub>, ''p''<sub>2</sub>,…, ''p<sub>n</sub>''}} be the first {{mvar|n}} primes and denote by {{math|Φ(''m'',''n'')}} the number of natural numbers not greater than {{mvar|m}} which are divisible by none of the {{mvar|p<sub>i</sub>}} for any {{math|''i'' ≤ ''n''}}. Then

: <math>\Phi(m,n)=\Phi(m,n-1)-\Phi\left(\frac m {p_n},n-1\right).</math>

Given a natural number {{mvar|m}}, if {{math|''n'' {{=}} ''π''({{sqrt|''m''|3}})}} and if {{math|''μ'' {{=}} ''π''({{sqrt|''m''}}) − ''n''}}, then

:<math>\pi(m) = \Phi(m,n)+n(\mu+1)+\frac{\mu^2-\mu} 2 - 1 - \sum_{k=1}^\mu\pi\left(\frac m {p_{n+k}}\right) .</math>

Using this approach, Meissel computed {{math|''π''(''x'')}}, for {{mvar|x}} equal to {{val|5e5}}, 10<sup>6</sup>, 10<sup>7</sup>, and 10<sup>8</sup>.

In 1959, [[Derrick Henry Lehmer]] extended and simplified Meissel's method. Define, for real {{mvar|m}} and for natural numbers {{mvar|n}} and {{mvar|k}}, {{math|''P<sub>k</sub>''(''m'',''n'')}} as the number of numbers not greater than {{mvar|m}} with exactly {{mvar|k}} prime factors, all greater than {{mvar|p<sub>n</sub>}}. Furthermore, set {{math|''P''<sub>0</sub>(''m'',''n'') {{=}} 1}}. Then

:<math>\Phi(m,n) = \sum_{k=0}^{+\infty} P_k(m,n)</math>

where the sum actually has only finitely many nonzero terms. Let {{mvar|y}} denote an integer such that {{math|{{sqrt|''m''|3}} ≤ ''y'' ≤ {{sqrt|''m''}}}}, and set {{math|''n'' {{=}} ''π''(''y'')}}. Then {{math|''P''<sub>1</sub>(''m'',''n'') {{=}} ''π''(''m'') − ''n''}} and {{math|''P<sub>k</sub>''(''m'',''n'') {{=}} 0}} when {{math|''k'' ≥ 3}}. Therefore,

:<math>\pi(m) = \Phi(m,n) + n - 1 - P_2(m,n)</math>

The computation of {{math|''P''<sub>2</sub>(''m'',''n'')}} can be obtained this way:

:<math>P_2(m,n) = \sum_{y < p \le \sqrt{m} } \left( \pi \left( \frac m p \right) - \pi(p) + 1\right)</math>

where the sum is over prime numbers.

On the other hand, the computation of {{math|Φ(''m'',''n'')}} can be done using the following rules:

#<math>\Phi(m,0) = \lfloor m\rfloor</math>
#<math>\Phi(m,b) = \Phi(m,b-1) - \Phi\left(\frac m{p_b},b-1\right)</math>

Using his method and an [[IBM 701]], Lehmer was able to compute the correct value of {{math|''π''(10<sup>9</sup>)}} and missed the correct value of {{math|''π''(10<sup>10</sup>)}} by 1.<ref name="lehmer">{{cite journal |last=Lehmer |first=Derrick Henry |author-link=D. H. Lehmer |date=1 April 1958 |title=On the exact number of primes less than a given limit |journal=Illinois J. Math. |volume=3 |issue=3 |pages=381–388 |url=https://projecteuclid.org/download/pdf_1/euclid.ijm/1255455259 |access-date=1 February 2017 }}</ref>

Further improvements to this method were made by Lagarias, Miller, Odlyzko, Deléglise, and Rivat.<ref name="pix_comp">{{cite journal |author1 = Deléglise, Marc |author2 = Rivat, Joel |date=January 1996 |title=Computing {{math|''π''(''x'')}}: The Meissel, Lehmer, Lagarias, Miller, Odlyzko method  |journal=Mathematics of Computation |volume=65 |issue=213 |pages=235–245 |doi = 10.1090/S0025-5718-96-00674-6 |doi-access=free |url=https://www.ams.org/mcom/1996-65-213/S0025-5718-96-00674-6/S0025-5718-96-00674-6.pdf }}</ref>

==Other prime-counting functions==

Other prime-counting functions are also used because they are more convenient to work with.

===Riemann's prime-power counting function===
Riemann's prime-power counting function is usually denoted as {{math|Π<sub>0</sub>(''x'')}} or {{math|''J''<sub>0</sub>(''x'')}}. It has jumps of {{math|{{sfrac|1|''n''}}}} at prime powers {{mvar|p<sup>n</sup>}} and it takes a value halfway between the two sides at the discontinuities of {{math|''π''(''x'')}}. That added detail is used because the function may then be defined by an inverse [[Mellin transform]].

Formally, we may define {{math|Π<sub>0</sub>(''x'')}} by
:<math>\Pi_0(x) = \frac{1}{2} \left( \sum_{p^n < x} \frac{1}{n} + \sum_{p^n \le x} \frac{1}{n} \right)\ </math>
where the variable {{mvar|p}} in each sum ranges over all primes within the specified limits.

We may also write
:<math>\ \Pi_0(x) = \sum_{n=2}^x \frac{\Lambda(n)}{\log n} - \frac{\Lambda(x)}{2\log x} = \sum_{n=1}^\infty \frac 1 n \pi_0\left(x^{1/n}\right)</math>
where {{math|Λ}} is the [[von Mangoldt function]] and

:<math>\pi_0(x) = \lim_{\varepsilon \to 0} \frac{\pi(x-\varepsilon) + \pi(x+\varepsilon)}{2}.</math>

The [[Möbius inversion formula]] then gives
:<math>\pi_0(x) = \sum_{n=1}^\infty \frac{\mu(n)}{n}\ \Pi_0\left(x^{1/n}\right),</math>
where {{math|''μ''(''n'')}} is the [[Möbius function]].

Knowing the relationship between the logarithm of the [[Riemann zeta function]] and the [[von Mangoldt function]] {{math|Λ}}, and using the [[Perron formula]] we have
:<math>\log \zeta(s) = s \int_0^\infty \Pi_0(x) x^{-s-1}\, \mathrm{d}x</math>

=== Chebyshev's function ===
The [[Chebyshev function]] weights primes or prime powers {{mvar|p<sup>n</sup>}} by {{math|log ''p''}}:

:<math>\begin{align}
\vartheta(x) &= \sum_{p\le x} \log p \\
\psi(x)&=\sum_{p^n \le x} \log p = \sum_{n=1}^\infty \vartheta \left( x^{1/n} \right) = \sum_{n \le x}\Lambda(n) .
\end{align}</math>

For {{math|''x'' ≥ 2}},<ref>{{cite book |last=Apostol |first=Tom M. |author-link=Tom M. Apostol |year=2010 |title=Introduction to Analytic Number Theory |publisher=Springer |isbn= 978-1441928054}}</ref>
:<math>\vartheta(x) = \pi(x)\log x - \int_2^x \frac{\pi(t)}{t}\, \mathrm{d}t </math>
and
:<math>\pi(x)=\frac{\vartheta(x)}{\log x} + \int_2^x \frac{\vartheta(t)}{t\log^{2}(t)} \mathrm{d} t .</math>

==Formulas for prime-counting functions==

Formulas for prime-counting functions come in two kinds: arithmetic formulas and analytic formulas. Analytic formulas for prime-counting were the first used to prove the [[prime number theorem]]. They stem from the work of Riemann and [[Hans Carl Friedrich von Mangoldt|von Mangoldt]], and are generally known as [[Explicit formulae (L-function)|explicit formulae]].<ref name="Titchmarsh">{{cite book |first=E.C. |last=Titchmarsh |year=1960 |title=The Theory of Functions, 2nd ed. |publisher=Oxford University Press}}</ref>

We have the following expression for the second [[Chebyshev function]] {{mvar|ψ}}:

:<math>\psi_0(x) = x - \sum_\rho \frac{x^\rho}{\rho} - \log 2\pi - \frac{1}{2} \log\left(1-x^{-2}\right),</math>

where

: <math>\psi_0(x) = \lim_{\varepsilon \to 0} \frac{\psi(x - \varepsilon) + \psi(x + \varepsilon)}{2}.</math>

Here {{mvar|ρ}} are the zeros of the Riemann zeta function in the critical strip, where the real part of {{mvar|ρ}} is between zero and one. The formula is valid for values of {{mvar|x}} greater than one, which is the region of interest. The sum over the roots is conditionally convergent, and should be taken in order of increasing absolute value of the imaginary part. Note that the same sum over the trivial roots gives the last [[subtrahend]] in the formula.

For {{math|''Π''<sub>0</sub>(''x'')}} we have a more complicated formula

:<math>\Pi_0(x) = \operatorname{li}(x) - \sum_\rho \operatorname{li}\left(x^\rho\right) - \log 2 + \int_x^\infty \frac{\mathrm{d}t}{t \left(t^2 - 1\right) \log t}.</math>

Again, the formula is valid for {{math|''x'' > 1}}, while {{mvar|ρ}} are the nontrivial zeros of the zeta function ordered according to their absolute value.  The first term {{math|li(''x'')}} is the usual [[logarithmic integral function]]; the expression {{math|li(''x<sup>ρ</sup>'')}} in the second term should be considered as {{math|Ei(''ρ'' log ''x'')}}, where {{math|Ei}} is the [[analytic continuation]] of the [[exponential integral]] function from negative reals to the complex plane with branch cut along the positive reals. The final integral is equal to the series over the trivial zeros:

:<math>\int_x^\infty \frac{\mathrm dt}{t \left(t^2 - 1\right) \log t}=\int_x^\infty \frac{1}{t\log t}
\left(\sum_{m}t^{-2m}\right)\,\mathrm dt=\sum_{m}\int_x^\infty \frac{t^{-2m}}{t\log t}
\,\mathrm dt \,\,\overset{\left(u=t^{-2m}\right)}{=}-\sum_{m} \operatorname{li}\left(x^{-2m}\right)
</math>

Thus, [[Möbius inversion formula]] gives us<ref name="RieselGohl" />

:<math>\pi_0(x) = \operatorname{R}(x) - \sum_{\rho}\operatorname{R}\left(x^\rho\right) - \sum_{m} \operatorname{R}\left(x^{-2m}\right)</math>

valid for {{math|''x'' > 1}}, where

:<math>\operatorname{R}(x) = \sum_{n=1}^{\infty} \frac{\mu(n)}{n} \operatorname{li}\left(x^{1/n}\right) = 1 + \sum_{k=1}^\infty \frac{\left(\log x\right)^k}{k! k \zeta(k+1)}</math>

is Riemann's R-function<ref name="mathworld_r">{{MathWorld |title=Riemann Prime Counting Function |urlname=RiemannPrimeCountingFunction}}</ref> and {{math|''μ''(''n'')}} is the [[Möbius function]]. The latter series for it is known as [[Jørgen Pedersen Gram|Gram]] series.<ref name="Riesel94">{{cite book | title=Prime Numbers and Computer Methods for Factorization | edition=2nd | first=Hans | last=Riesel | author-link=Hans Riesel | series=Progress in Mathematics | volume=126 | publisher=Birkhäuser | year=1994 | isbn=0-8176-3743-5 | pages=50–51 }}</ref><ref name="mathworld_gram">{{MathWorld |title=Gram Series |urlname=GramSeries}}</ref> Because {{math|log ''x'' < ''x''}} for all {{math|''x'' > 0}}, this series converges for all positive {{mvar|x}} by comparison with the series for {{mvar|e<sup>x</sup>}}. The logarithm in the Gram series of the sum over the non-trivial zero contribution should be evaluated as {{math|''ρ'' log ''x''}} and not {{math|log ''x<sup>ρ</sup>''}}.

Folkmar Bornemann proved,<ref>{{cite web |last=Bornemann | first=Folkmar |title=Solution of a Problem Posed by Jörg Waldvogel |url=http://www-m3.ma.tum.de/bornemann/RiemannRZero.pdf }}</ref> when assuming the [[conjecture]] that all zeros of the Riemann zeta function are simple,<ref group="note">[[Hugh Lowell Montgomery|Montgomery]] showed that (assuming the Riemann hypothesis) at least two thirds of all zeros are simple.</ref> that
:<math>\operatorname{R}\left(e^{-2\pi t}\right)=\frac{1}{\pi}\sum_{k=1}^\infty\frac{(-1)^{k-1}t^{-2k-1}}{(2k+1)\zeta(2k+1)}+\frac12\sum_{\rho}\frac{t^{-\rho}}{\rho\cos\frac{\pi\rho}{2}\zeta'(\rho)}</math>
where {{mvar|ρ}} runs over the non-trivial zeros of the Riemann zeta function and {{math|''t'' > 0}}.

The sum over non-trivial zeta zeros in the formula for {{math|''π''<sub>0</sub>(''x'')}} describes the fluctuations of {{math|''π''<sub>0</sub>(''x'')}} while the remaining terms give the "smooth" part of prime-counting function,<ref name="Watkins">{{cite web |title=The encoding of the prime distribution by the zeta zeros |url=http://www.secamlocal.ex.ac.uk/people/staff/mrwatkin/zeta/encoding1.htm |publisher=Matthew Watkins |access-date=2008-09-14}}</ref> so one can use

:<math>\operatorname{R}(x) - \sum_{m=1}^\infty \operatorname{R}\left(x^{-2m}\right)</math>

as a good estimator of {{math|''π''(''x'')}} for {{math|''x'' > 1}}. In fact, since the second term approaches 0 as {{math|''x'' → ∞}}, while the amplitude of the "noisy" part is heuristically about {{math|{{sfrac|{{sqrt|''x''}}|log ''x''}}}}, estimating {{math|''π''(''x'')}} by {{math|R(''x'')}} alone is just as good, and fluctuations of the [[distribution of primes]] may be clearly represented with the function

:<math>\bigl( \pi_0(x) - \operatorname{R}(x)\bigr) \frac{\log x}{\sqrt x}.</math>

==Inequalities==
[[Srinivasa Ramanujan|Ramanujan]]<ref>{{Cite book|url=https://books.google.com/books?id=QoMHCAAAQBAJ|title=Ramanujan's Notebooks, Part IV|last=Berndt|first=Bruce C.|date=2012-12-06|pages=112–113|publisher=Springer Science & Business Media|isbn=9781461269328|language=en}}</ref> proved that the inequality
:<math>\pi(x)^2 < \frac{ex}{\log x} \pi\left( \frac{x}{e} \right)</math>
holds for all sufficiently large values of {{mvar|x}}.

Here are some useful inequalities for {{math|''π''(''x'')}}.

:<math> \frac x {\log x} < \pi(x) < 1.25506 \frac x {\log x} \quad \text{for }x \ge 17.</math>

The left inequality holds for {{math|''x'' ≥ 17}} and the right inequality holds for {{math|''x'' > 1}}. The constant {{#expr:30*ln(113)/113 round 5}} is {{math|30{{sfrac|log 113|113}}}} to 5 decimal places, as {{math|''π''(''x'') {{sfrac|log ''x''|''x''}}}} has its maximum value at {{math|1=''x'' = ''p''<sub>30</sub> = 113}}.<ref name=Rosser1962>{{Cite journal | author-link = J. Barkley Rosser | last1 = Rosser | first1 = J. Barkley | last2 = Schoenfeld | first2 = Lowell | title = Approximate formulas for some functions of prime numbers | journal = [[Illinois J. Math.]] | year = 1962 | volume = 6 | pages = 64–94 | doi = 10.1215/ijm/1255631807 | zbl = 0122.05001 | issn = 0019-2082 | url = https://projecteuclid.org/euclid.ijm/1255631807 | doi-access = free }}</ref>

[[Pierre Dusart]] proved in 2010:<ref name = "Dusart2010">{{cite arXiv  |last = Dusart |first = Pierre |author-link = Pierre Dusart |eprint=1002.0442v1 |title = Estimates of Some Functions Over Primes without R.H. |class = math.NT |date = 2 Feb 2010 }}</ref>

:<math> \frac {x} {\log x - 1} < \pi(x) < \frac {x} {\log x - 1.1}\quad \text{for }x \ge 5393 \text{ and }x \ge 60184,\text{ respectively.}</math>

More recently, Dusart has proved<ref>{{cite journal |last = Dusart |first = Pierre |author-link = Pierre Dusart |title = Explicit estimates of some functions over primes |journal = Ramanujan Journal |volume = 45 |issue = 1 |pages=225–234 |date = January 2018 |doi = 10.1007/s11139-016-9839-4|s2cid = 125120533 }}</ref>
(Theorem 5.1) that
:<math>\frac{x}{\log x} \left( 1 + \frac{1}{\log x} + \frac{2}{\log^2 x} \right) \le \pi(x) \le \frac{x}{\log x} \left( 1 + \frac{1}{\log x} + \frac{2}{\log^2 x} + \frac{7.59}{\log^3 x} \right),</math>
for {{math|''x'' ≥ 88789}} and  {{math|''x'' > 1}}, respectively.

Going in the other direction, an approximation for the {{mvar|n}}th  prime, {{mvar|p<sub>n</sub>}}, is
:<math>p_n = n \left(\log n + \log\log n - 1 + \frac {\log\log n - 2}{\log n} + O\left( \frac {(\log\log n)^2} {(\log n)^2}\right)\right).</math>

Here are some inequalities for the {{mvar|n}}th prime. The lower bound is due to Dusart (1999)<ref>{{cite journal
| author-link=Pierre Dusart
| last       = Dusart
| first      = Pierre
| date       = January 1999
| title      = The ''k<sup>th</sup>'' prime is greater than ''k''(ln ''k'' + ln ln ''k'' − 1) for ''k'' ≥ 2
| journal    = Mathematics of Computation
| volume     = 68
| issue      = 225
| pages      = 411–415
| doi        = 10.1090/S0025-5718-99-01037-6
| doi-access = free
| bibcode    = 1999MaCom..68..411D
| url        = https://www.ams.org/mcom/1999-68-225/S0025-5718-99-01037-6/S0025-5718-99-01037-6.pdf
}}</ref> and the upper bound to Rosser (1941).<ref>{{cite journal
| first      = Barkley | last = Rosser | author-link = J. Barkley Rosser
| date       = January 1941
| title      = Explicit bounds for some functions of prime numbers
| jstor      = 2371291
| journal    = American Journal of Mathematics
| volume     = 63
| issue      = 1
| pages      = 211–232
| doi        = 10.2307/2371291
}}</ref>

:<math> n (\log n + \log\log n - 1) < p_n < n (\log n + \log\log n)\quad \text{for } n \ge 6.</math>

The left inequality holds for {{math|''n'' ≥ 2}} and the right inequality holds for {{math|''n'' ≥ 6}}.  A variant form sometimes seen substitutes <math>\log n +\log\log n = \log(n \log n).</math>  An even simpler lower bound is<ref name=Rosser62>{{cite journal
| title      = Approximate formulas for some functions of prime numbers
| first1     = J. Barkley | last1 = Rosser | author1-link = J. Barkley Rosser
| first2     = Lowell | last2 = Schoenfeld | author2-link = Lowell Schoenfeld
| journal    = Illinois Journal of Mathematics
| volume     = 6
| issue      = 1
| pages      = 64–94
| date       = March 1962
| doi        = 10.1215/ijm/1255631807
}}</ref>
:<math>n \log n < p_n,</math>
which holds for all {{math|''n'' ≥ 1}}, but the lower bound above is tighter for {{math|''n'' > ''e<sup>e</sup>'' &asymp;{{#expr:exp(exp(1)) round 3}}}}.

In 2010 Dusart proved<ref name = "Dusart2010" /> (Propositions 6.7 and 6.6) that
:<math> n \left( \log n + \log \log n - 1 + \frac{\log \log n - 2.1}{\log n} \right) \le p_n \le n \left( \log n + \log \log n - 1 + \frac{\log \log n - 2}{\log n} \right),</math>
for {{math|''n'' ≥ 3}} and {{math|''n'' ≥ 688383}}, respectively.

In 2024, Axler<ref>{{cite journal
| title      = New estimates for the ''n''th prime number
| first      = Christian | last = Axler
| journal    = Journal of Integer Sequences
| volume     = 19
| issue      = 4
| article-number = 2
| date       = 2019
| orig-date  = 23 Mar 2017
| arxiv      = 1706.03651
| url        = https://cs.uwaterloo.ca/journals/JIS/VOL22/Axler/axler17.html
}}</ref> further tightened this (equations 1.12 and 1.13) using bounds of the form
:<math> f(n,g(w)) = n \left( \log n + \log\log n - 1 + \frac{\log\log n - 2}{\log n} - \frac{g(\log\log n)}{2\log^2 n} \right)</math>
proving that
:<math> f(n, w^2 - 6w + 11.321) \le p_n \le f(n, w^2 - 6w)</math>
for {{math|''n'' ≥ 2}} and {{math|''n'' ≥ 3468}}, respectively.
The lower bound may also be simplified to {{math|''f''(''n'', ''w''<sup>2</sup>)}} without altering its validity.  The upper bound may be tightened to {{math|''f''(''n'', ''w''<sup>2</sup> − 6''w'' + 10.667)}} if {{math|''n'' ≥ 46254381}}.

There are additional bounds of varying complexity.<ref>{{cite web
| title      = Bounds for ''n''-th prime
| url        = https://math.stackexchange.com/questions/1270814/bounds-for-n-th-prime
| date       = 31 December 2015
| website    = Mathematics StackExchange
}}</ref><ref>{{cite journal
| title      = New Estimates for Some Functions Defined Over Primes 
| first      = Christian | last = Axler
| journal    = Integers
| volume     = 18
| article-number = A52
| doi        = 10.5281/zenodo.10677755
| doi-access = free
| date       = 2018
| orig-date  = 23 Mar 2017
| arxiv      = 1703.08032
| url        = https://math.colgate.edu/~integers/s52/s52.pdf
}}</ref><ref>{{cite journal
| title      = Effective Estimates for Some Functions Defined over Primes 
| first      = Christian | last = Axler
| journal    = Integers
| volume     = 24
| article-number = A34
| doi        = 10.5281/zenodo.10677755
| doi-access = free
| date       = 2024
| orig-date  = 11 Mar 2022
| arxiv      = 2203.05917 
| url        = https://math.colgate.edu/~integers/y34/y34.pdf
}}</ref>

==The Riemann hypothesis==

The [[Riemann hypothesis]] implies a much tighter bound on the error in the estimate for {{math|''π''(''x'')}}, and hence to a more regular distribution of prime numbers,

:<math>\pi(x) = \operatorname{li}(x) + O(\sqrt{x} \log{x}).</math>
Specifically,<ref>{{Cite journal | last1=Schoenfeld | first1=Lowell |author-link=Lowell Schoenfeld| title=Sharper bounds for the Chebyshev functions ''θ''(''x'') and ''ψ''(''x''). II | doi=10.2307/2005976 | mr=0457374  | year=1976 | journal=[[Mathematics of Computation]] | issn=0025-5718 | volume=30 | issue=134 | pages=337–360 | jstor=2005976 | publisher=American Mathematical Society}}</ref>

:<math>|\pi(x) - \operatorname{li}(x)| < \frac{\sqrt{x}}{8\pi} \, \log{x}, \quad \text{for all } x \ge 2657. </math>

{{harvtxt|Dudek|2015}} proved that the Riemann hypothesis implies that for all {{math|''x'' ≥ 2}} there is a prime {{mvar|p}} satisfying
:<math>x - \frac{4}{\pi} \sqrt{x} \log x < p \leq x.</math>

== See also ==
* [[Bertrand's postulate]]
* [[Oppermann's conjecture]]
* [[Ramanujan prime]]

==References==
{{Reflist}}
===Notes===
{{reflist|group=note}}
==External links==
*Chris Caldwell, [http://primes.utm.edu/nthprime/ ''The Nth Prime Page''] at The [[Prime Pages]].
*Tomás Oliveira e Silva, [http://sweet.ua.pt/tos/primes.html Tables of prime-counting functions].
* {{Citation| last=Dudek|first=Adrian W.|date=2015|title=On the Riemann hypothesis and the difference between primes|journal=International Journal of Number Theory|volume=11|issue=3|pages=771–778|doi=10.1142/S1793042115500426|issn=1793-0421|arxiv=1402.6417|bibcode=2014arXiv1402.6417D|s2cid=119321107}}

{{DEFAULTSORT:Prime-Counting Function}}
[[Category:Analytic number theory]]
[[Category:Prime numbers]]
[[Category:Arithmetic functions]]