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

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,3

Comments

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

Links

Table of n, a(n) for n=1..57.

Mac Tutor History of Mathematics, Adrien-Marie Legendre

Wikipedia, Legendre's conjecture

Example

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.

Mathematica

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

Prog

(PARI) 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

Crossrefs

Cf. A014085, A076957, A084597.

Cf. A333241 (Similar records between k and (9/8)*k).

Cf. A349996, A349997, A349998, A349999.

Sequence in context: A084372 A353543 A140611 * A076957 A310585 A179445

Adjacent sequences: A333843 A333844 A333845 * A333847 A333848 A333849

Keyword

nonn

Author

Bernard Schott, Apr 08 2020

Extensions

More terms from Michel Marcus, Apr 08 2020

Status

approved