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

4228 Posts

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

Maybeso is offline   Reply With Quote