cp's OEIS Frontend

A050216 Number of primes between (prime(n))^2 and (prime(n+1))^2, with a(0) = 2 by convention.

%I A050216 #197 Aug 15 2025 10:28:35
%S A050216 2,2,5,6,15,9,22,11,27,47,16,57,44,20,46,80,78,32,90,66,30,106,75,114,
%T A050216 163,89,42,87,42,100,354,99,165,49,299,58,182,186,128,198,195,76,356,
%U A050216 77,144,75,463,479,168,82,166,270,90,438,275,274,292,91,292,199,99
%N A050216 Number of primes between (prime(n))^2 and (prime(n+1))^2, with a(0) = 2 by convention.
%C A050216 The function in Brocard's Conjecture, which states that for n >= 2, a(n) >= 4.
%C A050216 The lines in the graph correspond to prime gaps of 2, 4, 6, ... . - _T. D. Noe_, Feb 04 2008
%C A050216 Lengths of blocks of consecutive primes in A000430 (union of primes and squares of primes). - _Reinhard Zumkeller_, Sep 23 2011
%C A050216 In the n-th step of the sieve of Eratosthenes, all multiples of prime(n) are removed. Then a(n) gives the number of new primes obtained after the n-th step. - _Jean-Christophe Hervé_, Oct 27 2013
%C A050216 More precisely, after the n-th step, one is sure to have eliminated all composites less than prime(n+1)^2, since any composite N has a prime factor <= sqrt(N). It is in exactly this (restricted) sense that a(n) yields the number of "new primes" (additional numbers known to be prime) after the n-th step. But one knows after the n-th step also that all remaining numbers between prime(n+1)^2 and prime(n+1)*(prime(n+1)+2) are prime: By construction they don't have a factor less than prime(n+1) and they don't have a factor prime(n+1) so the least prime factor could be prime(n+2) >= prime(n+1)+2. For example, after eliminating multiples of 3 in the 2nd step, one has (2, 3, 5, 7, 11, 13, 17, 23, 25, 29, 31, 35, ...) and one knows that all remaining numbers strictly in between 5^2=25 and 5*(5+2)=35 are prime, too. - _M. F. Hasler_, Dec 31 2014
%C A050216 Numerically, the slope of the lowest "ray" m(n) = min {a(k); k>n}, seems to converge to a value somewhere in the range 1.75 < m(n)/n < 1.8; with m(n)/n > 1.7 for n > 900, m(n)/n > 1.75 for n > 2700. - _M. F. Hasler_, Dec 31 2014
%C A050216 Legendre's conjecture (see A014085) would imply that a(n) >= 2 for all n and that sequences A054272, A250473 and A250474 were thus strictly increasing (see the Wikipedia article about Brocard's conjecture). - _Antti Karttunen_, Jan 01 2015
%C A050216 a(n) >= 4 up to at least n = 4*10^5. - _Eric W. Weisstein_, Jan 13 2025
%D A050216 Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 183.
%H A050216 T. D. Noe, <a href="/A050216/b050216.txt">Table of n, a(n) for n = 0..10000</a>
%H A050216 Joel E. Cohen, <a href="https://arxiv.org/abs/2508.08335">Conjectures about Primes and Cyclic Numbers</a>, arXiv:2508.08335 [math.NT], 2025. See p. 16.
%H A050216 Anthony G. Shannon and Jean V. Leyendekkers, <a href="http://nntdm.net/volume-23-2017/number-2/117-125/">On Legendre's Conjecture</a>, Notes on Number Theory and Discrete Mathematics, Vol. 23, No. 2 (2017): 117-125.
%H A050216 Nicolas Vaillant, <a href="/A050216/a050216_9.png">Graph of A050216(n) / (n * A001223(n))</a>
%H A050216 Nicolas Vaillant, <a href="/A050216/a050216_10.png">Average density of primes between prime(n)^2 and prime(n+1)^2</a>
%H A050216 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/BrocardsConjecture.html">Brocard's Conjecture</a>.
%H A050216 Wikipedia, <a href="http://en.wikipedia.org/wiki/Brocard%27s_conjecture">Brocard's Conjecture</a>
%F A050216 For all n >= 1, a(n) = A256468(n) + A256469(n). - _Antti Karttunen_, Mar 30 2015
%F A050216 Limit_{N->oo} (Sum_{n=1..N} a(n)) / (Sum_{n=1..N} prime(n)) = 1. - _Alain Rocchelli_, Sep 30 2023
%e A050216 There are 2 primes less than 2^2, there are 2 primes between 2^2 and 3^2, 5 primes between 3^2 and 5^2, etc. [corrected by Jonathan Sperry, Aug 30 2013]
%p A050216 A050216 := proc(n)
%p A050216     local p,pn ;
%p A050216     if n = 0 then
%p A050216         2;
%p A050216     else
%p A050216         p := ithprime(n) ;
%p A050216         pn := nextprime(p) ;
%p A050216         numtheory[pi](pn^2)-numtheory[pi](p^2) ;
%p A050216     end if;
%p A050216 end proc:
%p A050216 seq(A050216(n),n=0..40) ; # _R. J. Mathar_, Jan 27 2025
%t A050216 -Subtract @@@ Partition[PrimePi[Prime[Range[20]]^2], 2, 1] (* _Eric W. Weisstein_, Jan 10 2025 *)
%o A050216 (Haskell)
%o A050216 import Data.List (group)
%o A050216 a050216 n = a050216_list !! (n-1)
%o A050216 a050216_list =
%o A050216    map length $ filter (/= [0]) $ group $ map a010051 a000430_list
%o A050216 -- _Reinhard Zumkeller_, Sep 23 2011
%o A050216 (PARI) a(n)={n||return(2);primepi(prime(n+1)^2)-primepi(prime(n)^2)} \\ _M. F. Hasler_, Dec 31 2014
%Y A050216 First differences of A000879.
%Y A050216 One more than A251723.
%Y A050216 Cf. A010051, A001248, A014085, A089609, A251719, A256468, A256469, A256470, A029707, A137859.
%Y A050216 Cf. A380135 (High water marks for number of primes between prime(n)^2 and prime(n+1)^2).
%Y A050216 Cf. A380136 (Positions of the high water marks for number of primes between prime(n)^2 and prime(n+1)^2).
%K A050216 nonn,look
%O A050216 0,1
%A A050216 _Eric W. Weisstein_
%E A050216 Edited by _N. J. A. Sloane_, Nov 15 2009