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

 2012-10-03, 02:14 #67 ewmayer ∂2ω=0     Sep 2002 República de California 2D9C16 Posts Here is the summary for my runs of the 30 k's which survived the default (to ~32M for this size of MMp) factor sieve - These are grouped into the various residue classes k (mod 60) used by the full-blown TF code: Code: pass = 0. k = 5 Q( k = 5 ) has a small factor: 582994261 k = 185 1e11, continuing to 1e13 k = 665 Q( k = 665 ) has a small factor: 7450239943 k = 965 1e11 pass = 1. k = 668 1e11 pass = 2. k = 429 Q( k = 429 ) has a small factor: 221666251 k = 669 Q( k = 669 ) has a small factor: 294177553 pass = 3. k = 200 Q( k = 200 ) has a small factor: 37711537 k = 560 1e11 k = 800 1e11 k = 860 1e11 pass = 4. k = 201 1e11 pass = 5. k = 384 Q( k = 384 ) has a small factor: 35413317743 k = 684 1e11 pass = 6. k = 809 1e11 pass = 7. k = 273 1e11 k = 513 1e11 k = 753 1e11 k = 933 Q( k = 933 ) has a small factor: 66121651 pass = 8. k = 216 Q( k = 216 ) has a small factor: 747303643 pass = 9. k = 401 Q( k = 401 ) has a small factor: 184506277 k = 521 1e11 pass = 10. k = 944 1e11 pass = 11. pass = 12. k = 888 1e11 pass = 13. k = 233 1e11 k = 593 1e11 k = 713 1e11 pass = 14. k = 656 1e11 pass = 15. k = 600 Q( k = 600 ) has a small factor: 104486803 k = 660 1e11 Luigi, thanks for the -lm note ... I'd gotten spoiled from gcc under OS X auto-locating the needed libs for me. If I understand your note correctly, you are running these to 1e12? axn, I see now what you mean. Need to think on it to gauge if the runtime savings will be worth the coding effort. Also, do the addition chains you mention play nice with left-to-right binary modular powering?
 2012-10-03, 06:22 #68 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 231208 Posts Wow! That is fast! I modified my script to sieve for a range and is faster now, especially for k under 4G29 (that is 2^32, pari gets snail slow after 32-bit bound). So I got it few times faster, but no way to "compete" with what you did I had a look into the sources, and put them fast on the shelf where I keep the Chinese books, in case I ever decide to learn foreign languages (that is said with a lot of admiration! when I will have time I will try my best to understand what you did there! I have the opinion that I am assembler programmer too...). Now, if my work here (sieving) is not anymore needed (say, is not anymore productive), I moved to something more interesting: trial division. I may be going to do this for a while, from curiosity . Based on this idea: (the preamble is to understand what I am doing, only the last two commands are important): The last line finished too after a while, and so it did few others. The essential is that now the next candidate k for MM#23 (or MM11213) should be higher then a million very soon. A list of k's from 863504 to 1000000+ was prepared by filtering them to 10^7 (10M). It makes no sense to filter them higher, as a divisibility test take about 8 seconds as you see above (this is 2.8GHz single core on an old machine), so any sieving which takes more then a second or few for a candidate is futile. The list was feed to some routine like mmpdivq() above, but tuned to be a bit faster and to display the progress on the way too. It is going pretty fast: 863565, 863600, 863624, 863645, 863649, 863693, 863700, 863736, etc. They aren't factors. Remark if they are factors, they are also prime! (well, their correspondent q, what I said to axn above, about necessity of a prp test, that is not necessary, for such a small k, if q is a factor, then q is prime, and the divisibility test is faster then PRP test). For the other one, MM#29 (or MM110503), some more k's were filtered and tested, so the first untested one is now around 65000 (I temporarily stopped, and looking for a speed improvement, I will tell you the exact numbers when I reach the faster computer at home, where I am going to play with it again). [edit: now I see a funny effect with the color palette of the forum! if i click on my attached photo, I can't see the "time=xxxx" lines at all. If I double click it, and see it in a separate tab, then I see the time= lines in gray, and the afferent times in white. On the original snapshot they were different shades of purple/pink. in fact THAT was the reason I took a snap, instead of copy/paste the text in "code" tags: to see the colors. I use colors ("syntax highlighting"-like stuff) for an easy reading/understanding. The reader should see "at a glance" what I want, and not waste his time to understand my babbling... And here is very strange, someone could ask why I turn the time "on" if I deleted the times. No, they are not deleted, if you can't see them, save the file and open it with a gif viewer] Last fiddled with by LaurV on 2012-10-03 at 06:35
