Problems & Puzzles: Conjectures

Conjecture 15.-  The New Mersenne Conjecture.

Landon Curt Noll recalled my attention to the Bateman, Selfridge and Wagstaff (The so called 'New Mersenne') conjecture, that goes as follow:

Let p be any odd natural number. If two of the following conditions hold, then so does the third:

1) p = 2^k +/- 1   or   p = 4^k +/- 3

2) 2^p - 1 is a prime

3) (2^p + 1)/3 is a prime

See: http://orca.st.usm.edu/~cwcurry/NMC.html by Conrad Curry for the most recent status of this conjecture.

According to this link the smaller p  for which the conjecture is still pending is p = 1048573 *. More properly, is undecided the primality character of (2^1048573+1)/3 that is to say, no one factor is known and no primality test is known to have been done. Any of these results are important because:

 If (2^1048573+1)/3 is prime then the conjecture is false. If (2^1048573+1)/3 is composite then the conjecture remains credible.

Given its size, it seems to be easier (?) to get a factor, than probing the primality of (2^1048573+1)/3.

Would you like to get a factor of (2^1048573+1)/3? ( **)

_______
Notes

(*) Other p values in the same trend respect this conjecture are p = 1398269 and p = 6972593

(**) Warut Roonguthai thinks that maybe it's easier to probe the primality of (2^1048573+1)/3, than getting a small factor of it, according to the following lines:

" (23/11/99) Perhaps it'd be much easier to check if 3^(2^1048573) = 9 (mod 2^1048573+1) than to check if (2^1048573+1)/3 is an Euler PRP because only pure squaring would be used and reduction modulo 2^1048573+1 is easy...(28/11/99) My idea is to replace the base-3 Fermat test with a simpler test by using the fact that if 3^((2^p+1)/3-1) = 1 (mod (2^p+1)/3), then 3^(2^p) = 9 (mod 2^p+1)....  Note that testing if 3^2^p = 9 (mod 2^p+1) is easier in both powering and reduction and can be implemented with Crandall's DWT."

Solution

Nuutti Kuosa (10/02/2000) verified that (2^1048573+1)/3 is composite using PRIMEFORM.  "It is 315,652 digits long and test took 4 -5 days in my PIII 450". According to an Yves Gallot indication "a verification is needed" in order to discard any error (machine &/or code) during computation.

Then, if the Kuosa's result is verified the NMC remains alive!....

***

Greg Childers wrote (6/7/2001):

"Now that pfgw outputs the lowest 62 bits of the residue when finding a number is composite, verification of a composite result is possible. I've used this to verify Nuutti Kuosa's composite result for (2^1048573+1)/3, one important for the survival of the New Mersenne Conjecture. See this conjecture and here for more details.

I ran PRP tests on this number in pfgw using both the generic FFT code and the new DWT FFT code and verified the residues were the same. Here are the results:

Generic FFT: (2^1048573+1)/3 is composite: [CBE3FC22FAE27F6] (183948.340000 seconds)

DWT FFT: Phi(2097146,2) is composite: [Sig=CBE3FC22FAE27F6] (36405.390000 seconds)

Note the residues are the same while the DWT FFT code is 5 times faster than the generic FFT code. I will now repeat this procedure to verify Henri Lifchitz's composite result for (2^1398269+1)/3."

Then, Warut was right (see above)...

***

Again Gregg Childers wrote, the 27/8/2001:

I have used pfgw to verify Henri Lifchitz's composite result for (2^1398269+1)/3, an unsurprising but necessary result for the survival of the New Mersenne Conjecture.

I ran PRP tests on this number in pfgw using both the generic FFT code and the new DWT FFT code and verified the residues were the same. Here are the results:

Generic FFT: (2^1398269+1)/3 is composite: [183821950F064BF7] (234102.130000 seconds)

DWT FFT: Phi(2796538,2) is composite: [Sig=183821950F064BF7] (42715.940000 seconds)

Note the residues are the same while the DWT FFT code is over 5 times faster than the generic FFT code. The calculation was completed on a 1.2 GHz Athlon.

***

Richard Chen wrote on June 21, 2021:

