login
Number of primes between n^2 and (n+1)^2.
114

%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&amp;name2=A014085&amp;tform1=log+base+10&amp;tform2=log+base+10&amp;shift=0&amp;radiop1=xy&amp;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&amp;name2=A349999&amp;tform1=untransformed&amp;tform2=untransformed&amp;shift=0&amp;radiop1=xy&amp;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