20030808, 17:46  #1 
Aug 2002
Portland, OR USA
2·137 Posts 
Euclid sequences
In the Special whole numbers... thread in the Lounge, ewmayer wrote:
... a Euclidstyle 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 Euclidtype 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? 
20030808, 17:52  #2  
Aug 2002
Portland, OR USA
2×137 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. )
Quote:
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 

20030808, 17:55  #3  
Aug 2002
Portland, OR USA
2·137 Posts 
Hi, Bruce:
Rearding the very same sequence you mention, I quote from the nice discussion of Euclidstyle sequences in Crandall and Pomerance: Quote:
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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Euclid, the game  VBCurtis  Puzzles  0  20150309 04:28 
Euclid Mullin  henryzz  Factoring  1  20131227 01:37 
second EuclidMullin sequence  arbooker  Factoring  52  20131203 23:00 
Any interest in all sequences/open sequences?  Greebley  Aliquot Sequences  6  20120407 10:06 
Method of Euclid's Proof  kayjongsma  Math  4  20081129 20:27 