View Single Post
Old 2020-05-17, 07:39   #1
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2168 Posts
Cool 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
JeppeSN is offline   Reply With Quote