Sieving freakishly big MMs (was "World record" phone number?)

[philmoore]

Originally Posted by ewmayer

1257787: k = 8,29,48,53,84,92,93,113,149,168,212,228,249,308,348,420,425,504,540,569,572,573,600,665,684,729,785,809,812,849,872,888,893
1398269: k = 5,44,68,93,140,180,236,240,248,273,293,296,356,453,521,545,549,560,608,609,644,684,713,720,728,753,824,849,861,909,968
2976221: k = 56,80,84,96,144,153,164,245,248,264,296,381,441,461,465,501,509,528,536,668,681,749,756,780,788,909,956,996
3021377: k = 44,60,81,104,105,116,189,245,249,264,333,341,345,420,440,480,548,564,608,609,641,653,660,669,768,888,905,941,944,980
6972593: k = 5,24,68,89,96,101,153,168,185,285,329,336,369,408,453,465,468,473,485,521,593,629,648,720,741,749,809,840,860,884,929,948,956
13466917: k = 8,69,89,93,96,125,128,168,204,209,221,225,233,264,324,348,368,380,413,440,453,473,476,524,540,576,629,644,653,660,728,804,821,876,896,909,944,953,960,984
20996011: k = 8,113,224,249,272,300,333,348,425,429,477,485,564,569,608,645,657,680,740,837,849,893,900
24036583: k = 8,12,48,65,68,113,125,152,209,212,285,305,308,393,404,473,485,488,497,533,573,593,617,669,672,708,728,768,824,833
25964951: k = 45,68,164,168,177,180,257,305,332,369,389,429,432,444,473,488,537,552,593,597,608,648,657,660,672,713,752,780,812,828,893,917,944,980
30402457: k = 41,89,96,113,116,156,173,176,216,261,264,273,288,309,320,389,456,468,476,525,533,573,581,608,629,641,644,701,716,720,744,765,809,816,896,965,993
32582657: k = 20,44,60,108,140,216,221,273,276,305,324,353,356,413,429,453,489,513,528,576,600,608,716,720,761,809,849,860,884,921,944,980
37156667: k = 24,44,48,77,80,104,168,173,212,233,308,324,332,368,405,429,437,468,480,524,525,537,552,557,569,600,605,684,693,713,753,777,828,864,917,944
42643801: k = 33,44,69,96,189,221,233,285,293,345,369,380,393,428,441,468,485,504,509,624,648,716,740,744,749,768,813,816,833,873,876,924,996
43112609: k = 5*,185,200*,201,216*,233,273,384*,401*,429*,513,521,560,593,600*,656,660,665*,668,669*,684,713,753,800,809,860,888,933*,944,965

* = Since proven composite via deeper sieving to 1e11.

If I recall correctly, the results I posted on Will's web-page involved sieving each exponent from 2976221 to 30402457 up to 2^31. I probably have the factors I found somewhere around here, Ernst, although because of a hard-drive failure a few years ago, it may be in the form of a "printout", an antiquated form of storage frequently used in the 20th century.

[axn]

Originally Posted by philmoore

the results I posted on Will's web-page involved sieving each exponent from 2976221 to 30402457 up to 2^31.

Is that k <= 2^31 (in which case, how deep was it sieved) or sieved up to 2^31 (in which case, what was the k range)?

[LaurV]

Sorry for the delay, no free time, I just found a bit of time during lunch break but I could not access the computer (remoting to my house, I think out IT dept did something with the firewall or the servers during the lunch).

Now I got it. The k's which were eliminated in my table were:

#34:  1257787: k = 149,249,504,600,785,872
#35:  1398269: k = 180,240,248,273,609,849
#36:  2976221: k = 56,528,996
#37:  3021377: k = 81,333,420,608,660
#38:  6972593: k = 68,185,336,369,453,741,884,956
#39: 13466917: k = 69,93,96,476,576,653,953
#40: 20996011: k = 113,272,657,740
#41: 24036583: k = 113
#42: 25964951: k = 164,473,657,713,893,944
#43: 30402457: k = 176,261,273,288,641,744
#44: 32582657: k = 44,221,273,453,489,576,720,944,980
#45: 37156667: k = 524,693,713,944
#46: 42643801: k = 44,221,393,428,744
#47: 43112609: k = none

This list is "have factors between 32M and 1G", they have to be asterisked in - or eliminated from - ewmayer's table. Their factors (except for #46,k=44, whose factor is between 1G and 4G) are:

#34,149 has a factor : 306852607
#34,249 has a factor : 41338111
#34,504 has a factor : 91596737
#34,600 has a factor : 135549677
#34,785 has a factor : 57979847
#34,872 has a factor : 370969009

#35,180 has a factor : 452535697
#35,240 has a factor : 150051247
#35,248 has a factor : 60082859
#35,273 has a factor : 234717979
#35,609 has a factor : 585942169
#35,849 has a factor : 352875203

#36, 56 has a factor : 147547391
#36,528 has a factor : 41221249
#36,996 has a factor : 646207649