2012-10-03, 08:24   #69
ET_
Banned

"Luigi"
Aug 2002
Team Italia

10010111000102 Posts

Quote:
 Originally Posted by ewmayer Luigi, [...] If I understand your note correctly, you are running these to 1e12?
That is correct.

Luigi

2012-10-03, 09:37   #70
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2·2,417 Posts

Quote:
 Originally Posted by LaurV Now, if my work here (sieving) is not anymore needed (say, is not anymore productive), I moved to something more interesting: trial division. I may be going to do this for a while, from curiosity .
IIRC, you had M#39, M#41, M#42, M#43, M#45, M#46 reserved to 20G, m#41 completed, the others at 10G.

How are you going to proceed?

Also, (forgive me for being so drastically pedant ) if we want to update the "history" page, we need to be specific on the ranges done and the limits reached...

Quote:
 Originally Posted by LaurV The essential is that now the next candidate k for MM#23 (or MM11213) should be higher then a million very soon. A list of k's from 863504 to 1000000+ was prepared by filtering them to 10^7 (10M). It makes no sense to filter them higher, as a divisibility test take about 8 seconds as you see above (this is 2.8GHz single core on an old machine), so any sieving which takes more then a second or few for a candidate is futile. The list was feed to some routine like mmpdivq() above, but tuned to be a bit faster and to display the progress on the way too. It is going pretty fast: 863565, 863600, 863624, 863645, 863649, 863693, 863700, 863736, etc. They aren't factors. Remark if they are factors, they are also prime! (well, their correspondent q, what I said to axn above, about necessity of a prp test, that is not necessary, for such a small k, if q is a factor, then q is prime, and the divisibility test is faster then PRP test). For the other one, MM#29 (or MM110503), some more k's were filtered and tested, so the first untested one is now around 65000 (I temporarily stopped, and looking for a speed improvement, I will tell you the exact numbers when I reach the faster computer at home, where I am going to play with it again).
Are you saying that, after sieving the reserved ranges on higher MMs up to 20G, you are going to test all possible k on MM11213 up to 10M, and MM110503 up to 65000, and let us sieve the remaining k?

Or you decided to abandon your reservations? In that case, at what state are they?

Luigi

Last fiddled with by ET_ on 2012-10-03 at 09:48

2012-10-03, 10:11   #71
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

24×613 Posts

Quote:
 Originally Posted by ET_ IIRC, you had M#39, M#41, M#42, M#43, M#45, M#46 reserved to 20G, m#41 completed, the others at 10G.
Grrr, I thought that now the sieving should be done by the fastest method, which is about 100 times faster than mine, if I interpret right the numbers from ewmayer's posts...

But ok, I will finish them as claimed.
However this seems futile, as ewmayer's tool sieves a row at a time, and by the time it reaches 20G, my all "eliminated" things are also eliminated, much faster. And as his sieve is done now, if I understand it right, you still need to start it from the beginning, otherwise some k's which are - for example - eliminated by 3, 5, 7, small primes, may not be eliminated by higher primes. I may be wrong, but I compare it with NewPgen, where - to sieve from x to y, you still need the file saved when you sieved from 0 to x.

About the "exact" numbers, I work only at home (I am too busy at job for this) and when I post from job, like now, I don't know any "exact" numbers, that is why I am deliberately vague. Please do not modify any history. I am just playing and mumbling around, but when I have things clear, I will post exact results and notify you (like with the table I posted before) in "official" way

edit: about MM#29, there is nothing to test under 650000 (caution! not 65k, but 650k). That is because the history value was already at 645492 (first untested), I filtered them to some low limit (like 10^8 or so) and the survivors I did trial division with the procedure shown in the previous post. But please don't modify the history, I will post exact figures when I reach home.

Last fiddled with by LaurV on 2012-10-03 at 10:17

2012-10-03, 10:27   #72
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2×2,417 Posts

