cp's OEIS Frontend

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

%I A333846 #42 Dec 17 2024 12:56:50
%S A333846 0,1,4,6,10,15,16,24,31,38,45,48,52,57,70,76,79,106,111,117,123,134,
%T A333846 139,146,154,163,169,176,179,193,202,204,223,233,238,243,256,278,284,
%U A333846 318,326,336,359,369,412,419,430,456,458,468,479,517,550,564,595,601,612
%N A333846 Numbers k such that the number of primes between k^2 and (k+1)^2 increases to a new record.
%C A333846 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 A333846 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 A333846 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 A333846 Hugo Pfoertner, <a href="/A333846/b333846.txt">Table of n, a(n) for n = 1..2533</a>
%H A333846 Mac Tutor History of Mathematics, <a href="http://mathshistory.st-andrews.ac.uk/Biographies/Legendre.html">Adrien-Marie Legendre</a>
%H A333846 Wikipedia, <a href="https://en.wikipedia.org/wiki/Legendre%27s_conjecture">Legendre's conjecture</a>
%e A333846 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 A333846 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 A333846 (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 A333846 Cf. A014085, A076957, A084597.
%Y A333846 Cf. A333241 (Similar records between k and (9/8)*k).
%Y A333846 Cf. A349996, A349997, A349998, A349999.
%K A333846 nonn
%O A333846 1,3
%A A333846 _Bernard Schott_, Apr 08 2020
%E A333846 More terms from _Michel Marcus_, Apr 08 2020