info prev up next book cdrom email home

Prime Counting Function

\begin{figure}\begin{center}\BoxedEPSF{PrimeCountingFunction.epsf scaled 850}\end{center}\end{figure}

The function $\pi(n)$ giving the number of Primes less than $n$ (Shanks 1993, p. 15). The first few values are 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, ... (Sloane's A000720). The following table gives the values of $\pi(n)$ for powers of 10 (Sloane's A006880; Hardy and Wright 1979, p. 4; Shanks 1993, pp. 242-243; Ribenboim 1996, p. 237). Deleglise and Rivat (1996) have computed $\pi(10^{20})$.

$\displaystyle \pi(10^3)$ $\textstyle =$ $\displaystyle 168$  
$\displaystyle \pi(10^4)$ $\textstyle =$ $\displaystyle 1{,}229$  
$\displaystyle \pi(10^5)$ $\textstyle =$ $\displaystyle 9{,}592$  
$\displaystyle \pi(10^6)$ $\textstyle =$ $\displaystyle 78,498$  
$\displaystyle \pi(10^7)$ $\textstyle =$ $\displaystyle 664,579$  
$\displaystyle \pi(10^8)$ $\textstyle =$ $\displaystyle 5,761,455$  
$\displaystyle \pi(10^9)$ $\textstyle =$ $\displaystyle 50,847,534$  
$\displaystyle \pi(10^{10})$ $\textstyle =$ $\displaystyle 455,052,511$  
$\displaystyle \pi(10^{11})$ $\textstyle =$ $\displaystyle 4,118,054,813$  
$\displaystyle \pi(10^{12})$ $\textstyle =$ $\displaystyle 37,607,912,018$  
$\displaystyle \pi(10^{13})$ $\textstyle =$ $\displaystyle 346,065,536,839$  
$\displaystyle \pi(10^{14})$ $\textstyle =$ $\displaystyle 3,204,941,750,802$  
$\displaystyle \pi(10^{15})$ $\textstyle =$ $\displaystyle 29,844,570,422,669$  
$\displaystyle \pi(10^{16})$ $\textstyle =$ $\displaystyle 279,238,341,033,925$  
$\displaystyle \pi(10^{17})$ $\textstyle =$ $\displaystyle 2,623,557,157,654,233$  
$\displaystyle \pi(10^{18})$ $\textstyle =$ $\displaystyle 24,739,954,287,740,860$  
$\displaystyle \pi(10^{19})$ $\textstyle =$ $\displaystyle 234,057,667,276,344,607,$  

$\pi(10^9)$ is incorrectly given as 50,847,478 in Hardy and Wright (1979). 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).

Method Time Storage
Legendre ${\mathcal O}(x)$ ${\mathcal O}(x^{1/2})$
Meissel ${\mathcal O}(x/(\ln x)^3)$ ${\mathcal O}(x^{1/2}/\ln x)$
Lehmer ${\mathcal O}(x/(\ln x)^4)$ ${\mathcal O}(x^{1/3}/\ln x)$
Mapes' ${\mathcal O}(x^{0.7})$ ${\mathcal O}(x^{0.7})$
Lagarias-Miller-Odlyzko ${\mathcal O}(x^{2/3+\epsilon})$ ${\mathcal O}(x^{1/3+\epsilon})$
Lagarias-Odlyzko 1 ${\mathcal O}(x^{3/5+\epsilon})$ ${\mathcal O}(x^\epsilon)$
Lagarias-Odlyzko 2 ${\mathcal O}(x^{1/2+\epsilon})$ ${\mathcal O}(x^{1/4+\epsilon})$


A modified version of the prime counting function is given by

\begin{displaymath} \pi_0(p)\equiv\cases{ \pi(p) & for $p$\ composite\cr \pi(p)-{\textstyle{1\over 2}}& for $p$\ prime\cr} \end{displaymath}


\begin{displaymath} \pi_0(p) = \sum_{n=1}^\infty {\mu(x)f(x^{1/n})\over n}, \end{displaymath}

where $\mu(n)$ is the Möbius Function and $f(x)$ is the Riemann-Mangoldt Function.