#37, 81 has a factor : 76165591
#37,333 has a factor : 427066817
#37,420 has a factor : 411433669
#37,608 has a factor : 33456589
#37,660 has a factor : 809870977

#38, 68 has a factor : 34411649
#38,185 has a factor : 386501543
#38,336 has a factor : 439589651
#38,369 has a factor : 738469559
#38,453 has a factor : 36832979
#38,741 has a factor : 896870687
#38,884 has a factor : 45868327
#38,956 has a factor : 58198181

#39, 69 has a factor : 119370001
#39, 93 has a factor : 33674209
#39, 96 has a factor : 194242183
#39,476 has a factor : 203942419
#39,576 has a factor : 307063187
#39,653 has a factor : 333708901
#39,953 has a factor : 565776451

#40,113 has a factor : 33208589
#40,272 has a factor : 227322647
#40,657 has a factor : 33082001
#40,740 has a factor : 108790961

#41,113 has a factor : 492502253

#42,164 has a factor : 168153533
#42,473 has a factor : 47613217
#42,657 has a factor : 67042249
#42,713 has a factor : 88283473
#42,893 has a factor : 601958087
#42,944 has a factor : 60004817

#43,176 has a factor : 72848761
#43,261 has a factor : 127585477
#43,273 has a factor : 297084287
#43,288 has a factor : 193964599
#43,641 has a factor : 542210323
#43,744 has a factor : 479934337

#44, 44 has a factor : 415021787
#44,221 has a factor : 77249351
#44,273 has a factor : 994172791
#44,453 has a factor : 120304357
#44,489 has a factor : 138744079
#44,576 has a factor : 33481247
#44,720 has a factor : 231810473
#44,944 has a factor : 101857159
#44,980 has a factor : 220184941

#45,524 has a factor : 53040683
#45,693 has a factor : 232066663
#45,713 has a factor : 177675227
#45,944 has a factor : 101350111

#46, 44,   tested to : 1000000007, no factor.
#46,221 has a factor : 161362987
#46,428 has a factor : 514204841
#46,744 has a factor : 85648273
#46,393 has a factor : 421524893

[ET_]

Nice job, folks, thank you very much!

The DB for this search is ready, I will work out some online tables during the weekend (or even earlier, if I find time), so that everyone will have a clear idea of who is doing what at which level...

@Ernst, thank you for the ks; your software is great as is, no need to continue sieving after a factor is found.

@Phil, thank you for the information about your sieving work.

@LaurV, M#42 and M#46 have been checked up to 10G, five k have been cleared, I collected the factors for double-checks. M#47 is being taken to 1T. I am attaching your table with my extensions here, please confirm or correct your claimed ranges .

I will work on automatic reservation system as I get started with the tables management.

BTW, any ideas for a name of this sieving project?

Luigi

[aketilander]

I am following this discussion with great interest. Sorry for draging it down to a basic level and at the same time exploring my ignorance , so if I may I would like to ask a few basic questions, just making sure that I have understood what it is all about,

1. So what you are doing right now is to sieve to find possible candidates that might divide the very large double mersennes MM#34 - MM#47. What you find is possible candidates that might divide MM#34 - MM#47 respectively. Is that rignt?

