Largest set of consecutive prime numbers.

Question

This is related to Euclid's proof of the infinitude of primes.

For any finite set $S = \{p_1, \ldots, p_r \}$ of primes, consider the number $n = p_1 p_2 \ldots p_r + 1$. This $n$ has a prime divisor $p$. But $p$ is not one of the $p_i$ (where $1 \leq i \leq r$): otherwise $p$ would be a divisor of $n$ and of the product $p_1 p_2 \ldots p_r$, and thus also of the difference $n – p_1 p_2 \ldots p_r = 1, which is impossible.

So, $S$ cannot be the collection of all prime numbers. (Q.E.D.)

Suppose I modify this proof into an algorithm for generating primes, as follows:

Start with some initial set $S_0 = S$; at each step $i$, constructing $n$ as described in the proof, set $S_{i + 1} = S_i \cup \{p: p \textrm{ is a prime divisor of } n\}$.

Clearly, this algorithm will produce a sequence of ever-larger sets of prime numbers, but the primes in these sets will not necessarily be consecutive. How can I find a starting set which leads to the largest set of consecutive prime numbers (each subsequently generated number should be next consecutive when added into the set)?

Ex. Initial set $S = \{ 2 \}$.

$n = 2 + 1 = 3$, $3$ has one prime factor only, i.e $3$, so the updated set is $S = \{2, 3 \}$.

$n = 2 \times 3 + 1 = 7$. $7$ has one prime factor only, i.e $7$, so $\{2, 3, 7 \}$.

But $5$ goes missing, hence starting with $2$ goes to maximum set size $2$.

Answer 1

2 is the most possible. Suppose otherwise; start with $\{p_n,p_{n+1}\}$ and assume that $p_np_{n+1} + 1= p_{n+2}$ (or equivalently, $p_np_{n+1} = p_{n+2}-1$). By Bertrand's Postulate, we have that $p_{n+2} -1 < 2p_{n+1} - 3 < 2p_{n+1}$, giving us $p_n < 2$, a contradiction.

Answer 2

Indeed $2$ gives you the greatest possible set of consecutive primes when starting from a set consisting of a single prime.

Except for $2$, all positive primes are odd. So if $S = \{ p \}$, where $p$ is some arbitrary odd prime, clearly the next prime to add to $S$ is $2$, because $p + 1$ is even. How are you handling things when $n$ has more than one distinct prime factor?

As Mr. Eitzen suggested in a comment he posted as I was writing this, you could just start with a set of more than one consecutive prime, e.g., $\{ 2, 3, 5 \}$. But then by Bertrand's postulate (mentioned by S. Ong), we're guaranteed to have at least one prime between $p_2 \ldots p_r$ and $2 p_2 \ldots p_r$ (let's say we always do $p_1 = 2$).

Our best hope at this point is for $2 p_2 \ldots p_r + 1$ to be composite. But what are the odds that this number would be divisible by precisely those primes between $p_r$ and $2 p_2 \ldots p_r + 1$?

In the $\{ 2, 3, 5 \}$ example, we'd get $31$ as our next prime, skipping over $7, 11, 13, 17, 19, 23, 29$. Let's then try $\{ 2, 3, 5, 7, 11, 13 \}$, which if I recall correctly will give us a composite number. Ah, yes, $30031 = 59 \times 509$. But that skips over $17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 61, 67, 71, 73, 79, \ldots$

I leave it to someone else to work out by the prime number theorem a rough estimate of how many primes there are between $p_r$ and $2 p_2 \ldots p_r + 1$, and how unlikely it is by the latter number to be divisible by all those primes.