MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

(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?

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.