A000720 - OEIS

%I M0256 N0090 #398 Oct 22 2024 02:52:20

%S 0,1,2,2,3,3,4,4,4,4,5,5,6,6,6,6,7,7,8,8,8,8,9,9,9,9,9,9,10,10,11,11,

%T 11,11,11,11,12,12,12,12,13,13,14,14,14,14,15,15,15,15,15,15,16,16,16,

%U 16,16,16,17,17,18,18,18,18,18,18,19,19,19,19,20,20,21,21,21,21,21,21

%N pi(n), the number of primes <= n. Sometimes called PrimePi(n) to distinguish it from the number 3.14159...

%C Partial sums of A010051 (characteristic function of primes). - _Jeremy Gardiner_, Aug 13 2002

%C pi(n) and prime(n) are inverse functions: a(A000040(n)) = n and A000040(n) is the least number m such that A000040(a(m)) = A000040(n). A000040(a(n)) = n if (and only if) n is prime. - _Jonathan Sondow_, Dec 27 2004

%C See the additional references and links mentioned in A143227. - _Jonathan Sondow_, Aug 03 2008

%C A lower bound that gets better with larger N is that there are at least T prime numbers less than N, where the recursive function T is: T = N - N*Sum_{i=0..T(sqrt(N))} A005867(i)/A002110(i). - _Ben Paul Thurston_, Aug 23 2010

%C Number of partitions of 2n into exactly two parts with the smallest part prime. - _Wesley Ivan Hurt_, Jul 20 2013

%C Equivalent to the Riemann hypothesis: abs(a(n) - li(n)) < sqrt(n)*log(n)/(8*Pi), for n >= 2657, where li(n) is the logarithmic integral (Lowell Schoenfeld). - _Ilya Gutkovskiy_, Jul 05 2016

%C The second Hardy-Littlewood conjecture, that pi(x) + pi(y) >= pi(x + y) for integers x and y with min{x, y} >= 2, is known to hold for (x, y) sufficiently large (Udrescu 1975). - _Peter Luschny_, Jan 12 2021

%D M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.

%D Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, p. 8.

%D Raymond Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963; p. 129.

%D Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 5.

%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, Theorems 6, 7, 420.

%D G. J. O. Jameson, The Prime Number Theorem, Camb. Univ. Press, 2003. [See also the review by D. M. Bressoud (link below).]

%D Władysław Narkiewicz, The Development of Prime Number Theory, Springer-Verlag, 2000.

%D József Sándor, Dragoslav S. Mitrinovic and Borislav Crstici, Handbook of Number Theory I, Springer Science & Business Media, 2005, Section VII.1. (For inequalities, etc.).

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D Gerald Tenenbaum and Michel Mendès France, Prime Numbers and Their Distribution, AMS Providence RI, 1999.

%D V. Udrescu, Some remarks concerning the conjecture pi(x + y) <= pi(x) + pi(y). Math. Pures Appl. 20 (1975), 1201-1208.

%H Daniel Forgues, <a href="/A000720/b000720.txt">Table of n, pi(n) for n = 1..100000</a> (first 20000 terms from N. J. A. Sloane; see below for links with 823852 terms (Verma) and more (Caldwell))

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

%H Christian Axler, <a href="http://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=26247">Über die Primzahl-Zählfunktion, die n-te Primzahl und verallgemeinerte Ramanujan-Primzahlen</a>, Ph.D. thesis 2013, in German, English summary.

%H Paul T. Bateman and Harold G. Diamond, <a href="http://www.jstor.org/stable/2974443">A Hundred Years of Prime Numbers</a>, Amer. Math. Month., Vol. 103, No. 9 (Nov. 1996), pp. 729-741, MAA Washington DC.

%H Steve Bennett, <a href="https://web.archive.org/web/20110926073136/http://www.freewebs.com/history_of_mathematics">The role of Riemann's zeta function in the analytic proof of the Prime Number Theorem</a>, 2004.

%H Claudio Bonanno and Mirko S. Mega, <a href="https://doi.org/10.1016/S0960-0779(03)00433-8">Toward a dynamical model for prime numbers</a>, Chaos, Solitons & Fractals, Vol. 20, No. 1 (2004), pp. 107-118; <a href="https://arxiv.org/abs/cond-mat/0309251">arXiv preprint</a>, arXiv:cond-mat/0309251, 2003.

%H David M. Bressoud, <a href="https://www.maa.org/press/maa-reviews/the-prime-number-theorem">Review of "The Prime Number Theorem" by G. J. O. Jameson</a>, MAA Reviews, 2005. - from _N. J. A. Sloane_, Dec 29 2018

%H D. M. Bressoud and Stan Wagon, <a href="http://www.msri.org/realvideo/ln/msri/2000/introant/wagon/1/main.html">Computational Number Theory: Basic Algorithms</a>, Springer/Key, 2000 (with a Mathematica package for computational number theory).

%H Ben Brubaker, <a href="https://web.archive.org/web/20171215121316/http://math.stanford.edu/~brubaker/pnt.pdf">The Prime Number Theorem</a>.

%H C. K. Caldwell, <a href="https://t5k.org/glossary/page.php/PrimeNumberThm.html">The Prime Glossary: Prime number theorem</a>.

%H W. W. L. Chen, <a href="http://www.williamchen-mathematics.info/lndpnfolder/lndpn.html">Distribution of Prime Numbers</a>.

%H Jean-Marie de Koninck and Aleksandar Ivić, <a href="https://www.sciencedirect.com/bookseries/north-holland-mathematics-studies/vol/43">Topics in Arithmetical Functions: Asymptotic Formulae for Sums of Reciprocals of Arithmetical Functions and Related Fields</a>, Amsterdam, Netherlands: North-Holland, 1980. See Chapter 9, p. 231.

%H Marc Deléglise, <a href="http://algo.inria.fr/seminars/sem95-96/deleglise.pdf">Computation of large values of pi(x)</a>, 1996.

%H Pierre Dusart, <a href="http://www.unilim.fr/laco/theses/1998/T1998_01.pdf">Autour de la fonction qui compte le nombre de nombres premiers</a>, Thèse, Université de Limoges, France (1998).

%H Pierre Dusart, <a href="http://dx.doi.org/10.1090/S0025-5718-99-01037-6">The k-th prime is greater than k(ln k + ln ln k-1) for k>=2</a>, Mathematics of Computation, Vo. 68, No. 225 (1999), pp. 411-415.

%H Encyclopedia Britannica, <a href="http://web.archive.org/web/20110824045457/http://users.forthnet.gr:80/ath/kimon/PNT/Prime%20Number%20Theorem.htm">The Prime Number Theorem</a> [web.archive.org's copy of a no longer available personal copy of the Encyclopedia's article]

%H R. Gray and J. D. Mitchell, <a href="http://dx.doi.org/10.1016/j.disc.2007.08.075">Largest subsemigroups of the full transformation monoid</a>, Discrete Math., 308 (2008), 4801-4810.

%H G. H. Hardy and J. E. Littlewood, <a href="https://doi.org/10.1007/BF02422942">Contributions to the theory of the Riemann zeta-function and the theory of the distribution of primes</a>, Acta Mathematica, Vol. 41 (1916), pp. 119-196.

%H G. H. Hardy and J. E. Littlewood, <a href="https://doi.org/10.1007/BF02403921">Some problems of 'Partitio numerorum'; III: On the expression of a number as a sum of primes</a>, Acta Math., Vol. 44, No. 1 (1923), pp. 1-70.

%H Mehdi Hassani, <a href="https://www.emis.de/journals/JIPAM/article643.html?sid=643">Approximation of pi(x) by Psi(x)</a>, J. Inequ. Pure Appl. Math., Vol. 7, No. 1 (2006), Article #7.

%H Y.-C. Kim, <a href="https://arxiv.org/abs/math/0502062">Note on the Prime Number Theorem</a>, arXiv:math/0502062 [math.NT], 2005.

%H Tzanio V. Kolev, <a href="https://www.researchgate.net/publication/2585909_On_the_Number_of_Prime_Numbers_less_than_a_Given_Quantity">On the number of Prime Numbers less than a Given Quantity</a>, 2000.

%H Angel V. Kumchev, <a href="https://tigerweb.towson.edu/akumchev/distributionofprimesnotes.pdf">The Distribution of Prime Numbers</a>, 2005.

