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

1, 2, 2, 2, 2, 2, 3, 2, 3, 4, 4, 4, 4, 3, 4, 5, 5, 4, 5, 4, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 7, 7, 8, 8, 9, 10, 9, 9, 10, 10, 10, 10, 9, 10, 10, 10, 9, 10, 10, 11, 12, 12, 12, 13, 13, 14, 14, 14, 13, 13, 12, 12, 13, 13, 14, 14, 13, 14, 15, 15, 14, 14, 13, 14, 15

Offset: 1

Author

Erich Friedman

Keywords

• nonn

Comments

By Bertrand's Postulate (proved by Chebyshev), there is always a prime between n and 2n, i.e., a(n) is positive for all n.

The number of primes in the interval [n,2*n) is the same sequence as this, except that a(1) = 0. - N. J. A. Sloane, Oct 18 2024

The smallest and largest primes between n and 2n inclusive are A007918 and A060308 respectively. - Lekraj Beedassy, Jan 01 2007

The number of partitions of 2n into exactly two parts with first part prime, n > 1. - Wesley Ivan Hurt, Jun 15 2013

Examples

			The primes between n = 13 and 2n = 26, inclusive, are 13, 17, 19, 23; so a(13) = 4.
a(5) = 2, since 2(5) = 10 has 5 partitions into exactly two parts: (9,1),(8,2),(7,3),(6,4),(5,5).  Two primes are among the first parts: 7 and 5.
		

References

• Aigner, M. and Ziegler, G. Proofs from The Book (2nd edition). Springer-Verlag, 2001.

Links

• N. J. A. Sloane, Table of n, a(n) for n = 1..20000 (first 1000 terms from T. D. Noe)
• International Mathematics Olympiad, Proof of Bertrand's Postulate [Via Wayback Machine]

Crossrefs

Cf. A073837, A073838, A099802, A060715.

Related sequences:

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

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.

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.

Programs

Haskell

a035250 n = sum $ map a010051 [n..2*n] -- Reinhard Zumkeller, Jan 08 2012

Magma

[#PrimesInInterval(n, 2*n): n in [1..80]]; // Bruno Berselli, Sep 05 2012

Maple

with(numtheory): A035250:=n->pi(2*n)-pi(n-1): seq(A035250(n), n=1..100); # Wesley Ivan Hurt, Aug 09 2014

Mathematica

f[n_] := PrimePi[2n] - PrimePi[n - 1]; Array[f, 76] (* Robert G. Wilson v, Dec 23 2012 *)

PARI

a(n)=primepi(2*n)-primepi(n-1) \\ Charles R Greathouse IV, Jul 01 2013

Formula

a(n) = A000720(2*n) - A000720(n-1); a(n) <= A179211(n). - Reinhard Zumkeller, Jul 05 2010

a(A059316(n)) = n and a(m) <> n for m < A059316(n). - Reinhard Zumkeller, Jan 08 2012

a(n) = sum(A010051(k): k=n..2*n). [Reinhard Zumkeller, Jan 08 2012]

a(n) = pi(2n) - pi(n-1). [Wesley Ivan Hurt, Jun 15 2013]