login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000720 pi(n), the number of primes <= n. Sometimes called PrimePi(n) to distinguish it from the number 3.14159...
(Formerly M0256 N0090)
699
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, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 21, 21, 21, 21, 21, 21 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Partial sums of A010051 (characteristic function of primes). - Jeremy Gardiner, Aug 13 2002

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

The g.f. -z*(-1-z-z^3-z^5+z^6+z^7)/((1+z)*(z^2-z+1)*(z^2+z+1)*(z-1)^2) conjectured by Simon Plouffe in his 1992 dissertation is wrong.

See the additional references and links mentioned in A143227. - Jonathan Sondow, Aug 03 2008

Equals row sums of triangle A143538. - Gary W. Adamson, Aug 23 2008

a(n) = A036234(n)-1. - Jaroslav Krizek, Mar 23 2009

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(A005867(i)/A002110(i), i=0..T(sqrt(N))). - Ben Paul Thurston, Aug 23 2010

a(n) ~ A003418(n)/A217863(n). - Eric Desbiaux, Nov 25 2012

a(n) = A001221(A003418(n)). - Eric Desbiaux, Mar 11 2013

Number of partitions of 2n into exactly two parts with the smallest part prime. - Wesley Ivan Hurt, Jul 20 2013

REFERENCES

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.

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 8.

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

Bressoud & Wagon, A Course in Computational Number Theory, Springer/Key, 2000 (with a Mathematica package for computational number theory); wagon_notes.nb: http://www.msri.org/publications/ln/msri/2000/introant/wagon/mma/wagon_notes.nb

R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 5.

Pierre Dusart, Autour de la fonction qui compte le nombre de nombres premiers, Dissertation, Universite de Limoges (1998).

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

G. J. O. Jameson, The Prime Number Theorem, Camb. Univ. Press, 2003

D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section VII.1. (For inequalities, etc.)

W. Narkiewicz, The Development of Prime Number Theory, Springer-Verlag 2000.

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

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

G. Tenebaum and M. Mendes France, Prime Numbers and Their Distribution, AMS Providence RI 1999

LINKS

N. J. A. Sloane and Daniel Forgues, Table of n, pi(n) for n = 1..100000 (first 20000 terms from N. J. A. Sloane)

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

C. Axler, Über die Primzahl-Zählfunktion, die n-te Primzahl und verallgemeinerte Ramanujan-Primzahlen, Ph.D. thesis 2013, in German, English summary.

P. T. Bateman & H. G. Diamond, A Hundred Years of Prime Numbers, Amer. Math. Month., Vol. 103 (9), Nov. 1996, pp. 729-741, MAA Washington DC.

S. Bennett, The role of Riemann's zeta function in the analytic proof of the Prime Number Theorem

C. Bonanno & M. S. Mega, Toward a dynamic model for prime numbers

D. M. Bressoud, Review of "The Prime Number Theorem" by G. J. O. Jameson

B. Brubaker, The Prime Number Theorem

C. K. Caldwell, The Prime Glossary, Prime number theorem

C. K. Caldwell, How Many Primes Are There

W. W. L. Chen, Distribution of Prime Numbers

M. Deleglise, Computation of large values of pi(x)

Pierre Dusart, The k-th prime is greater than k(ln k + ln ln k-1) for k>=2, Mathematics of Computation 68: (1999), 411-415.

Encyclopedia Britannica, The Prime Number Theorem

R. Gray and J. D. Mitchell, Largest subsemigroups of the full transformation monoid, Discrete Math., 308 (2008), 4801-4810.

G. H. Hardy & J. E. Littlewood, Contributions To The Theory Of The Riemann Zeta-Function And The Theory Of The Distribution Of Primes

M. Hassani, Approximation of pi(x) by Psi(x), J. Inequ. Pure Appl. Math. 7 (2006) vol. 1, #7

Y.-C. Kim, Note on the Prime Number Theorem

T. V. Kolev, On the number of Prime Numbers less than a Given Quantity

A. V. Kumchev, The Distribution of Prime Numbers

J. C. Lagarias, V. S. Miller and A. M. Odlyzko, Computing pi(x): The Meissel-Lehmer method, Math. Comp., 44 (1985), pp. 537-560.

J. C. Lagarias and A. M. Odlyzko, Computing pi(x): An analytic method, J. Algorithms, 8 (1987), pp. 173-191.

D. J. Lorch, The Distribution of Primes

N. McKenzie, Computing the Prime Counting Function with Linnik's Identity ....

