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

Author

Bernard Schott, Apr 08 2020

Keywords

• nonn

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

Examples

			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.
		

Links

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

Crossrefs

Cf. A014085, A076957, A084597.

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

Cf. A349996, A349997, A349998, A349999.

Programs

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

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

Extensions

More terms from Michel Marcus, Apr 08 2020