Mersenne prime in a Cunningham chain

JeppeSN · 2020-05-17, 07:39

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

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

/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:

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

kruoli · 2020-05-17, 18:23

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?

ATH · 2020-05-17, 19:54

The 5 chains are only length 2.

The next steps 2^p+2 - 7 are composite and the first 4 of them are square numbers:
p=2: 2^p+2 - 7 = 3²
p=3: 2^p+2 - 7 = 5²
p=5: 2^p+2 - 7 = 11²
p=13: 2^p+2 - 7 = 181²
p=19: 2^p+2 - 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 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

JeppeSN · 2020-05-17, 21:07

Quote:

Originally Posted by ATH

The 5 chains are only length 2.

The next steps 2^p+2 - 7 are composite and the first 4 of them are square numbers:
p=2: 2^p+2 - 7 = 3²
p=3: 2^p+2 - 7 = 5²
p=5: 2^p+2 - 7 = 11²
p=13: 2^p+2 - 7 = 181²
p=19: 2^p+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

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

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?

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:

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

2ⁿ - 7 = x²

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?

2020-05-17, 07:39	#1
JeppeSN "Jeppe" Jan 2016 Denmark 2³·3·7 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 2M - 1. Because M is prime, it would be possible to do a deterministic test of 2M - 1, even if the canonical form of 2M - 1does not reveal it: 2M - 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 2M + 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
question about a chain of primes	firejuggler	Math	31	2014-01-08 18:28
Help wanted, Mersenne base Cunningham numbers	kosta	Factoring	24	2013-03-21 07:17
Cunningham Tables at Mersenne Wiki	Raman	Cunningham Tables	32	2012-07-10 22:27
Calculation for Cunningham Chain 2nd Kind.	cipher	Math	1	2009-09-01 15:12
New Mersenne and Cunningham conjecture	olivier_latinne	Math	54	2008-03-12 10:04

2020-05-17, 17:36	#3
kruoli "Oliver" Sep 2017 Porta Westfalica, DE 539₁₀ Posts	2^11214-3 has a factor: 1796673824281091446021443177301 2^21702-3 has a factor: 22313687645759

2020-05-17, 19:54	#6
ATH Einyen Dec 2003 Denmark 3⁵×13 Posts	The 5 chains are only length 2. The next steps 2^p+2 - 7 are composite and the first 4 of them are square numbers: p=2: 2^p+2 - 7 = 3² p=3: 2^p+2 - 7 = 5² p=5: 2^p+2 - 7 = 11² p=13: 2^p+2 - 7 = 181² p=19: 2^p+2 - 7 = 5*419429

2020-05-18, 03:56	#10
ATH Einyen Dec 2003 Denmark 3⁵×13 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.