Consecutive composite numbers

When I took basic number-theory course there was this exercise to find 2000 consecutive numbers. And of course it's well known that the trick to take numbers of the form $$ (n+1)!+m, \quad 2 \leq m \leq n+1 $$ does the trick with $n=2000$. But these numbers are really huge which makes me think of the following question.

Is there a better way to construct consecutive composite numbers? With better I mean that is there a way to find smaller consecutive composites for each $n$? Or even the smallest?

Example: Smallest 3 consecutive composites are clearly $8,9,10$ but the formula gives us the numbers $26, 27, 28$ and even $14,15,16$ would be smaller. So I'm asking a way to find these smaller/smallest consecutive composites.

Solution 1:

Based on the ideas in Crostul's answer and my comment, I would suggest the following (not necessarily optimal) algorithm: Let $2000$ consecutive integers be denoted by $n, n+1,..., n+1999$. We will put conditions on $n$ so as to make all these integers composite.

(1) Require $n$ to be a multiple of $2$ (and greater than $2$). Then $n$, $n+2$, $n+4$,... are all composite. This condition is equivalent to $n\equiv 0\pmod{2}$.

(2) The first non multiple of $2$ is now $n+1$. So we'll require $3\mid n+1$. Then $n+1$, $n+4$,... are all divisible by $3$. This condition is equivalent to $n\equiv 2\pmod{3}$.

(3) At each subsequent step we determine the smallest integer in our sequence not yet known to be composite, and we force it to be a multiple of the next available prime. This will give us a congruence of the form $n\equiv t\pmod{p_k}$, where $p_k$ is the next available prime, and $t$ is some appropriate integer with $0\le t< p_k$.

Eventually all of $n, n+1, ..., n+1999$ will have to be composite. We'll then have a biggish Chinese Remainder Theorem (CRT) problem to solve for $n$, but this CRT problem will not have anywhere near $2000$ congruences because of identifying so many composites at each step.

Solution 2:

Well, the tables do not yet go high enough, but look at Prime pair points slope approaches 1

and the websites mentioned. Experience and the Granville-Cramer conjectures suggest that, to get a prime gap of 2000, we should expect the prime at the beginning of the gap to be at least $$ e^{\sqrt {2000}} \approx e^{44.721} \approx 2.64 \cdot 10^{19}, $$ maybe a little bigger.

So, wait a few years, if they get the maximal prime gap tables up to something like $10^{21}$ you would expect to get a gap over 2000. Right now the tables are up to $4 \cdot 10^{18}$

EEEDDDIIITTT: for gaps numbered 52 to 75, the ratio $g / \log^2 p$ is no smaller than $3/4.$ So, taking this as a pessimistic bound, we expect gap 2000 by

$$ e^{\sqrt {8000/3}} \approx e^{51.639} \approx 2.67 \cdot 10^{22}, $$ so maybe best up to $10^{23}$

ESSAY QUESTION: it would appear that finding a gap of fixed size (2000) is nowhere near as difficult as confirming maximal gaps. I would think that there is some low-tech method that could do this, I just do not know whether the entire range from $10^{18}$ to, say, $10^{24},$ can be done in under a year. We need to spend the smallest possible time deciding whether a number is prime or composite; a hierarchy of methods, (I) trial division by primes up to $10,000;$ (II) trial with Fermat's method of difference of squares (III) "probable prime" function from any CAS (IV) prime proof. Actual program to juggle a number of time/storage issues. Need to think about it, but I might do a tiny run with C++/GMP. All can be done because of the $10^{24}$ bound, but i have no idea how slow it would be.