Euclid sequences

[Maybeso]

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]

(This seemed to be off topic, so I made it a PM. If we want it public, you could post the Euclid sequence portion in Math or Puzzles or ???, and I will post this, etc. )

So we refine the question: is there *any* Euclid sequence starting with a finite number of primes which yields all the primes?

Since E(n+1) = E(n)*(E(n) - 1) + 1, whether E(n) is prime or not, it grows beyond my digit limit long before it yields even the first 100 primes.

I noticed that if I try to add a prime to a promising set of starting primes to improve it, there is no relation between the old generated set and the new one. In other words, the hunt is a blind search.

Also, 2 is either in the starting set, or is added at the first step.

I guess a safe answer would be "There is no Euclid sequence which yields all the primes." :( Now prove me wrong! :(

A new sequence definition: "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 smallest new prime factor to your set of known primes and continue."

2*3 + 1 = 7
2*3*7 + 1 = 43
2*3*7*43 + 1 = 1807 = 13*139
2*3*7*13*43 + 1 = 23479 = 53*443
2*3*7*13*43*53 + 1 = 1244335 = 5*248867 <- a factor of 5!

This sequence grows at a slightly more reasonable rate, although the next number in the sequence is prime.

Ironic that a sequence that produces fewer primes is better at generating the smaller primes as factors.

The obvious question is - Does this sequence have a better or worse chance of yielding all of the primes?

Bruce

[Maybeso]

Hi, Bruce:

Rearding the very same sequence you mention, I quote from the nice discussion of Euclid-style sequences in Crandall and Pomerance:

The sequnce {insert your sequence here} was considered by Guy and Nowakowski and later by Shanks. [Wagstaff 1993] computed the sequence through the 43rd term. The computational problem inherent in continuing the sequence further is the enormous size of the numbers that must be factored. Already, the number q1...q43 + 1 has 180 digits.

So this "puzzle" is in fact an unsolved research problem - I suggest you combine a suitably edited version of my post with your PM to me and start a thread in the Math section.

Amazing how quickly one can get to deep, interesting research topics in number theory merely by playing around a bit with Euclid's original idea.


Cheers,
-Ernst

BTW, if you don't yet have the book by C & P, I highly recommend it.