mersenneforum.org > Math Mersenne prime in a Cunningham chain
 Register FAQ Search Today's Posts Mark Forums Read

 2020-05-17, 07:39 #1 JeppeSN     "Jeppe" Jan 2016 Denmark 2338 Posts Mersenne prime in a Cunningham chain Often when a Mersenne prime M = 2^p - 1 is found, we check also the numbers M - 2 (twin), (M + 2)/3 (Wagstaff) and M*(M + 1)/2 + 1 (right perfect) to make sure M does not have a "companion" prime. In this message, I suggest we check one companion extra, namely 2*M - 1. Because M is prime, it would be possible to do a deterministic test of 2*M - 1, even if the canonical form of 2*M - 1does not reveal it: 2*M - 1 = 2^{p+1} - 3 Because of simple modulo 3 considerations, M cannot be a Sophie Germain prime or a safe prime, because 3 always divides 2*M + 1 and (M - 1)/2 (except for trivial initial examples), so we do not need to check them. And (M + 1)/2 is a power of two. So 2*M - 1 is the only relevant candidate for a Cunningham chain. Here is the status so far: Code:  p: factor of 2^{p+1} - 3 ---------------------------------- 2: prime 3: prime 5: prime 7: 11 13: prime 17: 11 19: prime 31: 9241 61: 37 89: 1823 107: 11 127: 11 521: 193 607: 11 1279: 98807 2203: 47 2281: 131 3217: 11 4253: 23 4423: 313 9689: composite 9941: 419303 11213: composite 19937: 11 21701: composite 23209: 37 44497: 11 86243: 6553 110503: 313 132049: composite 216091: 23 756839: 757 859433: 193 1257787: 11 1398269: 96997 2976221: 1451 3021377: 11 6972593: 103869349 13466917: 11 20996011: 86183 24036583: 59 25964951: 76382783 30402457: 11 32582657: 11 37156667: 11 42643801: 38334482051 43112609: 59 57885161: 193 74207281: unknown! 77232917: 11 82589933: 37463 Of course it would be interesting to resolve the unknown case. More factoring attempts will be needed. A PRP test would take very long. As I said, a deterministic test is possible in principle. It would also be interesting to find factors in the cases where the table above says only "composite". I have submitted all the relevant numbers to factordb.com. /JeppeSN
 2020-05-17, 10:26 #2 JeppeSN     "Jeppe" Jan 2016 Denmark 5×31 Posts Found a factor of one of them: Code:  p: factor of 2^{p+1} - 3 ---------------------------------- 2: prime 3: prime 5: prime 7: 11 13: prime 17: 11 19: prime 31: 9241 61: 37 89: 1823 107: 11 127: 11 521: 193 607: 11 1279: 98807 2203: 47 2281: 131 3217: 11 4253: 23 4423: 313 9689: 289935200473 9941: 419303 11213: composite 19937: 11 21701: composite 23209: 37 44497: 11 86243: 6553 110503: 313 132049: composite 216091: 23 756839: 757 859433: 193 1257787: 11 1398269: 96997 2976221: 1451 3021377: 11 6972593: 103869349 13466917: 11 20996011: 86183 24036583: 59 25964951: 76382783 30402457: 11 32582657: 11 37156667: 11 42643801: 38334482051 43112609: 59 57885161: 193 74207281: unknown! 77232917: 11 82589933: 37463 /JeppeSN
 2020-05-17, 17:36 #3 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 3·101 Posts 2^11214-3 has a factor: 1796673824281091446021443177301 2^21702-3 has a factor: 22313687645759
2020-05-17, 18:02   #4
JeppeSN

"Jeppe"
Jan 2016
Denmark

15510 Posts

Quote:
 Originally Posted by kruoli 2^11214-3 has a factor: 1796673824281091446021443177301 2^21702-3 has a factor: 22313687645759
Impressive. Can they be guaranteed to be minimal?

Only one composite without known factor, and one for which it is not known if it is prime or not. Updating:
Code:
        p:  factor of 2^{p+1} - 3
----------------------------------
2:  prime
3:  prime
5:  prime
7:  11
13:  prime
17:  11
19:  prime
31:  9241
61:  37
89:  1823
107:  11
127:  11
521:  193
607:  11
1279:  98807
2203:  47
2281:  131
3217:  11
4253:  23
4423:  313
9689:  289935200473
9941:  419303
11213:  1796673824281091446021443177301
19937:  11
21701:  22313687645759
23209:  37
44497:  11
86243:  6553
110503:  313
132049:  composite
216091:  23
756839:  757
859433:  193
1257787:  11
1398269:  96997
2976221:  1451
3021377:  11
6972593:  103869349
13466917:  11
20996011:  86183
24036583:  59
25964951:  76382783
30402457:  11
32582657:  11
37156667:  11
42643801:  38334482051
43112609:  59
57885161:  193
74207281:  unknown!
77232917:  11
82589933:  37463
/JeppeSN