%H J. C. Lagarias, V. S. Miller and A. M. Odlyzko, <a href="https://doi.org/10.1090/S0025-5718-1985-0777285-5">Computing pi(x): The Meissel-Lehmer method</a>, Math. Comp., Vol. 44, No. 170 (1985), pp. 537-560.

%H Jeffrey C. Lagarias and Andrew M. Odlyzko, <a href="https://doi.org/10.1016/0196-6774(87)90037-X">Computing pi(x): An analytic method</a>, Journal of Algorithms, Vol. 8, No. 2 (1987), pp. 173-191; <a href="http://www.dtc.umn.edu/~odlyzko/doc/cnt.html">alternative link</a>.

%H John Lorch, <a href="http://www.bsu.edu/libraries/beneficencepress/mathexchange/03-01/Lorch.pdf">The Distribution of Primes</a>, B.S. Undergraduate Mathematics Exchange, Vol. 3, No. 1 (Fall 2005).

%H Nathan McKenzie, <a href="http://www.icecreambreakfast.com/primecount/primecounting.php">Computing the Prime Counting Function with Linnik's Identity</a>, personal blog, March 24, 2011.

%H Murat Baris Paksoy, <a href="https://arxiv.org/abs/1210.6991">Derived Ramanujan primes: R'_n</a>, arXiv:1210.6991 [math.NT], 2012.

%H Bent E. Petersen, <a href="https://www.math.ucdavis.edu/~tracy/courses/math205A/PNT_Petersen.pdf">Prime Number Theorem</a>, Seminar Lecture Note, 1996; <a href="http://citeseerx.ist.psu.edu/pdf/118ddc1708154d5a7d5aaf28b9527c33f0ee5b69">version 2002-05-14</a>.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H Omar E. Pol, <a href="http://www.polprimos.com">Determinacion geometrica de los numeros primos y perfectos</a>, personal website, 2001 (?); <a href="http://www.polprimos.com/imagenespub/polprdipi.jpg">Illustration of initial terms: Divisors and pi(x)</a>.

%H Bernhard Riemann, <a href="http://www.maths.tcd.ie/pub/HistMath/People/Riemann/Zeta/">On the Number of Prime Numbers</a>, 1859, last page (various transcripts)

%H J. Barkley Rosser, <a href="http://www.jstor.org/stable/2371291">Explicit Bounds for Some Functions of Prime Numbers</a>, American Journal of Mathematics, Vol. 63, No. 1 (1941), pp. 211-232.

%H J. Barkley Rosser and Lowell Schoenfeld, <a href="http://projecteuclid.org/euclid.ijm/1255631807">Approximate formulas for some functions of prime numbers</a>, Ill. Journ. Math. 6 (1962) 64-94.

%H J. Barkley Rosser and Lowell Schoenfeld, <a href="/A000720/a000720.html">Approximate formulas for some functions of prime numbers</a> (scan of some key pages from an ancient annotated photocopy).

%H Sebastian Martin Ruiz and Jonathan Sondow, <a href="https://arxiv.org/abs/math/0210312">Formulas for pi(n) and the n-th prime</a>, arXiv:math/0210312 [math.NT], 2002, 2014.

%H Jeffrey Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/bib/pi.bib">Bibliography on calculation of pi(x)</a>.

%H Jonathan Sondow, <a href="https://www.jstor.org/stable/40391170">Ramanujan Primes and Bertrand's Postulate</a>, The American Mathematical Monthly, Vol. 116, No. 7 (2009), pp. 630-635; <a href="https://arxiv.org/abs/0907.5232">arXiv preprint</a>, arXiv:0907.5232 [math.NT], 2009-2010.

%H Igor Turkanov, <a href="https://arxiv.org/abs/1603.02914">The prime counting function</a>, arXiv:1603.02914 [math.NT], 2016.

%H Gaurav Verma and Srujan Sapkal, <a href="/A000720/a000720.txt">Table of n, pi(n) for n = 1..823852</a>.

%H Matthew R. Watkins, <a href="https://web.archive.org/web/20200111044829/http://empslocal.ex.ac.uk/people/staff/mrwatkin//zeta/ss-a.htm">The distribution of Prime Numbers</a>.

