mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Mersenne prime in a Cunningham chain (https://www.mersenneforum.org/showthread.php?t=25551)

 JeppeSN 2020-05-17 07:39

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 [URL="https://primes.utm.edu/glossary/page.php?sort=CunninghamChain"]Cunningham chain[/URL].

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
[/CODE]
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

 JeppeSN 2020-05-17 10:26

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
[/CODE]
/JeppeSN

 kruoli 2020-05-17 17:36

2^11214-3 has a factor: 1796673824281091446021443177301
2^21702-3 has a factor: 22313687645759

 JeppeSN 2020-05-17 18:02

[QUOTE=kruoli;545636]2^11214-3 has a factor: 1796673824281091446021443177301
2^21702-3 has a factor: 22313687645759[/QUOTE]
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
[/CODE]
/JeppeSN

 kruoli 2020-05-17 18:23

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

[QUOTE=JeppeSN;545643]Can they be guaranteed to be minimal?[/QUOTE]

No, I found all factors with ECM. Do you need minimal factors?

 ATH 2020-05-17 19:54

The 5 chains are only length 2.

The next steps 2[SUP]p+2[/SUP] - 7 are composite and the first 4 of them are square numbers:
p=2: 2[SUP]p+2[/SUP] - 7 = 3[SUP]2[/SUP]
p=3: 2[SUP]p+2[/SUP] - 7 = 5[SUP]2[/SUP]
p=5: 2[SUP]p+2[/SUP] - 7 = 11[SUP]2[/SUP]
p=13: 2[SUP]p+2[/SUP] - 7 = 181[SUP]2[/SUP]
p=19: 2[SUP]p+2[/SUP] - 7 = 5*419429

 JeppeSN 2020-05-17 20:59

Updated with the latest factor from kruoli.

The only pending is 2^74207282 - 3. The same one that causes trouble with [URL="https://www.mersenneforum.org/showpost.php?p=142828&postcount=10"]right perfect primes[/URL].

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
[/CODE]

 JeppeSN 2020-05-17 21:07

[QUOTE=ATH;545653]The 5 chains are only length 2.

The next steps 2[SUP]p+2[/SUP] - 7 are composite and the first 4 of them are square numbers:
p=2: 2[SUP]p+2[/SUP] - 7 = 3[SUP]2[/SUP]
p=3: 2[SUP]p+2[/SUP] - 7 = 5[SUP]2[/SUP]
p=5: 2[SUP]p+2[/SUP] - 7 = 11[SUP]2[/SUP]
p=13: 2[SUP]p+2[/SUP] - 7 = 181[SUP]2[/SUP]
p=19: 2[SUP]p+2[/SUP] - 7 = 5*419429[/QUOTE]

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: [URL="https://mathworld.wolfram.com/RamanujansSquareEquation.html"]It has been proved[/URL] that 2^{p+2} - 7 is never going to be square again.

/JeppeSN

 R.D. Silverman 2020-05-18 02:39

[QUOTE=JeppeSN;545659]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: [URL="https://mathworld.wolfram.com/RamanujansSquareEquation.html"]It has been proved[/URL] that 2^{p+2} - 7 is never going to be square again.

/JeppeSN[/QUOTE]

Do people not understand the difference between math and numerology?

 ATH 2020-05-18 03:56

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.

 Dr Sardonicus 2020-05-18 12:58

[QUOTE=R.D. Silverman;545681][QUOTE=JeppeSN;545659]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: [URL="https://mathworld.wolfram.com/RamanujansSquareEquation.html"]It has been proved[/URL] that 2^{p+2} - 7 is never going to be square again.

/JeppeSN[/QUOTE]
Do people not understand the difference between math and numerology?[/QUOTE]
According to the references in the link, the Diophantine equation

2[sup]n[/sup] - 7 = x[sup]2[/sup]

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 [i]he[/i] understand the difference between math and numerology?

All times are UTC. The time now is 09:53.