A053000 -id:A053000 - cp's OEIS frontend

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

Jon Wild, Jul 14 1997

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

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

J. R. Goldman, The Queen of Mathematics, 1998, p. 82.

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

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.

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

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

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

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

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

A007491 Smallest prime > n^2.

Original entry on oeis.org

2, 5, 11, 17, 29, 37, 53, 67, 83, 101, 127, 149, 173, 197, 227, 257, 293, 331, 367, 401, 443, 487, 541, 577, 631, 677, 733, 787, 853, 907, 967, 1031, 1091, 1163, 1229, 1297, 1373, 1447, 1523, 1601, 1693, 1777, 1861, 1949, 2027, 2129, 2213, 2309, 2411, 2503

Offset: 1

N. J. A. Sloane, Robert G. Wilson v, R. K. Guy

Suggested by Legendre's conjecture (still open) that there is always a prime between n^2 and (n+1)^2.
Legendre's conjecture is equivalent to a(n) < (n+1)^2. - Jean-Christophe Hervé, Oct 26 2013
From Jaroslav Krizek, Apr 02 2016: (Start)
Conjectures:
1) There is always a prime p between n^2 and n^2+n (verified up to 13*10^6).
2) a(n) is the smallest prime p such that n^2 < p < n^2+n; a(n) < n^2+n.
3) For all numbers k >= 1 there is the smallest number m > 2*(k+1) such that for all numbers n >= m there is always a prime p between n^2 and n^2 + n - 2k. Sequence of numbers m for k >= 1: 6, 8, 12, 13, 14, 24, 24, 24, 30, 30, 30, 31, 33, 35, 43, ...; lim_{k->oo} m/2k = 1. Example: k=2; for all numbers n >= 8 there is always a prime p between n^2 and n^2 + n - 4. (End)

Archimedeans Problems Drive, Eureka, 24 (1961), 20.
J. R. Goldman, The Queen of Mathematics, 1998, p. 82.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 19.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Jean-Christophe Hervé, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Eric Weisstein's World of Mathematics, Landau's Problem.
Eric Weisstein's World of Mathematics, Legendre's Conjecture.

Cf. A053000, A053001, A014085, A144831.

Cf. A007918, A000290.

a007491 = a007918 . a000290  -- Reinhard Zumkeller, Jun 07 2015

[NextPrime(n^2): n in [1..50]]; // Vincenzo Librandi, Apr 30 2015

Maple
```
[seq(nextprime(i^2), i=1..100)];
```

NextPrime[Range[60]^2]  (* Harvey P. Dale, Mar 24 2011 *)

PARI
```
vector(100,i,nextprime(i^2))
```

from sympy import nextprime
def a(n): return nextprime(n**2)
print([a(n) for n in range(1, 51)]) # Michael S. Branicky, Jan 13 2023

a(n) = A007918(A000290(n)). - Reinhard Zumkeller, Jun 07 2015

More terms from Labos Elemer, Nov 17 2000

Definition modified by Jean-Christophe Hervé, Oct 26 2013

A053001 Largest prime < n^2.

Original entry on oeis.org

3, 7, 13, 23, 31, 47, 61, 79, 97, 113, 139, 167, 193, 223, 251, 283, 317, 359, 397, 439, 479, 523, 571, 619, 673, 727, 773, 839, 887, 953, 1021, 1087, 1153, 1223, 1291, 1367, 1439, 1511, 1597, 1669, 1759, 1847, 1933, 2017, 2113, 2207, 2297, 2399, 2477, 2593

Offset: 2

N. J. A. Sloane, Feb 21 2000

Suggested by Legendre's conjecture (still open) that there is always a prime between n^2 and (n+1)^2.

Legendre's conjecture is equivalent to a(n) > (n-1)^2. - John W. Nicholson, Dec 11 2013

J. R. Goldman, The Queen of Mathematics, 1998, p. 82.

T. D. Noe, Table of n, a(n) for n=2..1000

Cf. A007491, A053000, A014085.

Cf. A007917, A000290.

a053001 = a007917 . a000290  -- Reinhard Zumkeller, Jun 07 2015

Maple
```
[seq(prevprime(i^2),i=2..100)];
```

Table[Prime[PrimePi[n^2]], {n, 2, 60}] (* Stefan Steinerberger, Apr 01 2006 *)
Table[NextPrime[n^2, -1], {n, 2, 60}] (* Jean-François Alcover, Oct 14 2013 *)

a(n) = precprime(n^2) \\ Michel Marcus, Oct 14 2013

from sympy import prevprime
def a(n):  return prevprime(n*n)
print([a(n) for n in range(2, 52)]) # Michael S. Branicky, Jul 29 2022