Last fiddled with by JeppeSN on 2020-05-17 at 18:03

2020-05-17, 18:23   #5
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

12F16 Posts

Just found 2^132050-3 is divisible by 593818027643.

Quote:
 Originally Posted by JeppeSN Can they be guaranteed to be minimal?
No, I found all factors with ECM. Do you need minimal factors?

 2020-05-17, 19:54 #6 ATH Einyen     Dec 2003 Denmark 3×11×89 Posts The 5 chains are only length 2. The next steps 2p+2 - 7 are composite and the first 4 of them are square numbers: p=2: 2p+2 - 7 = 32 p=3: 2p+2 - 7 = 52 p=5: 2p+2 - 7 = 112 p=13: 2p+2 - 7 = 1812 p=19: 2p+2 - 7 = 5*419429
 2020-05-17, 20:59 #7 JeppeSN     "Jeppe" Jan 2016 Denmark 100110112 Posts Updated with the latest factor from kruoli. The only pending is 2^74207282 - 3. The same one that causes trouble with right perfect primes. For the largest factors, there is no guarantee they are minimal. Code:  p: factor of 2^{p+1} - 3 ---------------------------------- 2: prime 3: prime 5: prime 7: 11 13: prime 17: 11 19: prime 31: 9241 61: 37 89: 1823 107: 11 127: 11 521: 193 607: 11 1279: 98807 2203: 47 2281: 131 3217: 11 4253: 23 4423: 313 9689: 289935200473 9941: 419303 11213: 1796673824281091446021443177301 19937: 11 21701: 22313687645759 23209: 37 44497: 11 86243: 6553 110503: 313 132049: 593818027643 216091: 23 756839: 757 859433: 193 1257787: 11 1398269: 96997 2976221: 1451 3021377: 11 6972593: 103869349 13466917: 11 20996011: 86183 24036583: 59 25964951: 76382783 30402457: 11 32582657: 11 37156667: 11 42643801: 38334482051 43112609: 59 57885161: 193 74207281: unknown! 77232917: 11 82589933: 37463
2020-05-17, 21:07   #8
JeppeSN

"Jeppe"
Jan 2016
Denmark

2338 Posts

Quote:
 Originally Posted by ATH The 5 chains are only length 2. The next steps 2p+2 - 7 are composite and the first 4 of them are square numbers: p=2: 2p+2 - 7 = 32 p=3: 2p+2 - 7 = 52 p=5: 2p+2 - 7 = 112 p=13: 2p+2 - 7 = 1812 p=19: 2p+2 - 7 = 5*419429
Yes, I wonder if there is any explanation why the four of them are prime squares. Apparently not. I did check that 2^74207283 - 7 is not a square, ha ha.

Edit: It has been proved that 2^{p+2} - 7 is never going to be square again.

/JeppeSN

Last fiddled with by JeppeSN on 2020-05-17 at 21:36

2020-05-18, 02:39   #9
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by JeppeSN Yes, I wonder if there is any explanation why the four of them are prime squares. Apparently not. I did check that 2^74207283 - 7 is not a square, ha ha. Edit: It has been proved that 2^{p+2} - 7 is never going to be square again. /JeppeSN
Do people not understand the difference between math and numerology?

 2020-05-18, 03:56 #10 ATH Einyen     Dec 2003 Denmark 293710 Posts Maybe some of us like "numerology". The whole GIMPS project is really "numerology" as well as filling out the Cunningham Tables. Unless we find so many Mersenne Primes that the theory of the distribution of Mersenne Primes needs to be altered.
2020-05-18, 12:58   #11
Dr Sardonicus

Feb 2017
Nowhere

23×433 Posts

Quote:
Originally Posted by R.D. Silverman
Quote:
 Originally Posted by JeppeSN Yes, I wonder if there is any explanation why the four of them are prime squares. Apparently not. I did check that 2^74207283 - 7 is not a square, ha ha. Edit: It has been proved that 2^{p+2} - 7 is never going to be square again. /JeppeSN
Do people not understand the difference between math and numerology?
According to the references in the link, the Diophantine equation

2n - 7 = x2

is called Ramanujan's square equation. He posed the question of whether it has any solutions for n > 15 in 1913.

So I guess you're asking, did he understand the difference between math and numerology?

 Similar Threads Thread Thread Starter Forum Replies Last Post firejuggler Math 31 2014-01-08 18:28 kosta Factoring 24 2013-03-21 07:17 Raman Cunningham Tables 32 2012-07-10 22:27 cipher Math 1 2009-09-01 15:12 olivier_latinne Math 54 2008-03-12 10:04

All times are UTC. The time now is 11:56.

Thu Sep 24 11:56:56 UTC 2020 up 14 days, 9:07, 0 users, load averages: 3.51, 2.44, 1.94