20121003, 02:14  #67 
∂^{2}ω=0
Sep 2002
República de California
2^{3}·3·487 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 fullblown 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 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 lefttoright binary modular powering? 
20121003, 06:22  #68 
Romulan Interpreter
"name field"
Jun 2011
Thailand
268D_{16} 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 32bit 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 20121003 at 06:35 
20121003, 08:24  #69 
Banned
"Luigi"
Aug 2002
Team Italia
11346_{8} Posts 

20121003, 09:37  #70  
Banned
"Luigi"
Aug 2002
Team Italia
2·41·59 Posts 
Quote:
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:
Or you decided to abandon your reservations? In that case, at what state are they? Luigi Last fiddled with by ET_ on 20121003 at 09:48 

20121003, 10:11  #71  
Romulan Interpreter
"name field"
Jun 2011
Thailand
23215_{8} Posts 
Quote:
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 20121003 at 10:17 

20121003, 10:27  #72  
Banned
"Luigi"
Aug 2002
Team Italia
2×41×59 Posts 
Quote:
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. Thank you for your collaboration! Luigi Last fiddled with by ET_ on 20121003 at 10:32 

20121003, 17:19  #73  
Banned
"Luigi"
Aug 2002
Team Italia
2·41·59 Posts 
Quote:
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 

20121004, 00:04  #74  
∂^{2}ω=0
Sep 2002
República de California
10110110101000_{2} Posts 
Quote:
Quote:
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. 

20121004, 02:25  #75 
Romulan Interpreter
"name field"
Jun 2011
Thailand
71·139 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 20121004 at 02:27 
20121004, 02:32  #76 
Aug 2010
Kansas
547_{10} Posts 
Running B1=100,000
B2=2,000,000 on all k's below 1000 for MM47 
20121004, 02:47  #77  
∂^{2}ω=0
Sep 2002
República de California
2^{3}·3·487 Posts 
Quote:
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 base2 PRP At n = 6287273087119, which is base2 PRP At n = 6316322679431, which is composite At n = 6345369919069, which is base2 PRP At n = 6374413059851, which is base2 PRP At n = 6403452276301, which is base2 PRP At n = 6432488172421, which is composite At n = 6461520260087, which is base2 PRP At n = 6490549216471, which is base2 PRP At n = 6519574702099, which is base2 PRP At n = 6548597029141, which is base2 PRP At n = 6577616916373, which is base2 PRP At n = 6606632631227, which is base2 PRP 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Is CEMPLLA 1.5 "the only software in the world capable of discovering" something? Not really.  CRGreathouse  Number Theory Discussion Group  51  20181216 21:55 
Official "World cup 2014/2018" teat  LaurV  Hobbies  74  20180711 19:33 
Problem E7 of Richard Guy's "Unsolved problems in number theory"  Batalov  Computer Science & Computational Number Theory  40  20130316 09:19 
Is the USA the "new" peacekeeper of the world??  outlnder  Soap Box  20  20050203 09:30 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 