M. B. Paksoy, Derived Ramanujan primes: R'_n, arXiv 2012.

B. E. Petersen, Prime Number Theorem(version 1996)

B. E. Petersen, Prime Number Theorem(version 20020514)

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

Omar E. Pol, Determinacion geometrica de los numeros primos y perfectos

Omar E. Pol, Illustration of initial terms: Divisors and pi(x)

B. Riemann, On the Number of Prime Numbers 1859, last page (various transcripts)

J. Barkley Rosser, Explicit Bounds for Some Functions of Prime Numbers, American Journal of Mathematics 63 (1941) 211-232.

J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Ill. Journ. Math. 6 (1962) 64-94.

J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers (scan of some key pages from an ancient annotated photocopy)

S. M. Ruiz and J. Sondow, Formulas for pi(n) and the n-th prime

A. M. Selvam, Quantum-like Chaos in Prime Number Distribution and in Turbulent Fluid Flows

A. M. Selvam, Quantum-like Chaos in Prime NumberDistribution and in Turbulent Fluid Flows

Jeffrey Shallit, Bibliography on calculation of pi(x)

J. Sondow, Ramanujan primes and Bertrand's postulate, Amer. Math. Monthly, 116 (2009), 630-635.

W. R. Watkins, The distribution of Prime Numbers

M. R. Watkins, the prime number theorem (some references)

Eric Weisstein's World of Mathematics, Prime Counting Function

Wikipedia, Prime number theorem

Wikipedia, Prime-counting function

M. Wolf, 'Applications of Statistical Mechanics in Prime Number Theory'

Wolfram Research, First 50 values of pi(n)

D. J. Wright, Distribution of primes

Index entries for "core" sequences

FORMULA

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

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]

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]

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

For n>1: A138194(n) <= a(n) <= A138195(n) (Tschebyscheff, 1850). - Reinhard Zumkeller, Mar 04 2008

For n>=3, 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

a(n) = A001221(A000142(n)). - Benoit Cloitre, Jun 03 2005

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

A recursive definition of PrimePi using the LegendrePhi function given in the Wagon_notes.nb: Pi(n) = Pi(Sqrt(n)) + Phi(n, Pi(Sqrt(n) ) - 1, with Pi(0)=0, Pi(1)=0. - Roger L. Bagula, Mar 26 2008

From Enrique Pérez Herrero, Jul 12 2010: (Start)

a(n) = sum_{i=2..n} floor((i+1)/A000203(i)).

a(n) = sum_{i=2..n} floor(A000010(n)/(i-1)).

a(n) = sum_{i=2..n} floor(2/A000005(n)). (End)

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

a(n) = -sum_{p <= n} mu(p). - Wesley Ivan Hurt, Jan 04 2013

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

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

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

EXAMPLE

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

MAPLE

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

MATHEMATICA

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

Array[ PrimePi[ # ]&, 100 ]

PROG

(PARI) A000720=vector(100, n, omega(n!));

(PARI) vector(300, j, primepi(j)) \\ Joerg Arndt, May 09 2008

(Sage) [prime_pi(n) for n in xrange(1, 79)] # Zerinvary Lajos, Jun 06 2009

(MAGMA) [ #PrimesUpTo(n): n in [1..200] ];  // Bruno Berselli, Jul 06 2011

(Haskell)

a000720 n = a000720_list !! (n-1)

a000720_list = scanl1 (+) a010051_list

-- Reinhard Zumkeller, Sep 15 2011

(PARI) A000720(n) = matsize(factor(n!))[1] \\ Colin Barker, Mar 11 2013

CROSSREFS

Cf. A048989, A000040, A132090, A137588, A099802, A139328, A014085, A060715, A104272, A143223, A143224, A143225, A143226, A143227.

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

Cf. A060715 Number of primes between n and 2n (exclusive).

Cf. A035250 Number of primes between n and 2n (inclusive).

Cf. A038107 Number of primes < n^2.

Cf. A014085 Number of primes between n^2 and (n+1)^2.

Cf. A007053 Number of primes <= 2^n.

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

Cf. A006880 Number of primes < 10^n.

Cf. A006879 Number of primes with n digits.

Sequence in context: A082447 A139789 * A230980 A070549 A074796 A061070

Adjacent sequences:  A000717 A000718 A000719 * A000721 A000722 A000723

KEYWORD

nonn,core,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Additional links contributed by Lekraj Beedassy, Dec 23 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 19 05:22 EDT 2014. Contains 240738 sequences.