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

A038107 Number of primes < n^2.

Original entry on oeis.org

0, 0, 2, 4, 6, 9, 11, 15, 18, 22, 25, 30, 34, 39, 44, 48, 54, 61, 66, 72, 78, 85, 92, 99, 105, 114, 122, 129, 137, 146, 154, 162, 172, 181, 191, 200, 210, 219, 228, 240, 251, 263, 274, 283, 295, 306, 319, 329, 342, 357, 367, 378, 393, 409, 421, 434, 445, 457, 474

Offset: 0

Joe K. Crump (joecr(AT)carolina.rr.com)

nonn

Also number of primes <= n^2 since n^2 is not prime.
Also the number of primes contained within an n X n square spiral. - William A. Tedeschi, Mar 03 2008
For large n, these numbers closely approximate the sum of primes less than n. For example, n = 10^10, sum of primes < n = 2220822432581729238. The number of primes < (10^10)^2 = 10^20 = 2220819602560918840. The error is 0.0000012743... The derivation of this is in the link Sum of Primes. - Cino Hilliard, Jun 09 2008
a(n) - A000720(n) = A073882(n) - A010051(n) = A117490(n). - Reinhard Zumkeller, May 20 2010
A061265(a(n)) = 1 for n > 1. - Reinhard Zumkeller, Apr 15 2013
From Zhi-Wei Sun, Feb 17 2014: (Start)
Conjecture:
(i) The sequence a(n)^(1/n) (n = 3, 4, ...) is strictly decreasing (to the limit 1).
(ii) If n > 0 is not among 25, 35, 44, 46, 105, then the interval [a(n), a(n+1)] contains at least one prime. (End)
A classical conjecture of Legendre asserts that a(n) < a(n+1) for all n > 0.
Conjecture: All the numbers Sum_{i=j,...,k} 1/a(i) with 1 < j <= k have pairwise distinct fractional parts. - Zhi-Wei Sun, Sep 24 2015

			a(2)=2 because the only primes < 4 are 2 and 3.

Zhi-Wei Sun, Problems on combinatorial properties of primes, in: M. Kaneko, S. Kanemitsu and J. Liu (eds.), Number Theory: Plowing and Starring through High Wave Forms, Proc. 7th China-Japan Seminar (Fukuoka, Oct. 28 - Nov. 1, 2013), Ser. Number Theory Appl., Vol. 11, World Sci., Singapore, 2015, pp. 169-187. (See Conjectures 2.14-2.16.)

T. D. Noe, Table of n, a(n) for n = 0..1000
Cino Hilliard, Sum of Primes.
Zhi-Wei Sun, Problems on combinatorial properties of primes, arXiv:1402.6641 [math.NT], 2014.
Wikipedia, Legendre's conjecture.

Cf. A014085 (first differences), A111208, A194189, A262408, A262443, A262447, A262462.

a038107 0 = 0
a038107 n = a000720 $ a000290 n
-- Reinhard Zumkeller, Apr 15 2013, Nov 01 2011

A038107 := proc(n) numtheory[pi]( n^2) ; end: seq(A038107(n),n=0..100) ; # R. J. Mathar, Jun 22 2009

Table[PrimePi[n^2], {n, 0, 100}] (* Ray Chandler, Oct 22 2005 *)

a(n)=primepi(n^2) \\ Charles R Greathouse IV, Apr 26 2012

[prime_pi(n^2) for n in range(0, 59)] # Zerinvary Lajos, Jun 06 2009

a(n) = A000720(A000290(n)).

a(n) ~ 1/2 * n^2/log n. - Charles R Greathouse IV, Apr 26 2012

Extended by Ray Chandler, Oct 22 2005

A224363 Primes p such that there are no squares between p and the prime following p.

Original entry on oeis.org

2, 5, 11, 17, 19, 29, 37, 41, 43, 53, 59, 67, 71, 73, 83, 89, 101, 103, 107, 109, 127, 131, 137, 149, 151, 157, 163, 173, 179, 181, 191, 197, 199, 211, 227, 229, 233, 239, 241, 257, 263, 269, 271, 277, 281, 293, 307, 311, 313, 331, 337, 347, 349, 353, 367, 373

Offset: 1

César Aguilera, Apr 04 2013

nonn

