Finding consecutive composite numbers [duplicate]

Solution 1:

Let $[k]_n = \{k, k+1, ..., k+n-1\}$ and let $\mathbb{P}$ denote the set of primes. Define $f(n) = \min\{k \in \mathbb{N} : [k]_{n} \cap \mathbb{P} = \varnothing\}$.

Consider that the prime number theorem says that $\frac{n}{\log n}(1+o(1))$ of the positive integers $\leq n$ are prime. By the pigeonhole principle, this implies that we should have a string of $\log n(1-o(1))$ consecutive composites $\leq n$. Therefore, we can expect that the first string of $k$ consecutive composites occurs somewhere in $\left[1, \exp\left(\frac{k}{1-o(1)}\right)\right]$. In other words, $f(n) \leq \exp\left(\frac{k}{1-o(1)}\right)$. Since $\exp\left(\frac{k}{1-o(1)}\right) = o(k!)$, this is certainly better than the usual $k!+2, k!+3...$ argument.

However, this is not the best we can do. It's for example known that $\limsup_{n \to \infty} \frac{p_{n+1} - p_n}{\log p_n} = \infty$, and hence (per the PNT) $\limsup_{n \to \infty} \frac{p_{n+1} - p_n}{\log p_{n+1}} = \infty$. From this, it's not hard to see that for any $M>0$, there are infinitely many $k$ such that $f(\lceil M\log p_{k+1} \rceil) \leq p_{k+1}$. In other words, for any $M>0$, there are infinitely many integers $r$ such that $f(r) \leq \exp\left(\frac{r}{M}\right) $.

The current best known result of this flavor is that there is an absolute constant $C>0$ such that $$p_{n+1} - p_n > \frac{C \log n \log \log n \log \log \log \log n}{\log \log \log n}$$