# Does the algorithm of the Greeks produce all prime numbers?

Let $${\cal P}$$ be the set of prime numbers. Define a subset $${\cal P}'=\{p_1,p_2,p_3,\cdots\}$$ of $${\cal P}$$ by setting $$p_1=2$$ and defining $$p_{n+1}$$ to be the smallest element of $${\cal P}$$ dividing $$1+p_1\cdots p_n$$. Is there any obstruction to $${\cal P}'={\cal P}$$ ?

• I don't think I would call this "the algorithm of the Greeks", since Eratosthenes produced an algorithm which definitely captures all the primes. – Todd Trimble Dec 2 '18 at 22:28
• This and variations have been considered. There is no nice (and known to me) alternate characterization of any of these variants. You should check the OEIS for more information. Gerhard "Should Always Check The OEIS" Paseman, 2018.12.02. – Gerhard Paseman Dec 2 '18 at 22:33
• In the spirit of mathoverflow.net/questions/45951/sexy-vacuity, let me point out that the special case $p_1 = 2$ is unnecessary here — the single general case “$p_n$ is the smallest prime dividing $1 + p_1 \cdots p_{n-1}$” suffices to define the whole sequence. – Peter LeFanu Lumsdaine Dec 3 '18 at 0:21
• Note that this is not an algorithm at all, just a recursively defined sequence. An algorithm also needs to specify the way to compute it; especially in this case how to compute the smallest prime divisor. – YCor Dec 3 '18 at 2:17
• @Acccumulation Which is exactly how empty products are treated, yes. – Johannes Hahn Dec 4 '18 at 1:11

• Any idea what the euristic expected asymptotic growth of the least missed prime $p_n$ at step $n$ would be? (Sorry for this sentence's violence to the English language.) – Yaakov Baruch Dec 3 '18 at 14:07
• The OEIS A000945 b-file gives $p_{50}=31$ – Henry Dec 3 '18 at 21:32