7
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ If you start with $m$ consecutive primes, you will certainly end up with at least $m$ consecutive primes ... $\endgroup$ – Hagen von Eitzen Jul 31 '17 at 20:52
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.