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.

***

 Records   |  Conjectures  |  Problems  |  Puzzles