On Euclid's proof of the infinitude of primes and generating primes

Here's the reason why keeping primes with multiplicity makes the answer "no." If $p_n$ denotes the product of all the numbers you have so far, where $p_1$ is the product of the primes you start with, then $p_n = p_1 ... p_{n-1} + 1$. But we can rewrite this as $p_n = p_{n-1}(p_{n-1} - 1) + 1 = f(p_{n-1})$ where $f(x) = x^2 - x + 1$, and it is well-known that any prime divisor of $f(n)$ for an integer $n$ must be $2, 3$, or congruent to $1 \bmod 3$, i.e. the primes $5, 11, 17, ...$ will never appear (unless they divide $p_1$ to start with.)

(Sketch: if $q | x^2 - x + 1$ then $q | x^3 + 1$, hence $x$ has order $6 \bmod q$ or $q = 2, 3$. Since the multiplicative group $\bmod q$ has order $q - 1$, this is possible if and only if $6 | q-1$.)

Many have considered this question, and variants of this question, in their study of number theory. It's a good question in that it's easy to pose and fun to think about. It's not such a good question in that very little seems to be known about it.

Perhaps the most common variant of your construction is to at each stage not throw in all the prime factors of p₁*...*p_n + 1 but only the smallest prime factor. I call this a "Euclid sequence" with "seed" the initial, nonempty finite set of primes you start with. If your seed is {2}, this is called the Euclid-Mullin sequence. See

http://en.wikipedia.org/wiki/Euclid%E2%80%93Mullin_sequence

for some information and further links.

See Problem 6 of

http://math.uga.edu/~pete/NT2009HW1.pdf

for some questions, mostly unsolved, about these sequences. (The link is to the first problem set from an advanced undergraduate course in number theory that I teach periodically at UGA.)

Going with what Qiaochu Yuan said about f(x), it follows that we will never get those primes unless we start, even if we don't include multiplicities. Since we're starting with 'n', then we're taking the prime factors of 'n+1', then we're taking the prime factors of f(n+1), then f(f(n+1)), then f(f(f(n+1))) etc, even if we get, say, a 7² in there, our number is [f(f(f(n+1)))] / 7, which then goes into f(x). So no, unless you start with the infinite product $p_1 = \prod_{n=1}^\infty 6n-1$, you will never get any of those numbers.

It's funny, though; I'd had a whole demonstration started to show that you'll never get a multiplicity when taking f(f(...f(2)...)), but this is simpler. As for the Euclid-Mullin sequence, I have no idea.