%H Matthew R. Watkins, <a href="https://web.archive.org/web/20040214162502/http://www.maths.ex.ac.uk/~mwatkins/zeta/pnt.htm">The prime number theorem (some references)</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimeCountingFunction.html">Prime Counting Function</a>.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Prime_number_theorem">Prime number theorem</a>.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Prime-counting_function">Prime-counting function</a>.

%H Marek Wolf, <a href="https://doi.org/10.1016/S0378-4371(99)00318-0">Applications of Statistical Mechanics in Number Theory</a>, Physica A, vol. 274, no. 2, 1999, pp. 149-157; <a href="http://www.maths.ex.ac.uk/~mwatkins/zeta/wolfgas.htm">1999 preprint</a>.

%H Wolfram Research, <a href="http://functions.wolfram.com/NumberTheoryFunctions/PrimePi/03/02">First 50 values of pi(n)</a>.

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%F The prime number theorem gives the asymptotic expression a(n) ~ n/log(n).

%F For x > 1, pi(x) < (x / log x) * (1 + 3/(2 log x)). For x >= 59, pi(x) > (x / log x) * (1 + 1/(2 log x)). [Rosser and Schoenfeld]

%F For x >= 355991, pi(x) < (x / log(x)) * (1 + 1/log(x) + 2.51/(log(x))^2 ). For x >= 599, pi(x) > (x / log(x)) * (1 + 1/log(x)). [Dusart]

%F For x >= 55, x/(log(x) + 2) < pi(x) < x/(log(x) - 4). [Rosser]

%F For n > 1, A138194(n) <= a(n) <= A138195(n) (Tschebyscheff, 1850). - _Reinhard Zumkeller_, Mar 04 2008

%F For n >= 33, a(n) = 1 + Sum_{j=3..n} ((j-2)! - j*floor((j-2)!/j)) (Hardy and Wright); for n >= 1, a(n) = n - 1 + Sum_{j=2..n} (floor((2 - Sum_{i=1..j} (floor(j/i)-floor((j-1)/i)))/j)) (Ruiz and Sondow 2000). - _Benoit Cloitre_, Aug 31 2003

%F a(n) = A001221(A000142(n)). - _Benoit Cloitre_, Jun 03 2005

%F G.f.: Sum_{p prime} x^p/(1-x) = b(x)/(1-x), where b(x) is the g.f. for A010051. - _Franklin T. Adams-Watters_, Jun 15 2006

%F a(n) = A036234(n) - 1. - _Jaroslav Krizek_, Mar 23 2009

%F From _Enrique Pérez Herrero_, Jul 12 2010: (Start)

%F a(n) = Sum_{i=2..n} floor((i+1)/A000203(i)).

%F a(n) = Sum_{i=2..n} floor(A000010(n)/(i-1)).

%F a(n) = Sum_{i=2..n} floor(2/A000005(n)). (End)

%F Let pf(n) denote the set of prime factors of an integer n. Then a(n) = card(pf(n!/floor(n/2)!)). - _Peter Luschny_, Mar 13 2011

%F a(n) = -Sum_{p <= n} mu(p). - _Wesley Ivan Hurt_, Jan 04 2013

%F a(n) = (1/2)*Sum_{p <= n} (mu(p)*d(p)*sigma(p)*phi(p)) + sum_{p <= n} p^2. - _Wesley Ivan Hurt_, Jan 04 2013

%F a(1) = 0 and then, for all k >= 1, repeat k A001223(k) times. - _Jean-Christophe Hervé_, Oct 29 2013

%F a(n) = n/(log(n) - 1 - Sum_{k=1..m} A233824(k)/log(n)^k + O(1/log(n)^{m+1})) for m > 0. - _Jonathan Sondow_, Dec 19 2013

%F a(n) = A001221(A003418(n)). - _Eric Desbiaux_, May 01 2014

%F a(n) = Sum_{j=2..n} H(-sin^2 (Pi*(Gamma(j)+1)/j)) where H(x) is the Heaviside step function, taking H(0)=1. - _Keshav Raghavan_, Jun 18 2016

%F a(A014076(n)) = (1/2) * (A014076(n) + 1) - n + 1. - _Christopher Heiling_, Mar 03 2017

