

A333846


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


3



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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



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(pcpp>pr, print1(k1, ", "); pr=pcpp); pp=pc) \\ Hugo Pfoertner, Apr 10 2020


CROSSREFS

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


KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



