|
|
A000720
|
|
pi(n), the number of primes <= n. Sometimes called PrimePi(n) to distinguish it from the number 3.14159...
(Formerly M0256 N0090)
|
|
1793
|
|
|
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
|
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
Number of partitions of 2n into exactly two parts with the smallest part prime. - Wesley Ivan Hurt, Jul 20 2013
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
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
|
|
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.
Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, p. 8.
Raymond Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963; p. 129.
Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 5.
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. [See also the review by D. M. Bressoud (link below).]
Władysław Narkiewicz, The Development of Prime Number Theory, Springer-Verlag, 2000.
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.).
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).
Gerald Tenenbaum and Michel Mendès France, Prime Numbers and Their Distribution, AMS Providence RI, 1999.
V. Udrescu, Some remarks concerning the conjecture pi(x + y) <= pi(x) + pi(y). Math. Pures Appl. 20 (1975), 1201-1208.
|
|
LINKS
|
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].
Encyclopedia Britannica, The Prime Number Theorem [web.archive.org's copy of a no longer available personal copy of the Encyclopedia's article]
|
|
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 >= 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
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) = (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(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
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
a(n) = Sum_{m=1..n} A143519(m) * floor(n/m).
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.
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.
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.
(End)
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
|
|
EXAMPLE
|
There are 3 primes <= 6, namely 2, 3 and 5, so pi(6) = 3.
|
|
MAPLE
|
|
|
MATHEMATICA
|
Array[ PrimePi[ # ]&, 100 ]
Accumulate[Table[Boole[PrimeQ[n]], {n, 100}]] (* Harvey P. Dale, Jan 17 2015 *)
|
|
PROG
|
(PARI) A000720=vector(100, n, omega(n!)) \\ For illustration only; better use A000720=primepi
(PARI) vector(300, j, primepi(j)) \\ Joerg Arndt, May 09 2008
(Magma) [ #PrimesUpTo(n): n in [1..200] ]; // Bruno Berselli, Jul 06 2011
(Haskell)
a000720 n = a000720_list !! (n-1)
(Python)
from sympy import primepi
for n in range(1, 100): print(primepi(n), end=', ') # Stefano Spezia, Nov 30 2018
|
|
CROSSREFS
|
Cf. A048989, A000040, A132090, A137588, A139328, A104272, A143223, A143224, A143225, A143226, A143227.
Cf. A143538, A036234, A033844, A034387, A034386, A179215, A010051, A212210-A212213, A233824, A056171, A304483.
Cf. A099802: Number of primes <= 2n.
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.
Cf. A033270: Number of odd primes <= n.
|
|
KEYWORD
|
nonn,core,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Edited by M. F. Hasler, Apr 27 2018 and (links recovered) Dec 21 2018
|
|
STATUS
|
approved
|
|
|
|