mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-05-17, 07:39   #1
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

5×23 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
Old 2020-05-17, 10:26   #2
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

5×23 Posts
Default

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
JeppeSN is offline   Reply With Quote
Old 2020-05-17, 17:36   #3
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

24·11 Posts
Default

2^11214-3 has a factor: 1796673824281091446021443177301
2^21702-3 has a factor: 22313687645759
kruoli is offline   Reply With Quote
Old 2020-05-17, 18:02   #4
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

5·23 Posts
Thumbs up

Quote:
Originally Posted by kruoli View Post
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
JeppeSN is offline   Reply With Quote
Old 2020-05-17, 18:23   #5
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

24·11 Posts
Default

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

Quote:
Originally Posted by JeppeSN View Post
Can they be guaranteed to be minimal?
No, I found all factors with ECM. Do you need minimal factors?
kruoli is offline   Reply With Quote
Old 2020-05-17, 19:54   #6
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

285010 Posts
Default

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
ATH is offline   Reply With Quote
Old 2020-05-17, 20:59   #7
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

5·23 Posts
Default

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 is offline   Reply With Quote
Old 2020-05-17, 21:07   #8
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

7316 Posts
Default

Quote:
Originally Posted by ATH View Post
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
JeppeSN is offline   Reply With Quote
Old 2020-05-18, 02:39   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

32×827 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
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?
R.D. Silverman is offline   Reply With Quote
Old 2020-05-18, 03:56   #10
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×3×52×19 Posts
Default

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.
ATH is offline   Reply With Quote
Old 2020-05-18, 12:58   #11
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×23×71 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Quote:
Originally Posted by JeppeSN View Post
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?
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 23:13.

Thu Jul 2 23:13:41 UTC 2020 up 99 days, 20:46, 1 user, load averages: 1.18, 1.29, 1.38

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.