I’m not convinced this is MO-appropriate, but I’m posting an answer ’cause what I’d have to say is probably too long for a comment.
Expanding on Reid’s comment. Yeah, Lucas’ theorem is nice. Lucas’ theorem is one of a fair number of combinatorial results which can be thought of as “first steps towards p-adic numbers.” What’s that mean? There’s a “different” absolute value that you can define on rational numbers, which has a lot of the same properties as the usual absolute value, but in other ways behaves totally differently. Actually there are an infinite number of these guys, one for every prime $p$! It’s called the p-adic absolute value, and you can read about it on Wikipedia.
What the p-adic numbers do is help you to get around the following obstacle: Say you want to tell whether a quotient of two numbers, $\frac{a}{b}$, is divisible by $p$. (We’ll assume for now that $\frac{a}{b}$ is definitely an integer, although this ends up not mattering at all. But “divisibility” is a trickier notion for non-integers.) If $a$ is divisible by $p$ and $b$ isn’t, then it’s obvious that $\frac{a}{b}$ is; if $a$ isn’t divisible by $p$, then of course $\frac{a}{b}$ isn’t. But things get tough if both $a$ and $b$ are divisible by $p$; it could happen that $a$ is divisible by $p^2$, and $b$ is divisible by $p$ but not by $p^2$. Or that $a$ is divisible by $p^{17}$, and $b$ is divisible by $p^{14}$ but not by $p^{15}$. You see how this gets confusing! The p-adic absolute value encodes this sort of information for you.
This also explains why we don’t work with, say, 10-adic numbers in mathematics; it’s because if you take the integers but consider two integers to be the same if they have the same remainder when you divide by $n$, you can still multiply and add and subtract perfectly well. So you get something called a ring. And if $n$ is prime, you can also divide numbers! (Well, you can’t divide by 0, or by a multiple of the prime, which is “the same as” 0. But this is true no matter what, so it’s not a real problem.) But this isn’t true for composites.
Anyway, the patterns for primes in Pascal’s triangle are pretty well known. Google “Pascal’s triangle modulo” (without quotes, probably) to find more stuff. Composites don’t behave as nicely, for the reasons Wikipedia and I both briefly mentioned, but powers of primes do have interesting patterns, which you can read about in the wonderfully-titled paper “Zaphod Beeblebrox’s Brain and the Fifty-ninth Row of Pascal’s Triangle”.
Hope this helps!
You can obtain a complete heuristic picture of what is going, by supposing that quadratic residues (as suggested by Laurent) are the only likely obstruction to getting the next prime. More precisely, if you let $Q_n = \prod_{k \le n} q_k$ be the product of all of the primes discovered so far, then you can let $p_{n+1} = p$ be the first remaining prime such that $Q_n$ is a quadratic residue mod $p$, assuming Denis' first proposal. Or, assuming Denis' second proposal, you can let $p$ be the first remaining prime such that either $Q_n$ or $-Q_n$ is a quadratic residue mod $p$. (Thus it will simply be the next prime if that prime happens to be 3 mod 4.) Or, assuming that you only use the sum formula, you would only check $-Q_n$. Then experimentally, $q_{n+1} = p_{n+1}$ in all three cases.
This describes the sequence that Charles obtained, which I also obtained (at least the first half of it) with a Sage program.
qseq = [2]
for z in range(16):
attain = set(); Q = prod(qseq)
prediction = [p for p in list(primes(500)) if not p in qseq and
(legendre_symbol(-1,p) == -1 or legendre_symbol(Q,p) == 1)][0]
for S in Combinations(qseq):
A = prod(S); attain.update([abs(A-Q/A),A+Q/A])
best = 10000
attain.discard(1)
best = min([min(factor(m))[0] for m in attain])
print prediction,':',qseq,'->',best
qseq.append(best)
Assuming both the sum and the difference are used, the validity of this prediction reduces to the following: If $p$ is this next prime, then the question is whether $1$ appears in the set product of the subsets $\{q_k,1/q_k\}$ and $\{\pm 1\}$ in the multiplicative group $(\mathbb{Z}/p)^*$. This is a question in additive set theory if you take a formal logarithm and pass to the additive group $\mathbb{Z}/(p-1)$. A reasonable conjecture is that you are convolving a lot of subsets that don't come close to lying in a subgroup of $\mathbb{Z}/(p-1)$, so you can expect $0$ to appear in the sum. The heuristic has such a large margin that it may be possible with existing methods to prove that it is always so.
The other part of the question is how much you deviate from seeing the primes in order. Again, using a randomness heuristic in number theory, the "probability" that a prime $p$ will be skipped at a given stage is 1/2 (assuming that it is 1 mod 4 in the second case). So you expect the first skipped prime to eventually be included with a "half life" of one round. Thus you expect the sequence to only ever be barely ahead of the list of primes, and you expect $q_n$ to be the $n$th prime infinitely often.
Best Answer
this is somewhat related (but different) to pseudo-random number generators (PRNGs):
The $s$-dimensional Halton sequence is a quasi-Monte Carlo sequence which is a collection of van der Corput sequences in bases $\{b_{1}, b_{2}, \ldots, b_{s}\}$. The bases $b_{i}$ are chosen so that they are pairwise mutually prime. Thus, the natural choice is to use the first $s$ prime numbers.
Quasi-Monte Carlo sequences are number-theoretic sequences designed to give good uniformity in the $s$-dimensional cube. There are randomization techniques which allow them to be to used in simulation like one would with regular PRNGs.