Now the new Mersenne conjecture has been verified for all primes p <= 1073741826
Currently status:

 p p=2^k +/- 1 or p=4^k +/- 3 2^p - 1 prime (2^p + 1)/3 prime 3 yes (-1) yes yes 5 yes (+1) yes yes 7 yes (-1/+3) yes yes 11 no no factor: 23 yes 13 yes (-3) yes yes 17 yes (+1) yes yes 19 yes (+3) yes yes 23 no no factor: 47 yes 31 yes (-1) yes yes 43 no no factor: 431 yes 61 yes (-3) yes yes 67 yes (+3) no factor: 193707721 no factor: 7327657 79 no no factor: 2687 yes 89 no yes no factor: 179 101 no no factor: 7432339208719 yes 107 no yes no factor: 643 127 yes (-1) yes yes 167 no no factor: 2349023 yes 191 no no factor: 383 yes 199 no no factor: 164504919713 yes 257 yes (+1) no factor: 535006138814359 no factor: 37239639534523 313 no no factor: 10960009 yes 347 no no factor: 14143189112952632419639 yes 521 no yes no factor: 501203 607 no yes no factor: 115331 701 no no factor: 796337 yes 1021 yes (-3) no factor: 40841 no factor: 10211 1279 no yes no factor: 706009 1709 no no factor: 379399 yes 2203 no yes no factor: 13219 2281 no yes no factor: 22811 2617 no no factor: 78511 yes 3217 no yes no factor: 7489177 3539 no no factor: 7079 yes 4093 yes (-3) no factor: 2397911088359 no factor: 3732912210059 4099 yes (+3) no factor: 73783 no factor: 2164273 4253 no yes no factor: 118071787 4423 no yes no factor: 2827782322058633 5807 no no factor: 139369 yes 8191 yes (-1) no factor: 338193759479 no (prp test) no factor (P-1 B1=10^10 B2=10^12) 9689 no yes no factor: 19379 9941 no yes no factor: 11120148512909357034073 10501 no no factor: 2160708549249199 yes 10691 no no factor: 21383 yes 11213 no yes no factor: 181122707148161338644285289935461939 11279 no no factor: 2198029886879 yes 12391 no no factor: 198257 yes 14479 no no factor: 27885728233673 yes 16381 yes (-3) no no factor < 2^64 (ECM t=45digits) no factor: 163811 19937 no yes no (prp test) no factor < 2^59 (ECM t=50digits) 21701 no yes no factor: 43403 23209 no yes no factor: 4688219 42737 no no factor: 542280975142237477071005102443059419300063 yes 44497 no yes no factor: 2135857 65537 yes (+1) no factor: 513668017883326358119 no factor: 13091975735977 65539 yes (+3) no factor: 3354489977369 no factor: 58599599603 83339 no no factor: 166679 yes (prp) 86243 no yes no factor: 1627710365249 95369 no no factor: 297995890279 yes (prp) 110503 no yes no factor: 48832113344350037579071829046935480686609 117239 no no no factor < 2^65 (ECM t=35digits) yes (prp) 127031 no no factor: 12194977 yes (prp) 131071 yes (-1) no factor: 231733529 no factor: 2883563 132049 no yes no factor: 618913299601153 138937 no no factor: 100068818503 yes (prp) 141079 no no factor: 458506751 yes (prp) 216091 no yes no factor: 10704103333093885136919332089553661899 262147 yes (+3) no factor: 268179002471 no factor: 4194353 267017 no no factor: 1602103 yes (prp) 269987 no no factor: 1940498230606195707774295455176153 yes (prp) 374321 no no no factor < 2^65 (ECM t=35digits) yes (prp) 524287 yes (+1) no factor: 62914441 no (prp test) no factor < 2^70 756839 no yes no factor: 1640826953 859433 no yes no factor: 1718867 986191 no no no factor < 2^67 (ECM t=35digits) yes (prp) 1048573 yes (-3) no factor: 73400111 no (prp test) no factor < 2^70 1257787 no yes no factor: 20124593 1398269 no yes no factor: 23609117451215727502931 2976221 no yes no factor: 434313978089 3021377 no yes no factor: 95264016811 4031399 no no factor: 8062799 yes (prp) 4194301 yes (-3) no factor: 2873888432993463577 no factor: 14294177809 6972593 no yes no factor: 142921867730820791335455211 13347311 no no factor: 26694623 yes (prp) 13372531 no no factor: 451135705817 yes (prp) 13466917 no yes no factor: 781081187 16777213 yes (-3) no no factor < 2^75 no factor: 68470872139190782171 20996011 no yes no factor: 50965926368055564259063193 24036583 no yes no factor: 11681779339 25964951 no yes no factor: 155789707 30402457 no yes no (prp test) no factor < 2^70 (ECM t=25digits) 32582657 no yes no factor: 13526662966442476828963 37156667 no yes no factor: 297253337 42643801 no yes no factor: 405661842777846034141594389769 43112609 no yes no factor: 86225219 57885161 no yes no factor: 7061989643 74207281 no yes no (prp test) no factor < 2^79 (ECM t=25digits) 77232917 no yes no factor: 3460697185562027 82589933 no yes no (prp test) no factor < 2^80 268435459 yes (+3) no factor < 2^83 no factor: 414099276471761 1073741827 yes (+3) no factor: 16084529043983099051873383 unknown no factor < 2^84 2147483647 yes (-1) no factor: 295257526626031 unknown no factor < 2^86 2305843009213693951 yes (-1) unknown no factor: 1328165573307087715777 ... ... ... ... 170141183460469231731687303715884105727 yes (-1) unknown no factor: 886407410000361345663448535540258622490179142922169401

*** Records   |  Conjectures  |  Problems  |  Puzzles  Home | Melancholia | Problems & Puzzles | References | News | Personal Page | Puzzlers | Search | Bulletin Board | Chat | Random Link Copyright © 1999-2012 primepuzzles.net. All rights reserved.