A000720 - OEIS (original) (raw)

A000720

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

1977

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

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

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

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

Daniel Forgues, Table of n, pi(n) for n = 1..100000 (first 20000 terms from N. J. A. Sloane; see below for links with 823852 terms (Verma) and more (Caldwell))

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].

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

Encyclopedia Britannica, The Prime Number Theorem [web.archive.org's copy of a no longer available personal copy of the Encyclopedia's article]

John Lorch, The Distribution of Primes, B.S. Undergraduate Mathematics Exchange, Vol. 3, No. 1 (Fall 2005).

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} A001221(m) * A002321(floor(n/m)) where A002321() is the Mertens function.

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.

MATHEMATICA

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

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

(Sage) [prime_pi(n) for n in range(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

(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.

Closely related:

A099802: Number of primes <= 2n.

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

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

A038107: Number of primes < n^2.

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

A007053: Number of primes <= 2^n.

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

A006880: Number of primes < 10^n.

A006879: Number of primes with n digits.

A033270: Number of odd primes <= n.

A065855: Number of composites <= n.

Related sequences:

EXTENSIONS

Edited by M. F. Hasler, Apr 27 2018 and (links recovered) Dec 21 2018