Proof showing there exists a sequence of $m$ consecutive natural numbers which contains exactly $n$ primes.

Question

Given that $n\in\Bbb N$, show that there exists a $k\in\Bbb N$ such that for all $m\ge k$, there exists a sequence of $m$ consecutive natural numbers which contains exactly $n$ primes.

Answer 1

First, note that for a given $n$ there exists $m_0$ and a sequence of $m_0$ consecutive natural numbers which contains exactly $n$ primes. For a proof, just consider the sequence $1,2,3,\dots,p_n$ where $p_n$ stands for the $n$-th prime (so, in this case, $m_0 = p_n$).

Second, note that (still for this fixed $n$) if $m \geq m_0$, then $m$ also "works", i.e. there exists a sequence of $m$ consecutive natural numbers with exactly $n$ primes. For a proof, start with an interval $I_0 = [a,a+1,\dots,a+m_0-1]$ that contains $n$ primes. Because $m \geq m_0$, the interval $I = [a,a+1,\dots,a+m-1] \supseteq I$ contains at least $n$ primes.

The only problem is that it could contain too many primes. If this happens, consider the shifted intervals $I+1 = [a+1,\dots,a+m]$, $I+2, I+3,\dots$. Each consecutive shift $I +j$ is obtained from the previous one $I+j-1$ by removing the least element, and adding an element just after. So, as far as the number of primes is concerned, there may be one more, one fewer, or the same number. Thus, the possible numbers of primes in $I+j$ consist of consecutive numbers (in the sense that if there can be $s$ primes in such interval, or $t$ primes, then there can be any number between $s$ and $t$).

Let us now notice that there are intervals of length $m$ that contain as few primes as you like. Indeed, just consider the intervals that begin $c \cdot (m+1)! + 2$: it's $i$-th element can easily be checked to be divisible by $i+1$, and cannot be prime. Thus, the initial interval had "too many" primes, and as you keep shifting, you find intervals that have "too few" primes. It follows that somewhere along the way, you meet an interval that has exactly the right number of primes.