%I #34 Dec 12 2021 11:51:06

%S 0,1,4,6,10,15,16,24,31,38,45,48,52,57,70,76,79,106,111,117,123,134,

%T 139,146,154,163,169,176,179,193,202,204,223,233,238,243,256,278,284,

%U 318,326,336,359,369,412,419,430,456,458,468,479,517,550,564,595,601,612

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

%C 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).

%C 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.

%C 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

%H Mac Tutor History of Mathematics, <a href="http://mathshistory.st-andrews.ac.uk/Biographies/Legendre.html">Adrien-Marie Legendre</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Legendre%27s_conjecture">Legendre's conjecture</a>

%e 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.

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

%o (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

%Y Cf. A014085, A076957, A084597.

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

%Y Cf. A349996, A349997, A349998, A349999.

%K nonn

%O 1,3

%A _Bernard Schott_, Apr 08 2020

%E More terms from _Michel Marcus_, Apr 08 2020