Legendre's Conjecture states that there is a prime between n^2 and (n+1)^2 for every integer n > 0 and thus that between two adjacent primes there can be at most one square. As of April 2013, the conjecture is still unproved.

a(n) = A000040(A221056(n)). - Reinhard Zumkeller, Apr 15 2013

			5 is a term because there are no squares between the adjacent primes 5 and 7.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Legendre's Conjecture
Wikipedia, Legendre's conjecture

Cf. A061265, A014085.

a224363 = a000040 . a221056  -- Reinhard Zumkeller, Apr 15 2013

Select[Prime[Range[60]], Floor[Sqrt[NextPrime[#]]] == Floor[Sqrt[#]] &] (* Giovanni Resta, Apr 10 2013 *)

Corrected and edited by Giovanni Resta, Apr 10 2013

A221056 Numbers k such that there is no square between prime(k) and prime(k+1).

Original entry on oeis.org

1, 3, 5, 7, 8, 10, 12, 13, 14, 16, 17, 19, 20, 21, 23, 24, 26, 27, 28, 29, 31, 32, 33, 35, 36, 37, 38, 40, 41, 42, 43, 45, 46, 47, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 60, 62, 63, 64, 65, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83, 84, 86

Offset: 1

Reinhard Zumkeller, Apr 15 2013

nonn

A061265(a(n)) = 0;

a(n) = A049084(A224363(n)); A000040(a(n)) = A224363(n).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Legendre's Conjecture
Wikipedia, Legendre's conjecture

Cf. A038107, A014085.

import Data.List (elemIndices)
a221056 n = a221056_list !! (n-1)
a221056_list = map (+ 1) $ elemIndices 0 a061265_list

Select[Range[86], Ceiling[Sqrt[Prime[#]]]^2 > Prime[# + 1] &] (* Zak Seidov, Apr 16 2013 *)

{for (n = 1, 86, ceil (sqrt (prime (n)))^2 > prime (n + 1) && print1 (n ","))} \\ Zak Seidov, Apr 16 2013

A104477 Number of successive squarefree intervals between primes.

Original entry on oeis.org

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

Offset: 1

Alexandre Wajnberg, Apr 18 2005

Find the number (the "run length") of successive intervals [p, p'=nextprime(p)] (followed by [p', p''], then [p'', p'''] etc.) which do not contain a square. When a square (n+1)^2 is found in such an interval, this will result in a term a(2n) = 0, preceded by a(2n-1) = the number of intervals of primes counted before reaching that square, i.e., between n^2 and (n+1)^2. - M. F. Hasler, Oct 01 2018

			a(1)=1 because the first interval between primes (2 to 3) is free of squares.
a(2)=0 because there is a square between 3 and 5.
a(7)=2 because there are two successive squarefree intervals: 17 to 19; and 19 to 23.
a(8)=0 because between 23 and 29 there is a square: 25.

Vincenzo Librandi, Table of n, a(n) for n = 1..10000

Cf. A061265, A031265, A104481.

Equals A014085 - 1 without the initial term, interleaved with 0's.

NextPrim[n_] := Block[{k = n + 1}, While[ !PrimeQ[k], k++ ]; k]; PrevPrim[n_] := Block[{k = n - 1}, While[ !PrimeQ[k], k-- ]; k]; f[n_] := If[ EvenQ[n], 0, PrimePi[ PrevPrim[(n + 3)^2/4]] - PrimePi[ NextPrim[(n + 1)^2/4]]]; Table[ f[n], {n, 100}] (* Robert G. Wilson v, Apr 23 2005 *)

p=2; c=0; forprime(np=p+1, 1e4, if( sqrtint(p) < sqrtint(np), print1(c",",c=0,","), c++); p=np) \\ For illustrative purpose. Better:
A104477(n)=if(bittest(n,0),primepi((1+n\/=2)^2)-primepi(n^2)-1,0) \\ M. F. Hasler, Oct 01 2018

a(2n) = 0: this is the interval from the greatest prime less than the (n+1)th square, through that square and up to the least prime greater than that square. - Robert G. Wilson v, Apr 23 2005
a(2n-1) = the difference between the indices of the greatest prime less than (n+1)^2 and the least prime greater than n^2. - Robert G. Wilson v, Apr 23 2005
a(2n-1) = A014085(n) - 1 = primepi((n+1)^2) - primepi(n^2) - 1. - M. F. Hasler, Oct 01 2018

More terms from Robert G. Wilson v, Apr 23 2005

Offset corrected by M. F. Hasler, Oct 01 2018

A074905 a(n) = number of terms in A030229 between prime(n) and prime(n+1).

Original entry on oeis.org

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

Offset: 1

Jani Melik, Sep 30 2002

nonn

			Between prime(6)=13 and prime(7)=17 there are two terms in A030229, namely 14 and 15, so a(6) = 2.

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A030229, A061265, A061399.

readlib(issqr): sstmp := proc(n) local t1,i; t1 := 0; for i from ithprime(n) to ithprime(n+1) do if (issqrfree(i) = 'true' and mobius(i)=1) then t1 := t1+1; fi; od; t1; end: sstmp(200);

nt[{a_,b_}]:=Count[MoebiusMu[Range[a+1,b-1]],1]; nt/@Partition[Prime[ Range[ 110]],2,1] (* Harvey P. Dale, May 18 2021 *)

Clarified definition, corrected offset, edited. - N. J. A. Sloane, May 18 2021

A104481 Bisection of A104477.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 2, 3, 2, 4, 3, 4, 4, 3, 5, 6, 4, 5, 5, 6, 6, 6, 5, 8, 7, 6, 7, 8, 7, 7, 9, 8, 9, 8, 9, 8, 8, 11, 10, 11, 10, 8, 11, 10, 12, 9, 12, 14, 9, 10, 14, 15, 11, 12, 10, 11, 16, 12, 15, 15, 12, 16, 14, 13, 15, 14, 14, 16, 12, 20, 14, 14, 16, 16, 17, 21, 13, 17, 22, 12, 19, 18, 19

Offset: 1

Alexandre Wajnberg, Apr 18 2005

a(n) = A014085(n) - 1. - Klaus Brockhaus, Apr 20 2005

Cf. A014085, A061265, A104477.

NextPrim[n_] := Block[{k = n + 1}, While[ !PrimeQ[k], k++ ]; k]; PrevPrim[n_] := Block[{k = n - 1}, While[ !PrimeQ[k], k-- ]; k]; f[n_] := PrimePi[ PrevPrim[(n + 1)^2]] - PrimePi[ NextPrim[n^2]]; Table[ f[n], {n, 83}] (* Robert G. Wilson v, Apr 23 2005 *)

More terms from Robert G. Wilson v, Apr 23 2005

A074908 Number of integers with an odd number of distinct primes (for which mu(n)=-1) between two consecutive primes prime(n) and prime(n+1).

Original entry on oeis.org

2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 2, 3, 3, 2, 3, 2, 2, 2, 2, 3, 3, 2, 3, 3, 3, 2, 3, 2, 2, 3, 2, 3, 3, 3, 2, 5, 2, 3, 2, 2, 3, 2, 2, 4, 3, 2, 3, 3, 3, 3, 2, 3, 2, 3, 5, 2, 3, 2, 2, 4, 2, 3, 2, 2, 4, 3, 3, 3, 2, 3, 2, 3, 4, 4, 2, 5, 2, 5, 3, 2, 3, 2, 2, 3, 4, 3, 2, 4, 2, 3, 3, 2, 4, 2, 3, 3, 2, 2, 3

Offset: 1

Jani Melik, Sep 30 2002

nonn

			Between 7919 and 7927 the 5 numbers which have an odd number of distinct primes are as follows: {7919,7922,7923,7926,7927}, so a(1000)=5.

Cf. A061265, A061399.

readlib(issqr): lstmp := proc(n) local t1,i; t1 := 0; for i from ithprime(n) to ithprime(n+1) do if (issqrfree(i) = 'true' and mobius(i)=-1) then t1 := t1+1; fi; od; t1; end: lstmp(200);

Offset corrected by Sean A. Irvine, Feb 01 2025

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

A038107 Number of primes < n^2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Sage

Formula

Extensions

A224363 Primes p such that there are no squares between p and the prime following p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Extensions

A221056 Numbers k such that there is no square between prime(k) and prime(k+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A104477 Number of successive squarefree intervals between primes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A074905 a(n) = number of terms in A030229 between prime(n) and prime(n+1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions