mersenneforum.org > Math question about a chain of primes
 Register FAQ Search Today's Posts Mark Forums Read

 2014-01-02, 11:15 #1 firejuggler     Apr 2010 Over the rainbow 2·3·5·79 Posts question about a chain of primes suppose that k*2^x+1, k*2^(2x+1)+1,k*2^(4x+3)+1.... are prime. How long can this chain can be, and are they rare? 24051981*2^24 + 1 is prime 24051981*2^49 + 1 is prime 24051981*2^99 + 1 is prime 24051981*2^199 + 1 isn't prime so that make that one 3 term long.
2014-01-02, 12:44   #2
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 Originally Posted by firejuggler suppose that k*2^x+1, k*2^(2x+1)+1,k*2^(4x+3)+1.... are prime. How long can this chain can be, and are they rare? 24051981*2^24 + 1 is prime 24051981*2^49 + 1 is prime 24051981*2^99 + 1 is prime 24051981*2^199 + 1 isn't prime so that make that one 3 term long.
What does this have to do with factoring?

You are in the wrong forum.

Problems in Number Theory

Last fiddled with by R.D. Silverman on 2014-01-02 at 12:51 Reason: Added comment

2014-01-02, 16:23   #3
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

31×293 Posts

Quote:
 Originally Posted by firejuggler suppose that k*2^x+1, k*2^(2x+1)+1,k*2^(4x+3)+1.... are prime. How long can this chain can be, and are they rare? 24051981*2^24 + 1 is prime 24051981*2^49 + 1 is prime 24051981*2^99 + 1 is prime 24051981*2^199 + 1 isn't prime so that make that one 3 term long.
http://en.wikipedia.org/wiki/Cunningham_chain

 2014-01-02, 16:52 #4 LaurV Romulan Interpreter     Jun 2011 Thailand 863510 Posts It seems that the "construction" discussed is not a Cunningham chain, as those numbers do not "nearly doubles" every step. From few pari tests, there are plenty of chains in cause for length 6, they are easy to find for small numbers. Couldn't find one for length 7 after about 20 minutes of searching. It may be a modular trick there to show that none exists, or I did not searched enough.:smile: Length seven starts with k=969095 and n=1. It seems they can have arbitrary length. Last fiddled with by LaurV on 2014-01-02 at 16:59
2014-01-02, 17:12   #5
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by LaurV It seems that the "construction" discussed is not a Cunningham chain, as those numbers do not "nearly doubles" every step. From few pari tests, there are plenty of chains in cause for length 6, they are easy to find for small numbers. Couldn't find one for length 7 after about 20 minutes of searching. It may be a modular trick there to show that none exists, or I did not searched enough.:smile: Length seven starts with k=969095 and n=1. It seems they can have arbitrary length.
People should engage their brains BEFORE they start computing.

It is trivial to see that such chains of arbitrary but finite length exist if a
certain very very well known and very much believed conjecture
is true.

2014-01-02, 17:50   #6
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

31×293 Posts

Quote:
 Originally Posted by LaurV It seems that the "construction" discussed is not a Cunningham chain, as those numbers do not "nearly doubles" every step.
True, these are not Cunningham chains, but the same argument as with Cunningham chains applies: they are all finite. (The exponents are a Cunningham chain.)

Anyway, length-8 chain appears at p=209556883, and length-9 chain appears at p=1991589679

Last fiddled with by Batalov on 2014-01-02 at 18:15

2014-01-02, 18:23   #7
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by LaurV It seems that the "construction" discussed is not a Cunningham chain, as those numbers do not "nearly doubles" every step.
When are you going to stop prattling?

Most of the time when you try to discuss mathematics you say something
stupid.

These numbers certainly do "nearly double" every step. Or did you fail to take (or pass) first year secondary school algebra?

And this sequence most definitely IS a Cunningham chain. (of the second
kind)

2014-01-02, 18:54   #8
CRGreathouse

Aug 2006

22×32×163 Posts

Quote:
 Originally Posted by R.D. Silverman It is trivial to see that such chains of arbitrary but finite length exist if a certain very very well known and very much believed conjecture is true.
You refer, I suppose, to Dickson's conjecture?

2014-01-02, 19:11   #9
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by CRGreathouse You refer, I suppose, to Dickson's conjecture?
Also, the k-tuples conjecture. And Schinzel's conjecture. And the Bateman-Horn conjecture.

 2014-01-03, 00:21 #10 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 215738 Posts Length-10 fire-chain starts with 16115712390779. 8057856195389*2^(2^k-1)+1, 1<=k<=10. Code: 16115712390779 64462849563113 1031405593009793 264039831810506753 17304114417533370499073 74320605509547915282165438349313 1370973189237758456882189649193509622387878702088193 466518001818972126590484055297138550142720146550254423311785848574622370435037312216727553 54019094097436859658969629732306068413914220877860574426388607800345512773832031510172556937535694515382891590803380241493774418701828974532859206254646507553970716673 724277638207929266930253555137584980350438559225752130475243057017776657731820280872850742890001087060442445989121458534781350925486567003466887539158918517589176487344301914058802900339316416322436412544887150584702148836067366128236669774778238376700909967366375371470590291086953424789414347049137985049179149421248513
 2014-01-03, 00:55 #11 firejuggler     Apr 2010 Over the rainbow 2·3·5·79 Posts Thank you Batalov and Laurv for those example. Now , an important question : Can any of those number Fermat factors? Last fiddled with by firejuggler on 2014-01-03 at 01:06

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 3 2017-08-10 13:47 emily Math 34 2017-07-16 18:44 Unregistered Information & Answers 0 2011-01-31 15:41 cipher Math 1 2009-09-01 15:12 troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 10:42.

Tue Aug 11 10:42:34 UTC 2020 up 25 days, 6:29, 1 user, load averages: 1.64, 1.84, 1.89