OFFSET
0,2
COMMENTS
Suggested by Legendre's conjecture (still open) that for n > 0 there is always a prime between n^2 and (n+1)^2.
a(n) is the number of occurrences of n in A000006. - Philippe Deléham, Dec 17 2003
See the additional references and links mentioned in A143227. - Jonathan Sondow, Aug 03 2008
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]
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
For n > 0: number of occurrences of n^2 in A145445. - Reinhard Zumkeller, Jul 25 2014
Sorenson & Webster (2025) show that there's at least one prime in [n^2, n^2+n] and at least one in [n^2+n, (n+1)^2], thus a(n) >= 2 for all 0 < n < 7*10^13. But Oliveira e Silva et al. (2014) show there's no gap > 1500 up to 4*10^18 and no gap > 1200 up to 8*10^16. If the maximum gap up to n^2 is m(n), then a(n) >= (2n+1)/m(n+1), which means a(2*10^9) > 2*10^6 and a(2*10^8) > 2*10^5. - M. F. Hasler, May 03 2026
REFERENCES
J. R. Goldman, The Queen of Mathematics, 1998, p. 82.
LINKS
T. D. Noe, Table of n, a(n) for n = 0..10000
Joel E. Cohen, Conjectures about Primes and Cyclic Numbers, arXiv:2508.08335 [math.NT], 2025. See p. 8.
Pierre Dusart, The k-th prime is greater than k(ln k + ln ln k - 1) for k >= 2, Mathematics of Computation 68: (1999), 411-415.
Tsutomu Hashimoto, On a certain relation between Legendre's conjecture and Bertrand's postulate, arXiv:0807.3690 [math.GM], 2008.
Mehdi Hassani, Counting primes in the interval (n^2, (n+1)^2), arXiv:math/0607096 [math.NT], 2006.
Edmund Landau, Gelöste und ungelöste Probleme aus der Theorie der Primzahlverteilung und der Riemannschen Zetafunktion. Jahresbericht der Deutschen Mathematiker-Vereinigung (1912), Vol. 21, page 208-228.
Tomás Oliveira e Silva, Siegfried Herzog, and Silvio Pardi, Empirical verification of the even Goldbach conjecture and computation of prime gaps up to 4*10^18, Mathematics of Computation Vol. 83, No. 288 (2014), pp. 2033-2060.
Michael Penn, Legendre's Conjecture is probably true, and here's why, YouTube video, 2023.
Hugo Pfoertner, One million terms in b-file format, 13.1 MB (2024).
Hugo Pfoertner, Plot of 10^6 sequence terms with conjectured scatter band, large pdf (13.6 MB) (2024).
Hugo Pfoertner, Lower limit of the scatter band represented as a step function.
Jonathan Sorenson and Jonathan Webster, An algorithm to verify Legendre’s conjecture up to 7*10^13, Research in Number Theory 11:4 (2025).
Eric Weisstein's World of Mathematics, Legendre's Conjecture.
Wikipedia, Legendre's conjecture.
FORMULA
a(n) = Sum_{k = n^2..(n+1)^2} A010051(k). - Reinhard Zumkeller, Mar 18 2012
Conjecture: for all n>1, abs(a(n)-(n/log(n))) < sqrt(n). - Alain Rocchelli, Sep 20 2023
Up to n = 10^6 there are no counterexamples to this conjecture. - Hugo Pfoertner, Dec 16 2024
Sorenson & Webster show that a(n) > 0 for all 0 < n < 7.05 * 10^13. - Charles R Greathouse IV, Jan 31 2025 [Actually, a(n) >= 2, cf. COMMENTS.]
EXAMPLE
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).
MATHEMATICA
Table[PrimePi[(n + 1)^2] - PrimePi[n^2], {n, 0, 80}] (* Lei Zhou, Dec 01 2005 *)
(* Alternative: *)
Differences[PrimePi[Range[0, 90]^2]] (* Harvey P. Dale, Nov 25 2015 *)
PROG
(PARI) a(n)=primepi((n+1)^2)-primepi(n^2) \\ Charles R Greathouse IV, Jun 15 2011
(Haskell)
a014085 n = sum $ map a010051 [n^2..(n+1)^2]
-- Reinhard Zumkeller, Mar 18 2012
(Python)
from sympy import primepi
def a(n): return primepi((n+1)**2) - primepi(n**2)
print([a(n) for n in range(81)]) # Michael S. Branicky, Jul 05 2021
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
Jon Wild, Jul 14 1997
STATUS
approved