A077766 -id:A077766 - 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

A077767 Number of primes of form 4k+3 between n^2 and (n+1)^2.

Original entry on oeis.org

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

Offset: 1

T. D. Noe, Nov 20 2002

nonn

Related to Legendre's conjecture that there is always a prime between two consecutive squares.

			a(8)=3 because primes 67, 71 and 79 are between squares 64 and 81

Seiichi Manyama, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)

Cf. A002145, A014085, A077766.

maxN=100; a=Table[0, {maxN}]; maxP=PrimePi[(maxN+1)^2]; For[i=1, i<=maxP, i++, p=Prime[i]; If[Mod[p, 4]==3, j=Floor[Sqrt[p]]; a[[j]]++ ]]; a
p3[{a_,b_}]:=Module[{p=Prime[Range[PrimePi[a]+1,PrimePi[b]]]},Count[p,?(Mod[#,4]==3&)]]; p3/@Partition[Range[100]^2,2,1] (* _Harvey P. Dale, Feb 20 2020 *)

A348193 (Number of primes == 3 mod 4 less than n^2) - (number of primes == 1 mod 4 less than n^2).

Original entry on oeis.org

0, 1, 1, 1, 2, 2, 2, 1, 3, 2, 1, 3, 4, 3, 5, 5, 4, 3, 3, 3, 2, 3, 6, 6, 5, 5, 6, 4, 5, 5, 5, 5, 6, 4, 3, 3, 4, 3, 7, 12, 10, 7, 10, 8, 9, 10, 10, 7, 6, 6, 9, 8, 6, 6, 9, 6, 4, 9, 6, 8, 8, 7, 12, 11, 11, 9, 8, 9, 12, 9, 12, 17, 12, 13, 16, 12, 16, 18, 16, 15, 12, 12, 11, 17, 18, 14, 11, 13, 9, 5, 7, 7, 6, 7, 8, 7, 6, 8, 7, 10

Offset: 1

Seiichi Manyama, Oct 06 2021

a(790) = -1.

Seiichi Manyama, Table of n, a(n) for n = 1..10000

Cf. A014085, A077766, A077767, A091295, A348194, A348195, A348196.

a(n) = sum(k=2, n^2-1, (isprime(k)&&k%4==3)-(isprime(k)&&k%4==1));

a(n) = A348195(n) - A348196(n).

A077769 Number of times that the sum of two coprime squares of opposite parity is an integer between n^2 and (n+1)^2; multiple representations are counted multiply.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 2, 3, 4, 3, 2, 4, 5, 5, 3, 6, 5, 5, 7, 6, 7, 8, 9, 5, 6, 11, 7, 8, 8, 12, 9, 10, 12, 13, 11, 10, 11, 14, 11, 11, 13, 11, 17, 15, 12, 14, 18, 14, 15, 18, 18, 15, 16, 17, 18, 17, 20, 18, 19, 18, 19, 22, 20, 21, 17, 20, 21, 25, 18, 20, 23, 26, 24, 23, 23, 25, 28, 24, 24

Offset: 1

T. D. Noe, Nov 20 2002

nonn

See A077768 for a similar, but less restrictive sequence. A077774 counts multiple representations only once. Note that by also requiring a unique representation, we obtain sequence A077766, which counts primes of the form 4k+1.

			a(8)=3 because 65=64+1, 65=49+16 and 73=64+9 are between squares 49 and 64. Note that 65 occurs twice.

Cf. A077766, A077768, A077774.

maxN=100; lst={}; For[n=1, n<=maxN, n++, cnt=0; i=n; j=0; While[i>=j, j=1; While[i^2+j^2<(n+1)^2, If[i>=j&&i^2+j^2>n^2&&GCD[i, j]==1&&OddQ[i]==EvenQ[j], cnt++ ]; j++ ]; i--; j-- ]; AppendTo[lst, cnt]]; lst

A132657 a(n) is the product of the least prime > n^2 and the greatest prime < (n+1)^2.

Original entry on oeis.org

6, 35, 143, 391, 899, 1739, 3233, 5293, 8051, 11413, 17653, 24883, 33389, 43931, 56977, 72731, 92881, 118829, 145699, 176039, 212197, 254701, 308911, 357163, 424663, 492179, 566609, 660293, 756611, 864371, 987307, 1120697, 1257923

Offset: 1

Jonathan Vos Post, Nov 15 2007

			a(1) = 6 = 2*3 = (smallest prime in [1^2,2^2]) * (largest prime in [1^2,2^2]).
a(2) = 35 = 5*7 = (smallest prime in [2^2,3^2]) * (largest prime in [2^2,3^2]).

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000040, A001358, A007491, A014085, A053000, A053001, A053607, A077766, A077767, A132435.

seq(nextprime(n^2)*prevprime((n+1)^2,n=1..100); # Robert Israel, Jan 26 2020

Table[Prime[PrimePi[n^2] + 1]*Prime[PrimePi[(n + 1)^2]], {n, 1, 40}] (* Stefan Steinerberger, Nov 20 2007 *)
NextPrime[#[[1]]]NextPrime[#[[2]],-1]&/@Partition[Range[40]^2,2,1] (* Harvey P. Dale, Aug 27 2022 *)

for(n=1,33,print1(nextprime(n^2)*precprime((n+1)^2),", ")) \\ Hugo Pfoertner, Jan 26 2020

a(n) = A007491(n) * A053001(n+1).

More terms from Stefan Steinerberger, Nov 20 2007

cp's OEIS Frontend

A348194 a(n) = A077767(n) - A077766(n).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

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

A077767 Number of primes of form 4k+3 between n^2 and (n+1)^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A348193 (Number of primes == 3 mod 4 less than n^2) - (number of primes == 1 mod 4 less than n^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A077769 Number of times that the sum of two coprime squares of opposite parity is an integer between n^2 and (n+1)^2; multiple representations are counted multiply.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A132657 a(n) is the product of the least prime > n^2 and the greatest prime < (n+1)^2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A118492 Number of Gaussian primes with floor(abs(p)) = n.

Views

Author

Keywords

Links

Crossrefs

Formula