a(n) = A007917(A000290(n)). - Reinhard Zumkeller, Jun 07 2015

More terms from James Sellers, Feb 22 2000

A069003 Smallest integer d such that n^2 + d^2 is a prime number.

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 2, 3, 4, 1, 4, 7, 2, 1, 2, 1, 2, 5, 6, 1, 4, 5, 8, 1, 4, 1, 2, 5, 4, 11, 4, 3, 2, 5, 2, 1, 2, 3, 10, 1, 4, 5, 8, 9, 2, 5, 2, 13, 4, 7, 4, 3, 10, 1, 4, 1, 2, 3, 6, 13, 10, 3, 32, 9, 2, 1, 2, 5, 10, 3, 6, 5, 2, 1, 4, 5, 10, 7, 4, 7, 4, 3, 18, 1, 2, 9, 2, 3, 4, 1, 4, 7, 8, 1, 2, 5, 2, 3, 4, 3

Offset: 1

T. D. Noe, Apr 02 2002

With i being the imaginary unit, n + di is the smallest Gaussian prime with real part n and a positive imaginary part. Likewise for n - di. See A002145 for Gaussian primes with imaginary part 0. - Alonso del Arte, Feb 07 2011
Conjecture: a(n) does not exceed 4*sqrt(n+1) for any positive integer n. - Zhi-Wei Sun, Apr 15 2013
Conjecture holds for the first 15*10^6 terms. - Joerg Arndt, Aug 19 2014
Infinitely many d exist such that n^2 + d^2 is prime, under Schinzel's Hypothesis H; see Sierpinski (1988), p. 221. - Jonathan Sondow, Nov 09 2015

			a(5)=2 because 2 is the smallest integer d such that 5^2+d^2 is a prime number.

W. Sierpinski, Elementary Theory of Numbers, 2nd English edition, revised and enlarged by A. Schinzel, Elsevier, 1988.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Eric Weisstein's World of Mathematics, Gaussian Prime.
Wikipedia, Schinzel's Hypothesis H.

Cf. A068486 (lists the prime numbers n^2 + d^2).
Cf. A185636, A204065.
Cf. A239388, A239389 (record values).
Cf. A053000.

f:= proc(n) local d;
     for d from 1+(n mod 2) by 2 do
       if isprime(n^2+d^2) then return d fi
     od
end proc:
f(1):= 1:
map(f, [$1..1000]); # Robert Israel, Jul 06 2015

imP4P[n_] := Module[{k = 1}, While[Not[PrimeQ[n^2 + k^2]], k++]; k]; Table[imP4P[n], {n, 50}] (* Alonso del Arte, Feb 07 2011 *)

a(n)=my(k);while(!isprime(n^2+k++^2),);k \\ Charles R Greathouse IV, Mar 20 2013

A085099 Least natural number k such that k^2 + n is prime.

Original entry on oeis.org

1, 1, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 4, 1, 6, 7, 2, 9, 2, 1, 12, 1, 4, 3, 2, 3, 6, 1, 2, 3, 2, 1, 24, 1, 2, 3, 4, 1, 6, 5, 2, 3, 4, 1, 6, 5, 2, 9, 2, 1, 18, 1, 6, 3, 2, 3, 6, 1, 2, 9, 2, 1, 6, 1, 4, 3, 2, 5, 6, 1, 2, 3, 4, 1, 12, 5, 2

Offset: 1

Jason Earls, Aug 10 2003

First values of k and n such that k > 100 are: k=114, n=6041; for k > 200: k=210, n=26171; for k > 300: k=357, n=218084; for k > 400: k=402, n=576239.
Additionally, for k > 500: k=585, n=3569114; for k > 600: k=630, n=3802301; for k > 700: k=744, n=24307841; for k > 800: k=855, n=25051934; for k > 900: k=1008, n=54168539. Other cases k > 900: k=945, n=74380946, k=915, n=89992964, k=939, n=118991066. - Zak Seidov, May 23 2007
It is easily proved that for n > 2, a(n) >= A089128(n+1). The first inequality is a(21) = 4. - Franklin T. Adams-Watters, May 16 2018

Zak Seidov, Table of n, a(n) for n = 1..10000

Cf. A059843, A200926, A058055, A053000, A089128.

a:= proc(n) local d, t; d, t:= 1, n+1; while not
      isprime(t) do d:= d+2; t:= t+d od; (d+1)/2
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Feb 04 2019

Table[i = 1; While[! PrimeQ[i^2 + n], i++]; i, {n, 85}] (* Jayanta Basu, Apr 24 2013 *)

a(n)=my(k); while(!isprime(k++^2+n),); k \\ Charles R Greathouse IV, Jul 17 2016

