View Single Post
Old 2003-08-08, 17:46   #1
Maybeso's Avatar
Aug 2002
Portland, OR USA

2×137 Posts
Default Euclid sequences

In the Special whole numbers... thread in the Lounge, ewmayer wrote:

... a Euclid-style sequence beginning with 2. This sequence is defined as "start with one or more distinct known primes. Take their product and add one. The result is either a new prime, or factors into a set of new primes. In either case, add the newly found prime or prime factors to your set of known primes and continue."

Beginning with just the smallest known prime, 2, we add one, to get 3, which is also prime.

2*3 + 1 = 7, which is again prime. The product of 2, 3 and 7 is 42.

A more interesting question is: will such a Euclid-type inductive sequence eventually yield ALL the primes? For instance, if we continue the particular sequence above, we get:

2*3*7 + 1 = 43, which is again prime.

2*3*7*43 + 1 = 1807 = 13*139.

2*3*7*13*43*139 + 1 = 3263443, which is prime.

2*3*7*13*43*139*3263443 + 1 = 10650056950807 = 547*607*1033*31051.

It's pretty easy to show that the Euclid sequence starting with 2 and 3 never yields a number divisible by 5, so the answer to the above question is no. So we refine the question: is there *any* Euclid sequence starting with a finite number of primes which yields all the primes?
Maybeso is offline   Reply With Quote