%F From _Steven Foster Clark_, Sep 25 2018: (Start)

%F a(n) = Sum_{m=1..n} A143519(m) * floor(n/m).

%F a(n) = Sum_{m=1..n} A001221(m) * A002321(floor(n/m)) where A002321() is the Mertens function.

%F a(n) = Sum_{m=1..n} |A143519(m)| * A002819(floor(n/m)) where A002819() is the Liouville Lambda summatory function and |x| is the absolute value of x.

%F a(n) = Sum_{m=1..n} A137851(m)/m * H(floor(n/m)) where H(n) = Sum_{m=1..n} 1/m is the harmonic number function.

%F a(n) = Sum_{m=1..log_2(n)} A008683(m) * A025528(floor(n^(1/m))) where A008683() is the Moebius mu function and A025528() is the prime-power counting function.

%F (End)

%F Sum_{k=2..n} 1/a(k) ~ (1/2) * log(n)^2 + O(log(n)) (de Koninck and Ivić, 1980). - _Amiram Eldar_, Mar 08 2021

%F a(n) ~ 1/(n^(1/n)-1). - _Thomas Ordowski_, Jan 30 2023

%e There are 3 primes <= 6, namely 2, 3 and 5, so pi(6) = 3.

%p with(numtheory); A000720 := pi; [ seq(A000720(i),i=1..50) ];

%t A000720[n_] := PrimePi[n]; Table[ A000720[n], {n, 1, 100} ]

%t Array[ PrimePi[ # ]&, 100 ]

%t Accumulate[Table[Boole[PrimeQ[n]],{n,100}]] (* _Harvey P. Dale_, Jan 17 2015 *)

%o (PARI) A000720=vector(100,n,omega(n!)) \\ For illustration only; better use A000720=primepi

%o (PARI) vector(300,j,primepi(j)) \\ _Joerg Arndt_, May 09 2008

%o (Sage) [prime_pi(n) for n in range(1, 79)]  # _Zerinvary Lajos_, Jun 06 2009

%o (Magma) [ #PrimesUpTo(n): n in [1..200] ];  // _Bruno Berselli_, Jul 06 2011

%o (Haskell)

%o a000720 n = a000720_list !! (n-1)

%o a000720_list = scanl1 (+) a010051_list  -- _Reinhard Zumkeller_, Sep 15 2011

%o (Python)

%o from sympy import primepi

%o for n in range(1,100): print(primepi(n), end=', ') # _Stefano Spezia_, Nov 30 2018

%Y Cf. A048989, A000040, A132090, A137588, A139328, A104272, A143223, A143224, A143225, A143226, A143227.

%Y Cf. A143538, A036234, A033844, A034387, A034386, A179215, A010051, A212210-A212213, A233824, A056171, A304483.

%Y Closely related:

%Y A099802: Number of primes <= 2n.

%Y A060715: Number of primes between n and 2n (exclusive).

%Y A035250: Number of primes between n and 2n (inclusive).

%Y A038107: Number of primes < n^2.

%Y A014085: Number of primes between n^2 and (n+1)^2.

%Y A007053: Number of primes <= 2^n.

%Y A036378: Number of primes p between powers of 2, 2^n < p <= 2^(n+1).

%Y A006880: Number of primes < 10^n.

%Y A006879: Number of primes with n digits.

%Y A033270: Number of odd primes <= n.

%Y A065855: Number of composites <= n.

%Y For lists of large values of a(n) see, e.g., A005669(n) = a(A002386(n)), A214935(n) = a(A205827(n)).

%Y Related sequences:

%Y Primes (p) and composites (c): A000040, A002808, A065855.

%Y Primes between p(n) and 2*p(n): A063124, A070046; between c(n) and 2*c(n): A376761; between n and 2*n: A035250, A060715, A077463, A108954.

%Y Composites between p(n) and 2*p(n): A246514; between c(n) and 2*c(n): A376760; between n and 2*n: A075084, A307912, A307989, A376759.

%K nonn,core,easy,nice

%O 1,3

%A _N. J. A. Sloane_

%E Additional links contributed by _Lekraj Beedassy_, Dec 23 2003

%E Edited by _M. F. Hasler_, Apr 27 2018 and (links recovered) Dec 21 2018