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 (prp test)
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 < 2.2*10^17*(2^61-1) |
no
factor: 1328165573307087715777 |
|
... |
... |
... |
... |
|
170141183460469231731687303715884105727 |
yes (-1) |
unknown
no factor < 1.45*10^17*(2^127-1) |
no
factor:
886407410000361345663448535540258622490179142922169401 |
***
|
