A prime generating algorithm

Question

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 lead me to a different question. In both the mentioned cases, as is 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,\dots ,p_k\}$ be a finite set of primes. Apply the following algorithm-

1. Define $N=\prod_{i=1}^kp_i+1$
2. If $N$ is prime, add $N$ to the set $P$, i.e., take $P=P\cup \{N\}$.
3. If $N$ is not prime, let $N=q_1^{\alpha_1}q_2^{\alpha_2}\dots q_m^{\alpha_m}$ where $q_i<q_{i+1}\forall i\in\{1,2,\dots ,m-1\}$. Add $q_1$ to $P$, i.e., take $P=P\cup \{q_1\}$
4. 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 seeder $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,\dots 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.

This link pointed out by Steven Clark and this one by Gerry Myerson may be of some help.

This question is now also in MathOverflow.

Answer 1

Got a few more steps by alternately using pari factoring and my small factos command; I'll put in the product $n$ and the unfactored $1+n,$ which has roughly 115 digits.

  n = 30;
 n *= 31;
 n *= 7;
 n *= 17;
n *= 11;
 n *= 751;
 n *= 23;
 n *= 29;
 n *= 109;
 n *= 193;
 n *= 1597; cout << n << mp_Factored(n) << endl;
 n *= 13;
 n *=  961861631;
 n *=  53323;
 n *=  79;
 n *=  78941;
 n *=  641;
 n *=  5689;  cout << endl<< n << mp_Factored(n) << endl;
 n *=   15997129;
 n *=   1531;
 n *=   19;
 n *=   13859; 
 n *=  mpz_class( "16592183099");
 n *=   36343;
 n *=   mpz_class( "150409865693");
 n *=  127;
 n *= 1327;
  n *= 77801;
  n *= 59;
  n *= 10837;
  system("date");
n   = 2 3 5 7 11 13 17 19 23 29 31 59 79 109 127 193 641 751 1327 1531 1597 5689 10837 13859 36343 53323 77801 78941  cdot mbox{BIG} 

  n=  1523335511241041137495811049364474481231883294665122812069204639470659080175224843733883488923439548981870

1+  n=  1523335511241041137495811049364474481231883294665122812069204639470659080175224843733883488923439548981871