Quote:
 Originally Posted by LaurV Grrr, I thought that now the sieving should be done by the fastest method, which is about 100 times faster than mine, if I interpret right the numbers from ewmayer's posts... But ok, I will finish them as claimed. However this seems futile, as ewmayer's tool sieves a row at a time, and by the time it reaches 20G, my all "eliminated" things are also eliminated, much faster. And as his sieve is done now, if I understand it right, you still need to start it from the beginning, otherwise some k's which are - for example - eliminated by 3, 5, 7, small primes, may not be eliminated by higher primes. I may be wrong, but I compare it with NewPgen, where - to sieve from x to y, you still need the file saved when you sieved from 0 to x. About the "exact" numbers, I work only at home (I am too busy at job for this) and when I post from job, like now, I don't know any "exact" numbers, that is why I am deliberately vague. Please do not modify any history. I am just playing and mumbling around, but when I have things clear, I will post exact results and notify you (like with the table I posted before) in "official" way edit: about MM#29, there is nothing to test under 650000 (caution! not 65k, but 650k). That is because the history value was already at 645492 (first untested), I filtered them to some low limit (like 10^8 or so) and the survivors I did trial division with the procedure shown in the previous post. But please don't modify the history, I will post exact figures when I reach home.
OK, understood and approved

If you prefer stopping your sieve work, I may take care of it as time permits, no problem here! I asked just to be sure about the ranges that have been completed, and to let others know where to work. I, for instance, am working on M#47, and thanks to Ernst I am way closer to the end.

Luigi

Last fiddled with by ET_ on 2012-10-03 at 10:32

2012-10-03, 17:19   #73
ET_
Banned

"Luigi"
Aug 2002
Team Italia

10010111000102 Posts

Quote:
 Originally Posted by ewmayer Here is the summary for my runs of the 30 k's which survived the default (to ~32M for this size of MMp) factor sieve

1 - As I am setting up the DB for the distributed search, I need the complete list of k for the exponents from M( M( 1257787 ) ) to M( M( 43112609 ) ) that survive the default factor sieve. I think you may run your program on a very small range to have them all...
I will update them as factors pop out increasing the sieve range.

2 - It appears that the siever stops asit finds a factor. Am I correct? I need this informatio to set up the lmits of the search (and to credit it as I find time).

@LaurV: Meanwhile, I took k=20, 60, 108 of M( M( 32582657 ) ) to 10G, and found another factor: MM(32582657): Q( k = 108 ) has a small factor: 7413489781.

Luigi

2012-10-04, 00:04   #74
ewmayer
2ω=0

Sep 2002
República de California

22×3×7×139 Posts

Quote:
 Originally Posted by LaurV But ok, I will finish them as claimed. However this seems futile, as ewmayer's tool sieves a row at a time, and by the time it reaches 20G, my all "eliminated" things are also eliminated, much faster. And as his sieve is done now, if I understand it right, you still need to start it from the beginning, otherwise some k's which are - for example - eliminated by 3, 5, 7, small primes, may not be eliminated by higher primes. I may be wrong, but I compare it with NewPgen, where - to sieve from x to y, you still need the file saved when you sieved from 0 to x.
