mersenneforum.org  

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

Reply
 
Thread Tools
Old 2014-01-02, 11:15   #1
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

24×3×72 Posts
Default 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.
firejuggler is offline   Reply With Quote
Old 2014-01-02, 12:44   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

2·3·17·73 Posts
Default

Quote:
Originally Posted by firejuggler View Post
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.

And yes, your question can be answered. Read Richard Guy's Book: Unsolved
Problems in Number Theory

Last fiddled with by R.D. Silverman on 2014-01-02 at 12:51 Reason: Added comment
R.D. Silverman is online now   Reply With Quote
Old 2014-01-02, 16:23   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

5·1,811 Posts
Default

Quote:
Originally Posted by firejuggler View Post
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
Batalov is offline   Reply With Quote
Old 2014-01-02, 16:52   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

52·73 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2014-01-02, 17:12   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164268 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
R.D. Silverman is online now   Reply With Quote
Old 2014-01-02, 17:50   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

5×1,811 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
Batalov is offline   Reply With Quote
Old 2014-01-02, 18:23   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

2·3·17·73 Posts
Default

Quote:
Originally Posted by LaurV View Post
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)
R.D. Silverman is online now   Reply With Quote
Old 2014-01-02, 18:54   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

16E616 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?
CRGreathouse is offline   Reply With Quote
Old 2014-01-02, 19:11   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

2·3·17·73 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
You refer, I suppose, to Dickson's conjecture?
Also, the k-tuples conjecture. And Schinzel's conjecture. And the Bateman-Horn conjecture.
R.D. Silverman is online now   Reply With Quote
Old 2014-01-03, 00:21   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

5·1,811 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2014-01-03, 00:55   #11
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

24·3·72 Posts
Default

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
firejuggler is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 3 2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
A conjecture about Mersenne primes and non-primes Unregistered Information & Answers 0 2011-01-31 15:41
Calculation for Cunningham Chain 2nd Kind. cipher Math 1 2009-09-01 15:12
possible primes (real primes & poss.prime products) troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 14:26.

Fri Jul 3 14:26:25 UTC 2020 up 100 days, 11:59, 1 user, load averages: 1.72, 1.90, 1.91

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.