%I #107 Sep 27 2023 13:42:33
%S 0,2,2,2,3,2,4,3,4,3,5,4,5,5,4,6,7,5,6,6,7,7,7,6,9,8,7,8,9,8,8,10,9,
%T 10,9,10,9,9,12,11,12,11,9,12,11,13,10,13,15,10,11,15,16,12,13,11,12,
%U 17,13,16,16,13,17,15,14,16,15,15,17,13,21,15,15,17,17,18,22,14,18,23,13
%N Number of primes between n^2 and (n+1)^2.
%C Suggested by Legendre's conjecture (still open) that for n > 0 there is always a prime between n^2 and (n+1)^2.
%C a(n) is the number of occurrences of n in A000006. - _Philippe Deléham_, Dec 17 2003
%C See the additional references and links mentioned in A143227. - _Jonathan Sondow_, Aug 03 2008
%C Legendre's conjecture may be written pi((n+1)^2) - pi(n^2) > 0 for all positive n, where pi(n) = A000720(n), [the prime counting function]. - _Jonathan Vos Post_, Jul 30 2008 [Comment corrected by _Jonathan Sondow_, Aug 15 2008]
%C Legendre's conjecture can be generalized as follows: for all integers n > 0 and all real numbers k > K, there is a prime in the range n^k to (n+1)^k. The constant K is conjectured to be log(127)/log(16). See A143935. - _T. D. Noe_, Sep 05 2008
%C For n > 0: number of occurrences of n^2 in A145445. - _Reinhard Zumkeller_, Jul 25 2014
%D J. R. Goldman, The Queen of Mathematics, 1998, p. 82.
%H T. D. Noe, <a href="/A014085/b014085.txt">Table of n, a(n) for n = 0..10000</a>
%H Pierre Dusart, <a href="http://dx.doi.org/10.1090/S0025-5718-99-01037-6">The k-th prime is greater than k(ln k + ln ln k-1) for k>=2</a>, Mathematics of Computation 68: (1999), 411-415.
%H Tsutomu Hashimoto, <a href="http://arxiv.org/abs/0807.3690">On a certain relation between Legendre's conjecture and Bertrand's postulate</a>, arXiv:0807.3690 [math.GM], 2008.
%H M. Hassani, <a href="https://arxiv.org/abs/math/0607096">Counting primes in the interval (n^2, (n+1)^2)</a>, arXiv:math/0607096 [math.NT], 2006.
%H Edmund Landau, <a href="https://web.archive.org/web/20131227061130/http://www.mathunion.org/ICM/ICM1912.1/Main/icm1912.1.0093.0108.ocr.pdf">Gelöste und ungelöste Probleme aus der Theorie der Primzahlverteilung und der Riemannschen Zetafunktion.</a> Jahresbericht der Deutschen Mathematiker-Vereinigung (1912), Vol. 21, page 208-228.
%H Peter Munn, <a href="https://oeis.org/plot2a?name1=A005843&name2=A014085&tform1=log+base+10&tform2=log+base+10&shift=0&radiop1=xy&drawpoints=true">Logarithmic plot: number of primes between consecutive squares vs number of integers between the same squares</a>
%H Michael Penn, <a href="https://www.youtube.com/watch?v=j5qy-Or-1KM">Legendre's Conjecture is probably true, and here's why</a>, YouTube video, 2023.
%H Hugo Pfoertner, <a href="https://oeis.org/plot2a?name1=A349997&name2=A349999&tform1=untransformed&tform2=untransformed&shift=0&radiop1=xy&drawlines=true">Lower limit of the scatter band represented as a step function</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LegendresConjecture.html">Legendre's Conjecture</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Legendre%27s_conjecture">Legendre's conjecture</a>
%F a(n) = A000720((n+1)^2) - A000720(n^2). - _Jonathan Vos Post_, Jul 30 2008
%F a(n) = Sum_{k = n^2..(n+1)^2} A010051(k). - _Reinhard Zumkeller_, Mar 18 2012
%F Conjecture: for all n>1, abs(a(n)-(n/log(n))) < sqrt(n). - _Alain Rocchelli_, Sep 20 2023
%e a(17) = 5 because between 17^2 and 18^2, i.e., 289 and 324, there are 5 primes (which are 293, 307, 311, 313, 317).
%t Table[PrimePi[(n + 1)^2] - PrimePi[n^2], {n, 0, 80}] (* _Lei Zhou_, Dec 01 2005 *)
%t Differences[PrimePi[Range[0,90]^2]] (* _Harvey P. Dale_, Nov 25 2015 *)
%o (PARI) a(n)=primepi((n+1)^2)-primepi(n^2) \\ _Charles R Greathouse IV_, Jun 15 2011
%o (Haskell)
%o a014085 n = sum $ map a010051 [n^2..(n+1)^2]
%o -- _Reinhard Zumkeller_, Mar 18 2012
%o (Python)
%o from sympy import primepi
%o def a(n): return primepi((n+1)**2) - primepi(n**2)
%o print([a(n) for n in range(81)]) # _Michael S. Branicky_, Jul 05 2021
%Y First differences of A038107.
%Y Cf. A000006, A053000, A053001, A007491, A077766, A077767, A108954, A000720, A060715, A104272, A143223, A143224, A143225, A143226, A143227.
%Y Cf. A010051, A061265, A221056, A000290, A145445.
%Y Counts of primes between consecutive higher powers: A060199, A061235, A062517.
%Y Cf. A333846, A349996, A349997, A349998, A349999.
%K nonn,nice
%O 0,2
%A _Jon Wild_, Jul 14 1997