|
| |
|
|
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(pc-pp>pr, print1(k-1, ", "); pr=pc-pp); pp=pc) \\ Hugo Pfoertner, Apr 10 2020
|
|
|
CROSSREFS
|
Cf. A333241 (Similar records between k and (9/8)*k).
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