My code can start at any integer x > 0 (assuming it's also < 2^64), and -- assuming the sieve-setup is working properly, which I have tested enough to have quite high confidence in -- will proceed exactly as if the user had started from scratch, except for not testing < x, obviously. I didn't add any savefile stuff, since the checkpointing data printed to stdout (or piped to a file, which is recommended for multiday runs) allows things to be picked up easily after interrupt, by simply re-invoking with imin = (last printed checkpoint prime) and other params as before.

Quote:
 Originally Posted by ET_ Ernst, two more questions, please 1 - As I am setting up the DB for the distributed search, I need the complete list of k for the exponents from M( M( 1257787 ) ) to M( M( 43112609 ) ) that survive the default factor sieve. I think you may run your program on a very small range to have them all... I will update them as factors pop out increasing the sieve range.
Here you go - these were all sieved to p <= 32452867 (i.e. the first 2 million odd primes). These are for k < 1000 (let me know if you need larger k-ranges for any cases) and sorted by ascending k. I annotated the M47 line with the k's knocked out by the subsequent runs to 1e11 (my run of k = 185 to 1e13 is currently ~2/3 complete):
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.
Quote:
 Originally Posted by ET_ 2 - It appears that the siever stops asit finds a factor. Am I correct? I need this informatio to set up the lmits of the search (and to credit it as I find time).
Yes, that is the current behavior. If there is a good reason to allow it to continue in such cases, I can easily add a command-line arg for that - let me know.

 2012-10-04, 02:25 #75 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 265016 Posts That is what I said (related to starting at "any integer"). Now, do you mean "any k", or "any prime?" You see the difference. If you start from scratch, for MM#47, for example, but start sieving with primes from 1G to 10G, you will NEVER know if k=5, or k=216 (for example) was eliminated or not, as its only "small" prime factor is a bit below 1G. Next prim factor can have 20 digits or more and never be reached by the sieve. Therefore, to know which k were eliminated, you NEED either: [to start from scratch (i.e. from the very first prime x=3, up to the limit you chose)] OR [(to have a "history", like THIS table which we carry here around) AND (closely follow the output log of your program, with a pencil and a paper to cross out the k's which are eliminated, from this table)] Well this is not so bad in reality, but here it was slightly exaggerated, to the purpose of stressing what I want to say: if I filter few lines of the table to 10G or 20G, you either need to use my table, and start your program from primes higher then 10G or 20G, or you need to start again from scratch and REDO my work, in a much faster way. In this light, my work became futile, as is not productive at all (comparing with the speed of your siever) or at most it can count as "independent double check" for the starting point in making the initial table, which mission is already fulfilled, as we have the table already. Basically, this table is the same like the one I posted before, but larger. My table was filtered to 1G and few more k's were eliminated by filtering from 32M (in your case) to 1G (in my case). Checking if a factor is really a factor, this is very easy, and to make sure we did not miss any k, I will post again the eliminated k with their factor. You could also post the factors of the k you eliminated (the one with asterisks, only if their factor is higher then 1G, otherwise they are not in my table) for double checking. Then we can work based on the same table, and I can also use your program to do my lines, which would be faster, assuming someone would post a win64 executable and we each will post the factors we find. I am still playing with my pari, but it seems that I squeezed all the juice from it. It can't do more... For huge primes (over 4G, 32 bits) it is freaking slow. Be back after I do a tough comparison of the two tables :D Last fiddled with by LaurV on 2012-10-04 at 02:27
 2012-10-04, 02:32 #76 c10ck3r     Aug 2010 Kansas 547 Posts Running B1=100,000 B2=2,000,000 on all k's below 1000 for MM47
2012-10-04, 02:47   #77
ewmayer
2ω=0

Sep 2002
República de California

22·3·7·139 Posts

Quote:
 Originally Posted by LaurV That is what I said (related to starting at "any integer"). Now, do you mean "any k", or "any prime?" You see the difference. If you start from scratch, for MM#47, for example, but start sieving with primes from 1G to 10G, you will NEVER know if k=5, or k=216 (for example) was eliminated or not, as its only "small" prime factor is a bit below 1G. Next prim factor can have 20 digits or more and never be reached by the sieve.
Since my code is currently one-k-only, I presume the user is keeping track of which k's have been done, need doing, etc.

For MM#47, I listed the 10 factors I found for the 30 k's surviving my shallow sieve yesterday, a few posts up.

p.s. My MM#47 k=185 recently passed the threshold where I expect to start seeing some composites surviving the sieving, and indeed that is happening:

At n = 6258219203099, which is base-2 PRP
At n = 6287273087119, which is base-2 PRP
At n = 6316322679431, which is composite
At n = 6345369919069, which is base-2 PRP
At n = 6374413059851, which is base-2 PRP
At n = 6403452276301, which is base-2 PRP
At n = 6432488172421, which is composite
At n = 6461520260087, which is base-2 PRP
At n = 6490549216471, which is base-2 PRP
At n = 6519574702099, which is base-2 PRP
At n = 6548597029141, which is base-2 PRP
At n = 6577616916373, which is base-2 PRP
At n = 6606632631227, which is base-2 PRP

 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 05:51.

Tue Dec 7 05:51:38 UTC 2021 up 137 days, 20 mins, 0 users, load averages: 1.16, 1.31, 1.46