- Introduction: Asking the Correct Question
- The Prime Number Theorem
- Consequence One: You can Approximate pi(
*x*) with*x*/(log*x*- 1) - Consequence Two: The
*n*th prime is about*n*log*n* - Consequence Three: The chance of a random integer
*x*being prime is about 1/log*x*

- Consequence One: You can Approximate pi(
- History of the Prime Number Theorem and other approximations
of pi(
*x*) - There are better estimates!

Notes: (1) Rather than fill this document with gifs like ""
(which can not be displayed on some browsers and display poorly on
others), I am going to just write pi(x). (2) log x,
in this document, is the natural logarithm. This is sometimes
denoted ln x, but log x is the mathematical standard. |

- How many primes are there less than the number x?
- There are infinitely many primes, but how big of an infinity?

=The primes under 25 are 2, 3, 5, 7, 11, 13, 17, 19 and 23 so pi(3) = 2, pi(10) = 4 and pi(25) = 9. (A longer table can be found in the next sub-section.) Look at the following graph and notice how irregular the graph of pi(pi(x) = the number of primes less than or equal tox.

In this document we will study the function pi(*x*), the prime number theorem (which quantifies
this trend) and several classical approximation to pi(*x*).

Table 1. Values of pi(x)

xpi( x)reference 1 10 4 2 100 25 3 1,000 168 4 10,000 1,229 5 100,000 9,592 6 1,000,000 78,498 7 10,000,000 664,579 8 100,000,000 5,761,455 9 1,000,000,000 50,847,534 10 10,000,000,000 455,052,511 11 100,000,000,000 4,118,054,813 12 1,000,000,000,000 37,607,912,018 13 10,000,000,000,000 346,065,536,839 14 100,000,000,000,000 3,204,941,750,802 [LMO85] 15 1,000,000,000,000,000 29,844,570,422,669 [LMO85] 16 10,000,000,000,000,000 279,238,341,033,925 [LMO85] 17 100,000,000,000,000,000 2,623,557,157,654,233 [DR96] 18 1,000,000,000,000,000,000 24,739,954,287,740,860 [DR96] 19 10,000,000,000,000,000,000 234,057,667,276,344,607 20 100,000,000,000,000,000,000 2,220,819,602,560,918,840 21 1,000,000,000,000,000,000,000 21,127,269,486,018,731,928 22 10,000,000,000,000,000,000,000 201,467,286,689,315,906,290 23 100,000,000,000,000,000,000,000 1,925,320,391,606,803,968,923 24 1,000,000,000,000,000,000,000,000 18,435,599,767,349,200,867,866 (note) 25 10,000,000,000,000,000,000,000,000 176,846,309,399,143,769,411,680

Before the age of computers many mathematicians formed tables of primes. The most widely distributed was D. N. Lehmer's table of primes to 10,006,721 [Lehmer14]. By far the most amazing was a table by Kulik completed in 1867. This table listed the smallest factors of integers (hence all the primes) up to 100,330,200!

In the 1870's Meissel developed a clever way to calculate pi(*x*) far
beyond the known tables of primes and in 1885 (slightly mis-)calculated pi(10^{9}).
Meissel's methods were simplified by D. H. Lehmer in 1959 and then in 1985
improved using sieve techniques by Lagarias, Miller and Odlyzko [LMO85].

In 1994 Deléglise and Rivat [DR96]
improved the technique once again to find the values for pi(10^{17}) and
pi(10^{18}). Deléglise continued this work with an improved
algorithm to find pi(10^{20}) and other values (see his e-mail messages
of 18 Apr 1996 and 19
Jun 1996). See Riesel94 for
practical information about how these calculations are made.

Xavier Gourdon's distributed computing project determined pi(4*10^{22}),
but
stopped when they found an error of at least one in the calculation of
pi(10^{23}).
Tomás Oliveira e Silva has extensive
tables of values of pi(*x*) and pi_{2}(*x*). In 2007
he reevaluated pi(10^{23}) to get the value in
the table. This calculation was done on a single machine and
verified in 2008.

The value given for pi(10^{24}) was found by an analytic methods assuming the
unproven
Riemann Hypothesis by J. Buethe, J. Franke, A. Jost, T. Kleinjung. Their method "is
similar to the one described by Lagarias and Odlyzko, but uses the Weil explicit formula
instead of complex curve integrals" (see their e-mail
announcing the result in July 2010). This value was later verified unconditionally
by D. J. Platt [Platt2012].

In May 2013, J. Buethe, J. Franke, A. Jost, and T. Kleinjung completed calculating pi(10^25) unconditionally, using an analytic method based on Weil's explicit formula.

In terms of pi(The Prime Number Theorem:The number of primes not exceedingxisasymptotictox/logx.

This means (roughly) thatThe Prime Number Theorem:pi(x) ~x/logx.

"If you have not had calculus then this means that you can makea(x) isasymptotictob(x)" and "a(x)~b(x)" both mean that the limit (asxapproaches infinity) of the ratioa(x)/b(x) is 1.

x |
pi(x) |
x/log x |
x/(log x -1) |
---|---|---|---|

1000 | 168 | 145 | 169 |

10000 | 1229 | 1086 | 1218 |

100000 | 9592 | 8686 | 9512 |

1000000 | 78498 | 72382 | 78030 |

10000000 | 664579 | 620420 | 661459 |

100000000 | 5761455 | 5428681 | 5740304 |

There are longer tables below and (of pi(x) only) above.

Note that Pierre Dusart [Dusart99] showed that ifExample:Someone recently e-mailed me and asked for a list ofallthe primes with at most 300 digits. Since the prime number theorem implies this list would have about 1.4*10^{297}entries we know that there can be no such list!

((The upper bound holds for allx/logx)(1 + 0.992/logx)<pi(x)<(x/logx)(1 + 1.2762/logx)

[see Hardy and Wright, page 10]. A better estimate isTheorem:p(n) ~nlogn

[see Ribenboim95, pg. 249].Theorem:p(n) ~n(logn+ log logn- 1)

There have been many improvements on these bounds; for example, Robin [Robin83] showed that ifExample:These formulae predict that the one millionth prime is about 13,800,000 and 15,400,000 respectively. In fact, the one millionth prime is 15,485,863.

More recently Massias and Robin [MR96] showed that ifn(logn+ log logn- 1.0073) < p(n) <n(logn+ log logn- 0.9385)

p(and ifn)<n(logn+ log logn- 0.9427)

p((which is better for largen)<n(logn+ log logn- 1 + 1.8 log logn/ logn)

p(for alln) >n(logn+ log logn- 1)

p(n) =n(logn+ log logn- 1 + (log log (n) - 2)/logn-

((log log (n))^{2}- 6 log log (n) + 11)/(2 log^{2}n) + O((log logn/ logn)^{3}))

Again Ribenboim95 and Riesel94
are excellent starting places to look up more information. By the way, if you
are interested in the *n*th prime for small *n* (say less than
1,000,000,000), then use the
*n*th prime page."

Example:Suppose I want to find a 1000 digit prime. If I am choosing 1000 digit integersxto test for primalityat random, then I'd expect to test about log(10^{1000}) of them, or about 2302 integers before finding a prime. Obviously if I used odd integers I could multiply this estimate by 1/2, and if I choose integers not divisible by 3, then I could multiply by 2/3,...

Another way to say this is that the density of primes less than *x* is
about 1/log *x*. Below is a graph of the actual density for small
values of *x*.

Clearly Legendre's conjecture is equivalent to the prime number theorem, the constant 1.08366 was based on his limited table for values of pi(

- Legendre:
- pi(
x) is approximatelyx/(logx- 1.08366)

Gauss was also studying prime tables and came up with a different estimate (perhaps first considered in 1791), communicated in a letter to Encke in 1849 and first published in 1863.

Notice again that Gauss' conjecture is equivalent to the prime number theorem. Let's compare these estimates:

- Gauss:
- pi(
x) is approximately Li(x) (the principal value of integral of 1/logufromu=0 tou=x).

In this table Gauss' Li(

Table 3. Comparisons of approximations to pi(x)xpi( x)Gauss' Li Legendre x/(logx- 1)R( x)1000 168 178 172 169 168.4 10000 1229 1246 1231 1218 1226.9 100000 9592 9630 9588 9512 9587.4 1000000 78498 78628 78534 78030 78527.4 10000000 664579 664918 665138 661459 664667.4 100000000 5761455 5762209 5769341 5740304 5761551.9 1000000000 50847534 50849235 50917519 50701542 50847455.4 10000000000 455052511 455055614 455743004 454011971 455050683.3

Tchebycheff made the first real progress toward a proof of the prime number
theorem in 1850, showing there exist positive constants *a* __<__ 1 __<__
*b* such that

and thata(x/logx) < pi(x) <b(x/logx)

Finally, in 1896 Hadamard and independently de la Vallée Poussin **completely
proved the prime number theorem** using Riemann's work relating pi(*x*)
to the complex zeta function. de la Vallée Poussin also proved
that Gauss' Li(*x*) is a better approximation to pi(*x*) than x/(log *x*
-*a*) no matter what value is assigned to the constant *a* (and also
that the best value for *a* is 1). A much better approximation
than any of these is the Riemann function [Ribenboim91,
Riesel94].

In 1949 Atle Selberg [Selberg49] and Paul Erdös [Erdös49] independently gave the first elementary proofs of the prime number theorem-- here elementary means not using modern complex analysis--in fact their proofs are very difficult! An easier to read (but less elementary) proof is in Hardy and Wright's text [HW79 sect. 22.15-16].

Finally, when Hadamard and de la Vallée Poussin proved the Prime number theorem, they actually showed

for some positive constant

This page focused on the prime number theorem in it simplest form, but there
are far better estimates for pi(*x*). To cut to the chase, the Riemann zeta function provides a way to give an exact formula
for pi(*x*) by summing over the non-trivial zeros of the zeta function (in order of increasing magnitude).

(At the primes, the graph of pi(

The last form above for R(

To appreciate how close of an approximation these are, see the impressive tables of deviations by Andrey Kulsha.

Matthew R. Watkins also has a beautiful development of this information and some excellent animations.

Considerable importance was attached formerly to a function suggested by Riemann as an approximation to pi(x)... This function represents pi(x) with astonishing accuracy for all values of x for which pi(x) has been calculated, but we now see that its superiority over Li(x) is illusory... and for special values of x (as large as we please) the one approximation will deviate as widely as the other from the true value.The problem is that the contributions from the non-trivial zeros at times swamps that of any but the main terms in these expansions.

... And we can see in the same way that the function Li(x)-(1/2)Li(x^{1/2}) is 'on the average' a better approximation than Li(x) to pi(x); but no importance can be attached to the latter terms in Riemann's formula even by repeated averaging.

Another prime page by Chris K. Caldwell <