For $N,M\in \mathbb{N}\gt\gt 1$ can we have $N$ consecutive natural numbers of which $M$ are prime?

Question

We know that for an arbitrarily large $N \in \mathbb{N}$ we can have $N$ consecutive natural numbers of which none is prime. A construction that verifies this is the set $B(n)=\{n!+2, n!+3,\cdots,n!+n\}$ since the first term is divisible by $2$, the second by $3$ and so on. So we have gaps between primes which are as large as we want them to be.

I was wondering-as part of a cryptography application I was working on-whether

For a given $M\in \mathbb{N}$ can we choose an $N$ such that $N$ consecutive natural numbers are not primes but there exists a set of $N$ consecutive natural numbers of which $M$ are prime?

Or, for $S_N=\{s+1,s+2,\cdots,s+N\}$ such that no $s+i, i\in\{1,2,\cdots,N\}$ is prime can we have $A_n=\{a+1,a+2,\cdots,a+N\}$ such that $A_N\supset Q=\{a+j_1,a+j_2,\cdots,a+j_M\}$ is a set of $M$ primes?

The two sets can differ in terms of how large the numbers are and no other similarities except of their cardinality are required.

I think it is obvious that $M\lt\lt N$ given the "scarcity" of primes the larger the $N$ is.

Answer 1

This is actually an open problem, but conjecturally it is fairly well-understood. See my answer here to a related question: the relationship between the two problems is in fact surprisingly close!

As Ross Millikan has pointed out, obviously it is possible for $M$ to be as large as $\pi(N)$, but in fact Hensley and Richards showed there are admissible tuples which are even denser, about $\pi(N) + c N/(\log N)^2$ in size for some $c>0$. It appears to be an open problem (as of 1985) whether $c$ can be arbitrarily large.

One catch is that just because we have an admissible tuple, doesn't mean we have the computational resources to find an actual suite of primes corresponding to those offsets. The prime $k$-tuples conjecture predicts that there are infinitely many examples, but at this scale (thousands of primes!) they are expected to be so exceedingly rare that it would take an enormously long time to find a concrete example.

Answer 2

The longest string of primes is two, composed of $2$ and $3$. All even numbers other than $2$ are composite, so there is no other string longer than one. Similarly, the shortest run of naturals with three primes is four, composed of $2,3,5$. I suspect the smallest $N$ such that there are $M$ primes in a run of $N$ is the run from $2$ to $p_M$, the run that includes the first $M$ primes. For five primes you would argue that unless you can include $2$ the run has to be longer than ten numbers. Among ten numbers only five are odd and at least one of them has to be a multiple of $3$, so only four of the odd numbers can be prime.

Answer 3

For any $M$ there will be infinitely many solutions. Here is how we can generate them. What we need is given $N$ and $M$ find an $x$ such that $$ \pi(x + N) - \pi(x) \ge M. $$ where $\pi(x)$ is the prime counting funciton. The following approximation by Dusart is known

$$ \frac{x}{\log x - 1} \le \pi(x) \le \frac{x}{\log x -1.1} $$ where the lower bound holds for $x \ge 5353$ and the upper bound holds for $x \ge 60184$. Note that there are sharper bounds on $\pi(x)$ which are valid for bigger $x$, but for us the above inequality is good enough get an approximation of $x$. Thus we have

$$ \pi(x + N) - \pi(x) \ge \frac{x+N}{\log (x+N) - 1} - \frac{x}{\log x - 1.1} $$

for $x \ge 60184$. So all we need to do is solve the weaker inequality

$$ \frac{x+N}{\log (x+N) - 1} - \frac{x}{\log x - 1.1} \ge M. $$

For any given $N$ and $M$ this can easily be solved to obtain the lower bound on $x$. Thus the $N$ consecutive natural numbers $x+1, x+2,..., x+N$ will contain at least $M$ primes.

I leave the algebraic manipulation/simplification to the OP. If you want a better on $x$ all you need to do is use sharper bounds on $\pi(x)$.