mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-08-08, 17:46   #1
Maybeso
 
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
Old 2003-08-08, 17:52   #2
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2×137 Posts
Default

(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:
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 is offline   Reply With Quote
Old 2003-08-08, 17:55   #3
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

11216 Posts
Default

Hi, Bruce:

Rearding the very same sequence you mention, I quote from the nice discussion of Euclid-style sequences in Crandall and Pomerance:
Quote:
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.
Maybeso is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Euclid, the game VBCurtis Puzzles 0 2015-03-09 04:28
Euclid Mullin henryzz Factoring 1 2013-12-27 01:37
second Euclid-Mullin sequence arbooker Factoring 52 2013-12-03 23:00
Any interest in all sequences/open sequences? Greebley Aliquot Sequences 6 2012-04-07 10:06
Method of Euclid's Proof kayjongsma Math 4 2008-11-29 20:27

All times are UTC. The time now is 22:34.


Fri Jan 21 22:34:42 UTC 2022 up 182 days, 17:03, 0 users, load averages: 1.41, 2.76, 3.08

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