cp's OEIS Frontend

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

%I A014085 #134 Aug 15 2025 10:28:32
%S A014085 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 A014085 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 A014085 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 A014085 Number of primes between n^2 and (n+1)^2.
%C A014085 Suggested by Legendre's conjecture (still open) that for n > 0 there is always a prime between n^2 and (n+1)^2.
%C A014085 a(n) is the number of occurrences of n in A000006. - _Philippe Deléham_, Dec 17 2003
%C A014085 See the additional references and links mentioned in A143227. - _Jonathan Sondow_, Aug 03 2008
%C A014085 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 A014085 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 A014085 For n > 0: number of occurrences of n^2 in A145445. - _Reinhard Zumkeller_, Jul 25 2014
%D A014085 J. R. Goldman, The Queen of Mathematics, 1998, p. 82.
%H A014085 T. D. Noe, <a href="/A014085/b014085.txt">Table of n, a(n) for n = 0..10000</a>
%H A014085 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. 8.
%H A014085 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 A014085 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 A014085 Mehdi 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 A014085 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 A014085 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 A014085 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 A014085 Hugo Pfoertner, <a href="https://www.randomwalk.de/sequences/b014085.txt">One million terms in b-file format</a>, 13.1 MB (2024).
%H A014085 Hugo Pfoertner, <a href="https://www.randomwalk.de/sequences/b014085.pdf">Plot of 10^6 sequence terms with conjectured scatter band</a>, large pdf (13.6 MB) (2024).
%H A014085 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 A014085 Jonathan Sorenson and Jonathan Webster, <a href="https://doi.org/10.1007/s40993-024-00589-4">An algorithm to verify Legendre’s conjecture up to 7*10^13</a>, Research in Number Theory 11:4 (2025).
%H A014085 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LegendresConjecture.html">Legendre's Conjecture</a>
%H A014085 Wikipedia, <a href="http://en.wikipedia.org/wiki/Legendre%27s_conjecture">Legendre's conjecture</a>
%F A014085 a(n) = A000720((n+1)^2) - A000720(n^2). - _Jonathan Vos Post_, Jul 30 2008
%F A014085 a(n) = Sum_{k = n^2..(n+1)^2} A010051(k). - _Reinhard Zumkeller_, Mar 18 2012
%F A014085 Conjecture: for all n>1, abs(a(n)-(n/log(n))) < sqrt(n). - _Alain Rocchelli_, Sep 20 2023
%F A014085 Up to n=10^6 there are no counterexamples to this conjecture. - _Hugo Pfoertner_, Dec 16 2024
%F A014085 Sorenson & Webster show that a(n) > 0 for all 0 < n < 7.05 * 10^13. - _Charles R Greathouse IV_, Jan 31 2025
%e A014085 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 A014085 Table[PrimePi[(n + 1)^2] - PrimePi[n^2], {n, 0, 80}] (* _Lei Zhou_, Dec 01 2005 *)
%t A014085 Differences[PrimePi[Range[0,90]^2]] (* _Harvey P. Dale_, Nov 25 2015 *)
%o A014085 (PARI) a(n)=primepi((n+1)^2)-primepi(n^2) \\ _Charles R Greathouse IV_, Jun 15 2011
%o A014085 (Haskell)
%o A014085 a014085 n = sum $ map a010051 [n^2..(n+1)^2]
%o A014085 -- _Reinhard Zumkeller_, Mar 18 2012
%o A014085 (Python)
%o A014085 from sympy import primepi
%o A014085 def a(n): return primepi((n+1)**2) - primepi(n**2)
%o A014085 print([a(n) for n in range(81)]) # _Michael S. Branicky_, Jul 05 2021
%Y A014085 First differences of A038107.
%Y A014085 Cf. A000006, A053000, A053001, A007491, A077766, A077767, A108954, A000720, A060715, A104272, A143223, A143224, A143225, A143226, A143227.
%Y A014085 Cf. A010051, A061265, A221056, A000290, A145445.
%Y A014085 Counts of primes between consecutive higher powers: A060199, A061235, A062517.
%Y A014085 Cf. A333846, A349996, A349997, A349998, A349999.
%K A014085 nonn,nice
%O A014085 0,2
%A A014085 _Jon Wild_, Jul 14 1997