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

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, 10, 9, 10, 9, 9, 12, 11, 12, 11, 9, 12, 11, 13, 10, 13, 15, 10, 11, 15, 16, 12, 13, 11, 12, 17, 13, 16, 16, 13, 17, 15, 14, 16, 15, 15, 17, 13, 21, 15, 15, 17, 17, 18, 22, 14, 18, 23, 13

Offset: 0

Author

Jon Wild, Jul 14 1997

Keywords

• nonn
• nice

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

Examples

			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).
		

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.
• Peter Munn, Logarithmic plot: number of primes between consecutive squares vs number of integers between the same squares
• 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

Crossrefs

First differences of A038107.

Cf. A000006, A053000, A053001, A007491, A077766, A077767, A108954, A000720, A060715, A104272, A143223, A143224, A143225, A143226, A143227.

Cf. A010051, A061265, A221056, A000290, A145445.

Counts of primes between consecutive higher powers: A060199, A061235, A062517.

Cf. A333846, A349996, A349997, A349998, A349999.

Programs

Haskell

a014085 n = sum $ map a010051 [n^2..(n+1)^2]
-- Reinhard Zumkeller, Mar 18 2012

Mathematica

Table[PrimePi[(n + 1)^2] - PrimePi[n^2], {n, 0, 80}] (* Lei Zhou, Dec 01 2005 *)
Differences[PrimePi[Range[0,90]^2]] (* Harvey P. Dale, Nov 25 2015 *)

PARI

a(n)=primepi((n+1)^2)-primepi(n^2) \\ Charles R Greathouse IV, Jun 15 2011

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

Formula

a(n) = A000720((n+1)^2) - A000720(n^2). - Jonathan Vos Post, Jul 30 2008

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