a(n) = sqrt(A059843(n) - n). - Zak Seidov, Nov 24 2011

A056929 Difference between n^2 and average of smallest prime greater than n^2 and largest prime less than n^2.

Original entry on oeis.org

0, 0, 1, -1, 2, -1, 0, 0, 1, 1, 0, -1, 1, 0, 2, 1, 0, -2, 1, 0, 1, -3, 2, 0, 1, -1, 4, -5, 3, 1, -2, 0, -2, -1, 2, -1, 1, 4, 1, 0, -4, -5, -5, 3, -5, -1, 1, -4, 10, 0, 1, -2, 3, -5, 7, 9, -2, 1, 0, -2, 4, -9, 0, 1, 3, 1, -5, -10, 4, -4, 0, 1, 2, -6, 12, -4, 0, 3, -9, 3, -2, -2, 6, 1, -6, 2, -3

Offset: 2

Henry Bottomley, Jul 12 2000

Conjecture: the most frequent value will be 1 (including sequence variants with any even power n^2k). - Bill McEachen, Dec 12 2022

			a(4)=1 because smallest prime greater than 4^2 is 17, largest prime less than 4^2 is 13, average of 17 and 13 is 15 and 16-15=1.

Hugo Pfoertner, Table of n, a(n) for n = 2..10000

Cf. A007491, A053000, A053001, A056927, A056928, A056930, A056931.

with(numtheory): A056929 := n-> n^2-(prevprime(n^2)+nextprime(n^2))/2);

Array[# - Mean@ {NextPrime[#], NextPrime[#, -1]} &[#^2] &, 87, 2] (* Michael De Vlieger, May 20 2018 *)

a(n) = n^2 - (nextprime(n^2) + precprime(n^2))/2; \\ Michel Marcus, May 20 2018

a(n) = A000290(n) - A056928(n).

a(n) = (A056927(n) - A053000(n))/2.

More terms from James Sellers, Jul 13 2000

A056931 Difference between n-th oblong (promic) number, n(n+1), and the average of the smallest prime greater than n^2 and the largest prime less than (n+1)^2.

Original entry on oeis.org

0, 0, 0, 0, 0, -1, -1, 0, 3, -1, -2, -1, 0, 1, 2, 1, -3, -2, 0, 1, 1, -4, 2, -2, 0, 3, -1, 0, 0, -2, -3, 0, -3, 0, 0, 0, 3, 0, 5, -4, -6, -5, -3, 0, -6, 1, -2, 6, 2, -2, 1, -2, 0, 1, 9, 0, 2, -2, -3, 2, -1, -9, 1, 1, 2, -1, -6, -6, -1, -3, 0, 0, 0, 6, -1, -3, 3, -2, -7, 1, -2, 1, 2, -1, -4

Offset: 2

Henry Bottomley, Jul 12 2000

a(1)=-0.5 which is not an integer

			a(4)=0 because smallest prime greater than 4^2 is 17, largest prime less than 5^2 is 23, average of 17 and 23 is 20 and 4*5-20=0

Cf. A002378, A007491, A053000, A053001, A056927, A056928, A056929, A056930.

with(numtheory): A056931 := n-> n*(n+1)-(prevprime((n+1)^2)+nextprime(n^2))/2);

a(n) =A002378(n)-(A007491(n)+A053001(n+1))/2 =A002378(n)-A056930(n).

More terms from James Sellers, Jul 13 2000

A058055 a(n) is the smallest positive number m such that m^2 + n is the next prime > m^2.

Original entry on oeis.org

1, 3, 8, 5, 12, 11, 18, 51, 82, 49, 234, 23, 42, 75, 86, 231, 174, 107, 288, 63, 80, 69, 102, 325, 166, 765, 128, 143, 822, 727, 276, 597, 226, 835, 702, 461, 254, 693, 592, 797, 1284, 349, 370, 2337, 596, 645, 3012, 1033, 590, 4083, 1490, 757, 882, 833, 1668

Offset: 1

Labos Elemer, Nov 20 2000

nonn

The primes are in A058056.

			n=6: a(6)=11 and 11^2+6 is 127, a prime; n=97: a(97) = 2144 and 2144^2+97 = 4596833, the least prime of the form m^2+97.

Zak Seidov, Table of n, a(n) for n = 1..500 (first 400 terms from T. D. Noe)

Cf. A053000, A070316, A070317.

See A085099, A215249 for other versions.

for m from 1 to 10^5 do
   r:= nextprime(m^2)-m^2;
   if not assigned(R[r]) then R[r]:= m end if;
end do:
J:= map(op,{indices(R)}):
N:= min({$1..J[-1]} minus J)-1:
[seq(R[j],j=1..N)]; # Robert Israel, Aug 10 2012

