|
| |
|
|
A000720
|
|
pi(n), the number of primes <= n. Sometimes called PrimePi(n) to distinguish it from the number 3.14159...
(Formerly M0256 N0090)
|
|
590
|
|
|
|
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 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
|
|
|
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.
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.
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).
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.
R. Gray and J. D. Mitchell, Largest subsemigroups of the full transformation monoid, Discrete Math., 308 (2008), 4801-4810.
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
N. McKenzie, Computing the Prime Counting Function with Linnik's Identity ..., http://www.icecreambreakfast.com/primecount/primecounting.php.
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.
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.
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].
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)
Encyclopedia Britannica, The Prime Number Theorem
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
B. E. Petersen, Prime Number Theorem(version 1996)
B. E. Petersen, Prime Number Theorem(version 20020514)
_Simon Plouffe_, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
_Simon Plouffe_, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
O. E. Pol, Determinacion geometrica de los numeros primos y perfectos
O. 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 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)
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. - Frank 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
Contribution from Enrique Perez 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
|
|
|
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 (zerinvarylajos(AT)yahoo.com), 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, A006880, A000040, A132090, A137588, A038107, A099802, A139328, A014085, A060715, A104272, A143223, A143224, A143225, A143226, A143227.
Cf. A143538.
Cf. A036234.
Cf. A035250, A034387, A034386, A099802, A179215.
Cf. A010051, A212210-A212213.
Sequence in context: A179390 A082447 A139789 * 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
|
| |
|
|