The notation $\pi_{a,b}$ is also used to denote the number of Primes of the form $ak+b$ (Shanks 1993, pp. 21-22). Groups of Equinumerous values of $\pi_{a,b}$ include ($\pi_{3,1}$, $\pi_{3,2}$), ($\pi_{4,1}$, $\pi_{4,3}$), ($\pi_{5,1}$, $\pi_{5,2}$, $\pi_{5,3}$, $\pi_{5,4}$), ($\pi_{6,1}$, $\pi_{6,5}$), ($\pi_{7,1}$, $\pi_{7,2}$, $\pi_{7,3}$, $\pi_{7,4}$, $\pi_{7,5}$, $\pi_{7,6}$), ($\pi_{8,1}$, $\pi_{8,3}$, $\pi_{8,5}$, $\pi_{8,7}$), ($\pi_{9,1}$, $\pi_{9,2}$, $\pi_{9,4}$, $\pi_{9,5}$, $\pi_{9,7}$, $\pi_{9,8}$), and so on. The values of $\pi_{n,k}$ for small $n$ are given in the following table for the first few powers of ten (Shanks 1993).

$n$ $\pi_{3,1}(n)$ $\pi_{3,2}(n)$ $\pi_{4,1}(n)$ $\pi_{4,3}(n)$
$10^1$ 1 2 1 2
$10^2$ 11 13 11 13
$10^3$ 80 87 80 87
$10^4$ 611 617 609 619
$10^5$ 4784 4807 4783 4808
$10^6$ 39231 39266 39175 39322
$10^7$ 332194 332384 332180 332398

$n$ $\pi_{5,1}(n)$ $\pi_{5,2}(n)$ $\pi_{5,3}(n)$ $\pi_{5,4}(n)$
$10^1$ 0 2 1 0
$10^2$ 5 7 7 5
$10^3$ 40 47 42 38
$10^4$ 306 309 310 303
$10^5$ 2387 2412 2402 2390
$10^6$ 19617 19622 19665 19593
$10^7$ 166104 166212 166230 166032

$n$ $\pi_{6,1}(n)$ $\pi_{6,5}(n)$
$10^1$ 1 1
$10^2$ 11 12
$10^3$ 80 86
$10^4$ 611 616
$10^5$ 4784 4806
$10^6$ 39231 39265

$n$ $\pi_{7,1}$ $\pi_{7,2}$ $\pi_{7,3}$ $\pi_{7,4}$ $\pi_{7,5}$ $\pi_{7,6}$
$10^1$ 0 1 1 0 1 0
$10^2$ 3 4 5 3 5 4
$10^3$ 28 27 30 26 29 27
$10^4$ 203 203 209 202 211 200
$10^5$ 1593 1584 1613 1601 1604 1596
$10^6$ 13063 13065 13105 13069 13105 13090

$n$ $\pi_{8,1}(n)$ $\pi_{8,3}(n)$ $\pi_{8,5}(n)$ $\pi_{8,7}(n)$
$10^1$ 0 1 1 1
$10^2$ 5 7 6 6
$10^3$ 37 44 43 43
$10^4$ 295 311 314 308
$10^5$ 2384 2409 2399 2399
$10^6$ 19552 19653 19623 19669
$10^7$ 165976 166161 166204 166237

Note that since $\pi_{8,1}(n)$, $\pi_{8,3}(n)$, $\pi_{8,5}(n)$, and $\pi_{8,7}(n)$ are Equinumerous,

$\displaystyle \pi_{4,1}(n)$ $\textstyle =$ $\displaystyle \pi_{8,1}(n)+\pi_{8,5}$  
$\displaystyle \pi_{4,3}(n)$ $\textstyle =$ $\displaystyle \pi_{8,3}(n)+\pi_{8,7}$  

are also equinumerous.


Erdös proved that there exist at least one Prime of the form $4k+1$ and at least one Prime of the form $4k+3$ between $n$ and $2n$ for all $n>6$.


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

See also Bertelsen's Number, Equinumerous, Prime Arithmetic Progression, Prime Number Theorem, Riemann Weighted Prime-Power Counting Function


References

Berndt, B. C. Ramanujan's Notebooks, Part IV. New York: Springer-Verlag, pp. 134-135, 1994.

Brent, R. P. ``Irregularities in the Distribution of Primes and Twin Primes.'' Math. Comput. 29, 43-56, 1975.

Deleglise, M. and Rivat, J. ``Computing $\pi(x)$: The Meissel, Lehmer, Lagarias, Miller, Odlyzko Method.'' Math. Comput. 65, 235-245, 1996.

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/hrdyltl/hrdyltl.html

Forbes, T. ``Prime $k$-tuplets.'' http://www.ltkz.demon.co.uk/ktuplets.htm.

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. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.

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.

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.

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.

Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, 1993.

Sloane, N. J. A. Sequences A038625, A038626, A038627, A000720/M0256, and A006880/M3608 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.

Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 74-76, 1991.

Wolf, M. ``Unexpected Regularities in the Distribution of Prime Numbers.'' http://rose.ift.uni.wroc.pl/~mwolf/.


info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26