nn = 100; t = Table[0, {nn}]; found = 0; m = 0; While[found < nn, m++; k = NextPrime[m^2] - m^2; If[k <= nn && t[[k]] == 0, t[[k]] = m; found++]]; t (* T. D. Noe, Aug 10 2012 *)

R = {}   # After Robert Israel's Maple script.
for m in (1..2^12) :
    r = next_prime(m^2) - m^2
    if r not in R : R[r] = m
L = sorted(R.keys())
for i in (1..len(L)-1) :
    if L[i] != L[i-1]+1 : break
[R[k] for k in (1..i)]  # Peter Luschny, Aug 11 2012

a(n) = Min{ m > 0 | m^2 + n is the next prime after m^2}.

A053000(a(n)) = n. - Zak Seidov, Apr 12 2013

Definition corrected by Zak Seidov, Mar 03 2008, and again by Franklin T. Adams-Watters, Aug 10 2012

A060272 Distance from n^2 to closest prime.

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 2, 3, 2, 1, 6, 5, 2, 1, 2, 1, 4, 7, 2, 1, 2, 3, 6, 1, 6, 1, 2, 3, 2, 7, 6, 3, 2, 3, 2, 1, 2, 3, 2, 1, 12, 5, 2, 3, 2, 3, 2, 5, 2, 3, 8, 3, 6, 1, 2, 1, 2, 3, 10, 7, 2, 3, 2, 3, 4, 1, 4, 3, 2, 3, 2, 5, 4, 1, 2, 3, 2, 5, 6, 3, 2, 5, 6, 1, 4, 3, 4, 3, 2, 1, 6, 3, 2, 1, 4, 5, 4, 3, 2, 7, 8, 5, 2

Offset: 1

Labos Elemer, Mar 23 2001

nonn

			n=1: n^2=1 has next prime 2, so a(1)=1;
n=11: n^2=121 is between primes {113,127} and closer to 127, thus a(11)=6.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A007491, A053001, A058043, A056927, A053000, A051700, A060268-A060269, A060272, A059959, A059790.

seq((s-> min(nextprime(s)-s, `if`(s>2, s-prevprime(s), [][])))(n^2), n=1..256);  # edited by Alois P. Heinz, Jul 16 2017

Table[Function[k, Min[k - #, NextPrime@ # - k] &@ If[n == 1, 0, Prime@ PrimePi@ k]][n^2], {n, 103}] (* Michael De Vlieger, Jul 15 2017 *)
Min[#-NextPrime[#,-1],NextPrime[#]-#]&/@(Range[110]^2) (* Harvey P. Dale, Jun 26 2021 *)

a(n) = if (n==1, nextprime(n^2) - n^2, min(n^2 - precprime(n^2), nextprime(n^2) - n^2)); \\ Michel Marcus, Jul 16 2017

a(n) = abs(A000290(n) - A113425(n)) = abs(A000290(n) - A113426(n)). - Reinhard Zumkeller, Oct 31 2005

A056928 Average of the smallest prime greater than n^2 and the largest prime less than n^2.

Original entry on oeis.org

4, 9, 15, 26, 34, 50, 64, 81, 99, 120, 144, 170, 195, 225, 254, 288, 324, 363, 399, 441, 483, 532, 574, 625, 675, 730, 780, 846, 897, 960, 1026, 1089, 1158, 1226, 1294, 1370, 1443, 1517, 1599, 1681, 1768, 1854, 1941, 2022, 2121, 2210, 2303, 2405, 2490

Offset: 2

Henry Bottomley, Jul 12 2000

			a(4)=15 because the smallest prime greater than 4^2 is 17, the largest prime less than 4^2 is 13, and the average of 17 and 13 is 15.

Hugo Pfoertner, Table of n, a(n) for n = 2..10000

Cf. A007491, A053000, A053001, A056927, A056929, A056930, A056931.

Table[n2=n^2;(NextPrime[n2,-1]+NextPrime[n2])/2,{n,2,100}] (* Vladimir Joseph Stephan Orlovsky, Mar 09 2011 *)

a(n) = (nextprime(n^2) + precprime(n^2))/2; \\ Michel Marcus, May 20 2018

a(n) = (A007491(n) - A053001(n))/2.
a(n) = A000290(n) + (A053000(n) - A056927(n))/2.
a(n) = A000290(n) - A056929(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

A007491 Smallest prime > n^2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A053001 Largest prime < n^2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A069003 Smallest integer d such that n^2 + d^2 is a prime number.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A085099 Least natural number k such that k^2 + n is prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A056929 Difference between n^2 and average of smallest prime greater than n^2 and largest prime less than n^2.

Views

Author

Keywords

Comments

Examples