2. So when you are speaking of "factors" you are not speaking of factors of the double mersennes but factors of the possible candidates which have the form 2*k*[M#34-M#47]+1 for different k:s. Is that right? So it is rather factors of possible factors and these factors of factors do not have any special form known?

3. And the reason why you are not using the candidates found for TF of MM#34-MM#47 is that these numbers are so increadibly large that, presently there is no program available that could do such a TF. Is that right?

4. And if you find a factor of MM#47 that factor would be larger then M#47 hence the largest prime found? Is that right?

Once again sorry for asking these basic questions!

[LaurV]

Originally Posted by aketilander

3. And the reason why you are not using the candidates found for TF of MM#34-MM#47 is that these numbers are so increadibly large that, presently there is no program available that could do such a TF. Is that right?

You got it all right, except number 3. Doing a TF for a double mersenne, you have to compute mod , which is equivalent to raise 2^(2^p) and check if this is 2 (mod q). This means you have to, in fact, take x=2, and square it p times, mod q. Many programs can do that, including P95, but the time involved would be the same amount of time as LL-ing Mp (is exactly the same type and amount of computation like a LL test, the modulus q has just few bits more then Mp, when we do mod Mp on a "clasic" LL test).

i.e. to LL any M_p (the job we normally do for GIMPS), you start with s₀=4 and do s_n+1=s_n²-2 (mod M_p), p-2 times

otoh, to test if 2*k*M_p+1 divides MM_p, you start with s₀=2 and do s_n+1=s_n² (mod 2*k*M_p+1), exactly p times (so there are two more iterations), and the mod is just few bits (for a small k) bigger then M_p (taking about the same time, in fact).

The time will be the same like doing LL test for exponent p (about).

[LaurV]

A small observation about question 4 (deliberately a separate post, do be easy visible, and not lost in the TL;DR text of the former post):

If we find a factor q=2*k*M#47+1 of MM#47, for such a small k [in fact for ANY k smaller than or equal to (M#47+2)], that number q will be higher then 2*M#47+1 (in fact, larger than, or equal to 2*185*M#47+1).

And that factor q will be PRIME.

And it will be for the first time in a VERY LONG history when the LARGEST KNOWN PRIME is not a mersenne number.

[aketilander]

Originally Posted by LaurV

And that factor q will be PRIME.

And it will be for the first time in a VERY LONG history when the LARGEST KNOWN PRIME is not a mersenne number.

That would indeed be sensational!!!

[ET_]

Originally Posted by philmoore

If I recall correctly, the results I posted on Will's web-page involved sieving each exponent from 2976221 to 30402457 up to 2^31. I probably have the factors I found somewhere around here, Ernst, although because of a hard-drive failure a few years ago, it may be in the form of a "printout", an antiquated form of storage frequently used in the 20th century.

How many k did you sieve up to 2^31, per exponent?

Luigi

[ewmayer]

Originally Posted by LaurV

You got it all right, except number 3. Doing a TF for a double mersenne, you have to compute mod , which is equivalent to raise 2^(2^p) and check if this is 2 (mod q). This means you have to, in fact, take x=2, and square it p times, mod q. Many programs can do that, including P95, but the time involved would be the same amount of time as LL-ing Mp (is exactly the same type and amount of computation like a LL test, the modulus q has just few bits more then Mp, when we do mod Mp on a "clasic" LL test).

i.e. to LL any M_p (the job we normally do for GIMPS), you start with s₀=4 and do s_n+1=s_n²-2 (mod M_p), p-2 times

otoh, to test if 2*k*M_p+1 divides MM_p, you start with s₀=2 and do s_n+1=s_n² (mod 2*k*M_p+1), exactly p times (so there are two more iterations), and the mod is just few bits (for a small k) bigger then M_p (taking about the same time, in fact).

The time will be the same like doing LL test for exponent p (about).

You got the gist of it right, but the work estimate is an order of magnitude too optimistic, because there is no fast DWT-method for multiply modulo such candidate factors, as there is for the multiply modulo Mp used in LL testing, and p-1/ecm done on Mp. As a result one must do a generalized modmul. In my code - which does not yet have the FFT-enabled versions of all these needed to do this efficiently on the really big M(Mp) - I use a Montgomery-mul-based modpow algorithm, which needs not 1 bignum MUL (as for LL) but 3 MUL operations, as detailed on p.3 of the draft manuscript I posted in this Math forum thread. The only part of that MUL sequence which permits optimization beyond general FFT-based MUL is the final UMULH_b(q, lo), which can take advantage of the special form of q for double-Mersennes to achieve the result with just some shift/add/scalar-mul work. So the best one could hope to achieve is a per-powering-bit time perhaps 3-5x longer than the per-iteration time for LL run on the same Mp.

Also note - and I don't mean to damp folks' enthusiasm here, just to set realistic expectations - that for the kinds of M(Mp) we're discussing here, the fact that a given candidate q has no factors below (say) 10^15 or even ~10^20 (probabilistically, if one follows the TF with p-1 and/or ecm) only slightly increases the odds of q being prime, from [a very small number] to perhaps 2 or 3 times [a very small number]. Of course such a find would be spectacular, and one does not improve the methods available for attempting such a feat by giving up because the odds seem to be so daunting. One can learn much from failed attempts, if one approaches such projects from an algorithmic-improvement perspective, rather than one of "my life will only have meaning if this succeeds".

---------------------------

p.s. to Luigi: My run of MM#47(k=185) is to 10T, not 1T. (97% complete as I write this, odds of finding a factor in the final 3% very small). If folks want to do this one very deeply, I suggest divvying up the range 10-100T into 9 10T-sized chunks and handing those out to people interested in asssigning 1 or more CPU to the task.

[ET_]

Originally Posted by ewmayer

---------------------------

p.s. to Luigi: My run of MM#47(k=185) is to 10T, not 1T. (97% complete as I write this, odds of finding a factor in the final 3% very small). If folks want to do this one very deeply, I suggest divvying up the range 10-100T into 9 10T-sized chunks and handing those out to people interested in asssigning 1 or more CPU to the task.

Yes, I have 10T on my scrapboard, thank you.

The idea was indeed to take the first 1000 k that survive low-level sieving to (say) 1T, and then dedicate resources to deep-sieving the first candidate of each row (exponent), in the hope of enhancing our knowledge about the limits of these ranges.

The idea of using 9 ranges of 10T to get to 100T is nice, but risky: if you dedicate your hardware to test 40T-100T, you would not be happy when I will tell you that the factor was hidden on the 10T-20T range.
A different approach could be testing the first candidate of each exponent in parallel to minimize the risk, but then we may not find a record non-Mersenne prime.

Anyway, I don't think there will be much audience for this project, and my worries may as well disappear. Said from the one who launched the Operation Billion Digits with William Lipp.

On another thought, without OBD we would not have had mfaktc...

Luigi