I posted this question in MSE around a month ago, but didn't receive any suitable answers. So, I decided to give it a try here as well-
I was trying to explain the famous proof of infinitude of primes to a young one, and I tried to explicitly show some examples. So, I said something like
Let the only primes be $2,3,5$. Then $$N=2\times 3\times 5+1=31$$ which is a prime.
So, let the only primes be $2,3,5,31$. This time $$N=2\times 3\times 5\times 31+1=931=7^2\times 19$$ which introduces two more "new primes" in the list.
But, this led me to a different question. In both the mentioned cases, as in general, if we start with the first $k$ primes, the "new prime" is the list will not be the $(k+1)$-th prime. So, my question is, if we start with a finite number of primes, and go on repeating this algorithm, are we bound to hit all the primes? If not, then what are the primes that we may hit or miss?
So, let me frame the question once again in a more mathy way
Let $P=\{p_1,p_2,\dotsc ,p_k\}$ be a finite set of primes. Apply the following algorithm:
- Define $N=\prod_{i=1}^kp_i+1$.
- If $N$ is prime, add $N$ to the set $P$, i.e., take $P=P\cup \{N\}$.
- If $N$ is not prime, let $N=q_1^{\alpha_1}q_2^{\alpha_2}\dotsm q_m^{\alpha_m}$ where $q_i<q_{i+1}$ $\forall i\in\{1,2,\dotsc ,m-1\}$. Add $q_1$ to $P$, i.e., take $P=P\cup \{q_1\}$.
- Repeat steps 1, 2, 3 using updated $P$.
Euclid's proof guarantees that this algorithm will never stop. The question is, for what initial "seeds" $P$ is this algorithm guaranteed to hit some given prime $p$ in a finite number of steps (if that's possible)? If it indeed does, then how many steps will it take? If not, then for some given initial seed $P$, what are the primes that we can be sure to miss? What changes (if any) will we notice if we change the 3rd step of the algorithm to "take $P=P\cup \{q_1,q_2,\dotsc, q_m\}$" (i.e., instead of updating the list with the least new prime, we are updating it with all the new primes)?
Although the question apparently seems to be quite elementary, I don't see any obvious way to proceed. I just feel like we need some analytic tools to answer this. I would love to know your thoughts on it.
OEIS A051342 pointed out by Steven Clark and the talk Booker and Pomerance - Euclidean prime generators by Gerry Myerson may be of some help.
An answer by Will Jagy to the MSE question (that I linked at the beginning) gives us an idea of the algorithm using a computer programme. That may of be some help as well.
