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 base3 Fermat test with a simpler test by using the
fact that if 3^((2^p+1)/31) = 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 (P1 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^611) 
no
factor: 1328165573307087715777 
... 
... 
... 
... 
170141183460469231731687303715884105727 
yes (1) 
unknown
no factor < 1.45*10^17*(2^1271) 
no
factor:
886407410000361345663448535540258622490179142922169401 
***
