mersenneforum.org Sieving freakishly big MMs (was "World record" phone number?)
 Register FAQ Search Today's Posts Mark Forums Read

2012-10-04, 03:42   #78
philmoore

"Phil"
Sep 2002
Tracktown, U.S.A.

100010111112 Posts

Quote:
 Originally Posted by ewmayer Code: 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.

2012-10-04, 05:53   #79
axn

Jun 2003

527610 Posts

Quote:
 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)?

 2012-10-04, 05:55 #80 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 232268 Posts 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: Code: #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: Code: #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
2012-10-04, 07:14   #81
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2·41·59 Posts

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.

@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
Attached Files
 mmpp.zip (6.6 KB, 139 views)

Last fiddled with by ET_ on 2012-10-04 at 07:16

 2012-10-04, 09:55 #82 aketilander     "Åke Tilander" Apr 2011 Sandviken, Sweden 2·283 Posts Some basic questions 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!
2012-10-04, 10:08   #83
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

987810 Posts

Quote:
 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 $2^{2^p-1}-1$ mod $q=2*k*(2^p-1)+1$, 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 Mp (the job we normally do for GIMPS), you start with s0=4 and do sn+1=sn2-2 (mod Mp), p-2 times

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

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

Last fiddled with by LaurV on 2012-10-04 at 10:18

 2012-10-04, 10:31 #84 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 2×11×449 Posts 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. Last fiddled with by LaurV on 2012-10-04 at 10:47
2012-10-04, 10:59   #85
aketilander

"Åke Tilander"
Apr 2011
Sandviken, Sweden

10668 Posts

Quote:
 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!!!

2012-10-04, 13:32   #86
ET_
Banned

"Luigi"
Aug 2002
Team Italia

10010111001102 Posts

Quote:
 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

2012-10-04, 18:45   #87
ewmayer
2ω=0

Sep 2002
República de California

2DAF16 Posts

Quote:
 Originally Posted by LaurV You got it all right, except number 3. Doing a TF for a double mersenne, you have to compute $2^{2^p-1}-1$ mod $q=2*k*(2^p-1)+1$, 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 Mp (the job we normally do for GIMPS), you start with s0=4 and do sn+1=sn2-2 (mod Mp), p-2 times otoh, to test if 2*k*Mp+1 divides MMp, you start with s0=2 and do sn+1=sn2 (mod 2*k*Mp+1), exactly p times (so there are two more iterations), and the mod is just few bits (for a small k) bigger then Mp (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.

2012-10-04, 19:11   #88
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2·41·59 Posts

Quote:
 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

Last fiddled with by ET_ on 2012-10-04 at 19:11

 Similar Threads Thread Thread Starter Forum Replies Last Post CRGreathouse Number Theory Discussion Group 51 2018-12-16 21:55 LaurV Hobbies 74 2018-07-11 19:33 Batalov Computer Science & Computational Number Theory 40 2013-03-16 09:19 outlnder Soap Box 20 2005-02-03 09:30 nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 07:29.

Sat Jan 29 07:29:18 UTC 2022 up 190 days, 1:58, 1 user, load averages: 1.29, 1.12, 1.10