# Algorithm for keeping a concrete version of Euclid's argument simple

(A version of this same question was posted to stackexchange.)

Suppose we do what Euclid wrote about: starting with a finite set of primes, multiply them, add or subtract 1, factor the result, append the prime factors to the list, then start over with the larger list and iterate. (In Euclid's version one added, not subtracted, 1. But contrary to what is sometimes reported, he didn't necessarily start with the smallest $n$ primes, but rather with an arbitrary finite set of primes.)

Now let's add a goal of trying to avoid large primes. We'd rather have many small primes than a few large ones. We might tolerate a large prime if after appending it to the list and going on to the next step, we get a large number of small ones.

Is there some systematic way of choosing the initial set and the sequences of "${}+1$"s and "${}-1$"s to avoid large primes in favor of large numbers of small primes?

Just doing some doodling, I found this:

Start with $\lbrace 5,7\rbrace$. Get $35$, subtract $1$, so we get $\lbrace2,5,7,17\rbrace$.

So we get $1190$. Subtract $1$, so that we get $\lbrace2,5,7,17,29,41\rbrace$.

So now we get $1414910$. Subtracting $1$ would give us a prime bigger than $10000$, so this time we add $1$, and get $\lbrace 2,3,5,7,17,19,29,41,103,241\rbrace$.

If I take it a step further, I need to choose between these: \begin{align} 2001971723011 & = 13 \times 105727 \times 1456561 \\ 2001971723009 & = \text{one large prime} \end{align} I haven't gone beyond that.

So is there is there nothing more efficient than just fiddling like this?

-
There really is no need to create a new tag number-theory. – Franz Lemmermeyer Oct 15 '11 at 18:05
I hadn't realized I had created a new tag. – Michael Hardy Oct 15 '11 at 18:15
Here's one that's usable for the purpose I had in mind: $\lbrace 5,11 \rbrace$ $\overset{-1}\mapsto \lbrace 2,3,5,11 \rbrace$ $\overset{-1}\mapsto\lbrace 2,3,5,7,11,47 \rbrace$ $\overset{-1}\mapsto\lbrace 2,3,5,7,11,47,151,719 \rbrace$ $\overset{-1}\mapsto\lbrace 2,3,5,7,11,47,67,79,151,719, 1249, 1783 \rbrace$. I'd been a little bit pessimistic about easily finding these, but maybe that was misplaced. – Michael Hardy Oct 17 '11 at 21:18