A035250 - OEIS

%I #55 Jan 03 2025 02:20:09

%S 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,

%T 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,

%U 13,13,12,12,13,13,14,14,13,14,15,15,14,14,13,14,15

%N Number of primes between n and 2n (inclusive).

%C 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.

%C 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

%C The smallest and largest primes between n and 2n inclusive are A007918 and A060308 respectively. - _Lekraj Beedassy_, Jan 01 2007

%C The number of partitions of 2n into exactly two parts with first part prime, n > 1. - _Wesley Ivan Hurt_, Jun 15 2013

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

%H N. J. A. Sloane, <a href="/A035250/b035250.txt">Table of n, a(n) for n = 1..20000</a> (first 1000 terms from T. D. Noe)

%H International Mathematics Olympiad, <a href="https://web.archive.org/web/20170407203826/http://www.mathsolympiad.org.nz/wp-content/uploads/2009/01/bertrands-theorem.pdf">Proof of Bertrand's Postulate</a> [Via Wayback Machine]

%F a(n) = A000720(2*n) - A000720(n-1); a(n) <= A179211(n). - _Reinhard Zumkeller_, Jul 05 2010

%F a(A059316(n)) = n and a(m) <> n for m < A059316(n). - _Reinhard Zumkeller_, Jan 08 2012

%F a(n) = sum(A010051(k): k=n..2*n). [_Reinhard Zumkeller_, Jan 08 2012]

%F a(n) = pi(2n) - pi(n-1). [_Wesley Ivan Hurt_, Jun 15 2013]

%e The primes between n = 13 and 2n = 26, inclusive, are 13, 17, 19, 23; so a(13) = 4.

%e 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.

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

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

%o (Haskell)

%o a035250 n = sum $ map a010051 [n..2*n] -- _Reinhard Zumkeller_, Jan 08 2012

%o (Magma) [#PrimesInInterval(n, 2*n): n in [1..80]]; // _Bruno Berselli_, Sep 05 2012

%o (PARI) a(n)=primepi(2*n)-primepi(n-1) \\ _Charles R Greathouse IV_, Jul 01 2013

%Y Cf. A073837, A073838, A099802, A060715.

%Y Related sequences:

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

%Y 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.

%Y 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.

%K nonn

%O 1,2

%A _Erich Friedman_