$$ \begin{align} 2254 & = 2\cdot7\cdot7\cdot23 \\ 2255 & = 5\cdot11\cdot41 \\ 2256 & = 2\cdot2\cdot2\cdot2\cdot3\cdot47 \\ 2257 & = 37\cdot61 \\ 2258 & = 2\cdot1129 \\ 2259 & = 3\cdot3\cdot251 \\ 2260 & = 2\cdot2\cdot5\cdot113 \\ 2261 & = 7\cdot17\cdot19 \\ 2262 & = 2\cdot3\cdot13\cdot29 \\ 2263 & = 31\cdot73 \\ 2264 & = 2\cdot2\cdot2\cdot283 \\ 2265 & = 3\cdot5\cdot151 \\ 2266 & = 2\cdot11\cdot103 \end{align} $$ I this question I pointed something out, of which the foregoing is another instance.

The integer parts of the square roots of all of these numbers are equal to $47$, which is the $15$th prime, so if we're checking for primality, we need to search that far and the rest does itself. Now notice which primes $\le47$ appear above: $$ 2,\,3,\,5,\,7,\,11,\,13,\,17,\,19,\,23,\,29,\,31,\,37,\,41,\,\bullet,\,47 $$ i.e. all of those first $15$ except $43$. Hence nearby numbers can be divisible only by small primes that recur frequently or primes bigger than the square root of the number being factored. (In particular $2272$ is $71$ times a power of $2$, and $2268$ has no prime factors bigger than $7$.)

Is there any reasonable sense it which it could be said that we shouldn't find it so surprising that this---all those early primes occurring so close together---occurs among numbers as small as these? Should we expect frequent instances of this?

PS: "Small" should probably be taken to mean these numbers are not much bigger than $47^2=2209$, where, remember, $47$ is the biggest prime number $\le$ the square roots of these numbers.


As you acknowledge, your example is imperfect in that your set $S=\{2254,\dots,2266\}$ lacks a multiple of 43. If we take $p_i=53$, then, to cover all primes $q<p_i$ with a range of consecutive integers not all less than $p_{i-1}{}^2=47^2=2209$, we need 16 integers, and the range $\{2664,\dots,2679\}$ will do.

To investigate further, for each prime $p=p_i$ I found that range of $k=k(p)$ consecutive integers $\{n-k+1,\dots,n\}$ that covers all primes $q<p$, minimising $k(p)$, subject to $n\geqslant p_{i-1}{}^2$.

There are 1229 primes $p<10000$. For 258 of them, or about 21%, $k(p)$ sets a new record high for $k$. Below I list the results for a few of these, where $k(p)/p$ also set a record high for $k/p$.

$\begin{array}{rrrrr} p&k&n-k+1&n&k/p\\ 43&14&1763&1776&0.326\\ 103&52&10184&10235&0.505\\ 241&161&56970&57130&0.668\\ 509&358&254472&254829&0.703\\ 1013&783&1023703&1024485&0.773\\ 2113&1807&4456626&4458432&0.855\\ 5101&4476&25996157&26000632&0.877\\ 9241&8441&85369195&85377635&0.913 \end{array}$

There is a general trend upwards in $k/p$. Below is another selection where this time I selected some of those $p$ where $k(p)/p$ is less than all later $k(q)/q$ for all $q>p$ within the scope of my program run:

$\begin{array}{rrrrr} p&k&n-k+1&n&k/p\\ 17&3&285&287&0.176\\ 53&16&2664&2679&0.302\\ 101&37&9699&9735&0.366\\ 229&109&51900&52008&0.476\\ 557&301&307268&307568&0.540\\ 1031&709&1049190&1049898&0.688\\ 2237&1606&4966944&4968549&0.718\\ 5011&4084&25093284&25097367&0.815 \end{array}$

Your $p=53$ is among these! Even though making an $S$ which covers all primes $q<53$ needed $k=16$, somewhat more than your example which lacked 43, $k(53)=16$ gives $k/p\approx0.302$ which turns out to be a record low.

Whether $\liminf_{p\to\infty} k(p)/p=1$ I daren't say, but it appears that way. At any rate, once $p$ gets into the thousands, every prime $p$ needs a sequence $S$ which has (as a proportion) nearly $p$ terms.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.