A349998 -id:A349998 - cp's OEIS frontend

A349999 Least number m of primes that must have appeared in an interval [j^2, (j+1)^2], such that all intervals [k^2, (k+1)^2], k>j contain more than m primes. The corresponding values of j are A349998.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 26, 27, 28, 29, 30, 32, 33, 35, 36, 38, 39, 40, 41, 44, 45, 47, 51, 54, 56, 63, 65, 68, 70, 71, 78, 80, 85, 94, 99, 106, 107, 114, 115, 120, 121, 127, 133, 138, 146, 154, 155, 164, 168, 169, 175, 176, 177

Offset: 1

Hugo Pfoertner, Dec 09 2021

nonn

All terms are empirical (see the graph of A014085 for the limited width of the scatter band), but supporting the validity of Legendre's conjecture that there is always a prime between n^2 and (n+1)^2.

The terms are determined by searching from large to small indices in A014085 for new minima.

			See A349997 and A349998.

Hugo Pfoertner, Table of n, a(n) for n = 1..2414

Cf. A014085, A084597, A349997, A349998.

Cf. A333846, A349996.

a(n) = A014085(A349998(n)).
A014085(k) > a(n) for k > A349998(n).
A014085(k) >= a(n) for k >= A349997(n).

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

Original entry on oeis.org

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

A349997 Numbers k such that the number of primes in any interval [j^2,(j+1)^2], j>k, is not less than the number of primes in the interval [k^2,(k+1)^2].

Original entry on oeis.org

1, 7, 11, 17, 18, 26, 27, 32, 46, 50, 56, 58, 85, 88, 92, 137, 143, 145, 152, 157, 178, 188, 194, 200, 201, 208, 225, 232, 253, 263, 279, 297, 327, 331, 339, 360, 433, 451, 485, 506, 536, 541, 607, 696, 708, 717, 768, 799, 801, 806, 904, 913, 1015, 1059, 1110, 1111

Offset: 1

Hugo Pfoertner, Dec 09 2021

nonn

All terms are empirical subject to the validity of Legendre's conjecture and the boundedness of the scatter band of A014085. See there for further information.

			a(1)=1: the interval [1^2, 2^2] contains A349999(1)=2 primes {2, 3}, and no later interval contains less than 2 primes.
a(2)=7: the interval [7^2, 8^2] contains A349999(2)=3 primes {53, 59, 61}, and no later interval contains less than 3 primes.
a(12)=58: the interval [58^2, 59^2] contains A349999(12)=13 primes {3371, ..., 3469}, and no later interval contains less than 13 primes.
a(13)=85: the interval [85^2, 86^2] contains A349999(13)=16 primes {7229, ..., 7393}, and no later interval contains less than 16 primes.

Hugo Pfoertner, Table of n, a(n) for n = 1..2414
Joel E. Cohen, Conjectures about Primes and Cyclic Numbers, arXiv:2508.08335 [math.NT], 2025. See pp. 9-10.

Cf. A014085, A349998, A349999.

A014085(k) >= A014085(a(n)) for all k >= a(n).

A333846 Numbers k such that the number of primes between k^2 and (k+1)^2 increases to a new record.

Original entry on oeis.org

0, 1, 4, 6, 10, 15, 16, 24, 31, 38, 45, 48, 52, 57, 70, 76, 79, 106, 111, 117, 123, 134, 139, 146, 154, 163, 169, 176, 179, 193, 202, 204, 223, 233, 238, 243, 256, 278, 284, 318, 326, 336, 359, 369, 412, 419, 430, 456, 458, 468, 479, 517, 550, 564, 595, 601, 612

Offset: 1

Bernard Schott, Apr 08 2020

nonn

Legendre's conjecture (still open) states that for n > 0 there is always a prime between n^2 and (n+1)^2. The number of primes between n^2 and (n+1)^2 is equal to A014085(n), so, the corresponding records are given by A014085(a(n)) = 0, 2, 3, 4, 5, 6, 7, 9, 10, 12, 13, ... (A349996).
m = 25 is the smallest number such that there are exactly 8 primes between m^2 = 625 et (m+1)^2 = 676, namely {631, 641, 643, 647, 653, 659, 661, 673} but there are 9 primes between 24^2 = 576 et 25^2 = 625, namely {577, 587, 593, 599, 601, 607, 613, 617, 619} so 24 is a term but not 25; hence, 25 is the first term of A076957 that is not a record.
This sequence is infinite. Suppose for contradiction that a(n) = k was the last term, with s primes between k^2 and (k+1)^2. Then there are at most s primes between (k+1)^2 and (k+2)^2, at most s primes between (k+2)^2 and (k+3)^3, and at most s*sqrt(x) + pi(k^2) primes up to x. But there are ~ x/log x primes up to x by the Prime Number Theorem, a contradiction. This can be made sharp with various explicit estimates. - Charles R Greathouse IV, Apr 10 2020

			There are 7 primes between 16^2 and 17^2, i.e., 256 and 289, which are 257, 263, 269, 271, 277, 281, 283, and there does not exist k < 16 with 7 or more primes between k^2 and (k+1)^2, hence, 16 is in the sequence.

Hugo Pfoertner, Table of n, a(n) for n = 1..2533
Mac Tutor History of Mathematics, Adrien-Marie Legendre
Wikipedia, Legendre's conjecture

Cf. A014085, A076957, A084597.
Cf. A333241 (Similar records between k and (9/8)*k).
Cf. A349996, A349997, A349998, A349999.

primeCount[n_] := PrimePi[(n + 1)^2] - PrimePi[n^2]; pmax = -1; seq = {}; Do[p = primeCount[n]; If[p > pmax, pmax = p; AppendTo[seq, n]], {n, 0, 612}]; seq (* Amiram Eldar, Apr 08 2020 *)

print1(pr=0,", ");pp=0;for(k=1,650,my(pc=primepi(k*k));if(pc-pp>pr,print1(k-1,", ");pr=pc-pp);pp=pc) \\ Hugo Pfoertner, Apr 10 2020

More terms from Michel Marcus, Apr 08 2020

cp's OEIS Frontend

A349999 Least number m of primes that must have appeared in an interval [j^2, (j+1)^2], such that all intervals [k^2, (k+1)^2], k>j contain more than m primes. The corresponding values of j are A349998.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A349997 Numbers k such that the number of primes in any interval [j^2,(j+1)^2], j>k, is not less than the number of primes in the interval [k^2,(k+1)^2].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A333846 Numbers k such that the number of primes between k^2 and (k+1)^2 increases to a new record.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions