20120927, 19:11  #45  
∂^{2}ω=0
Sep 2002
República de California
5·2,351 Posts 
Quote:
(I reproduced the small factor for k = 5; k= 185 I have sieved to 10^11, no factors below that bound). I am working on some optimizations today which I hope will double (or more) the speed; once I'm satisfied it's as fast as I can make it without major (week or more) effort I'll post it here. 

20120927, 20:46  #46  
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
Quote:
Code:
(17:34)>for(x=1,43112609,if(43112609%x==(x1),print(x))) 1 2 3 5 6 9 10 15 18 30 45 90 479029 958058 1437087 2395145 2874174 4311261 4790290 7185435 8622522 14370870 21556305 edit: the last mod is listed wrong it's mod (2^x1) Last fiddled with by science_man_88 on 20120927 at 20:56 

20120927, 21:29  #47  
Banned
"Luigi"
Aug 2002
Team Italia
11371_{8} Posts 
Quote:
Your timings seems at least 10x faster than our PARI script: when the code will be ready I think we may arrange a distributed sieving on all k. I also tested a primality testing of 2*185*M47+1 with pfgw. It is slow, but can be done (it takes about the time of a LL test on a 56M exponent). I was doing some tests, and I know that LaurV is updating a table for all k candidates below 1000 for MM from 34 to 47. So, if you all agree, we may wait for the table, define a criterion for the reservations, and then "Gentlemen, start our sievers!" (that should be "your siever", but this way sounds better)... Luigi Last fiddled with by ET_ on 20120927 at 22:20 

20120928, 03:32  #48  
Jun 2003
2^{2}×3^{2}×151 Posts 
Quote:
NewPGen can sieve a fixedk range at about 6G / min on similar machine (while it is not exactly applestoapples, the complexity of calculation is comparable). My sieve in PARI can do a 4G range in appr 2 mins. [k=1..10000, primelimit set to 4G]. Since I rely on precomputed primelist, that is as high as I can go with 32bit PARI. Nonetheless, the point is that you're way off in terms of what is achievable. Could there be an algorithmic issue with your code? 

20120928, 09:12  #49 
Romulan Interpreter
"name field"
Jun 2011
Thailand
10,273 Posts 
@sm88: You are a bit confuse here, there is no shame, I was doing this mistake in the beginning, and I am still doing it from time to time... Generally when you switch to modular things, the affirmation "if a=b then x^a=x^b" is not true. There is something called "eulerphi" in the middle... For example, 5=16 (mod 11), but 2^5=32=10 (mod 11) and 2^16=65536=9 (mod 11). When you do double mersenne, i.e MMp, the Mp is the one needing to have those modular properties, and not p. It does not help us too much what properties p (mod x) has; only what properties Mp (mod x) has, helps. You can't "raise" or "lift" from p to Mp. Those are tremendous numbers then, difficult to work with.

20120928, 10:16  #50  
Romulan Interpreter
"name field"
Jun 2011
Thailand
10,273 Posts 
Quote:
mmpp.zip Grrr, I tried to make some snaps, but either the file is too big, the picture is too wide, I have too many attachments (is there no way to overcome that restriction??? xyzzy? I'm not the kind of guy who attach thousands of things to posts just for occupying the space, and generally, beside of my longspeech posts, I don't waste space here!) so I made a zip. Is not nice looking, and you have to unzip it by yourself. I put the excel table and the pari scripts that helped me, updated. There was a laptop which helped me too, but that I can't attach it to the post (I tried! ) Remark that there are some hidden rows, you can unhide them to see more information, but nothing new, everything is from the web page or wikis, and also remark that I am working the darkgreen (khaki?) rows, in fact #39 and #41 should be finished to 20G by now, I let two workers in the morning running mmppsk() for the #k39 and #k41 lists, as shown in the sample code (the laptop is a twocore machine). Also, most of the work was duplitriplicated, as some people also did the testing, I didn't know ET is interesting in playing with those k's and he didn't know I am spending my time into it, so before we got contact on PM, we did the same work. edit: some supermod can move this thread at all to the "doppi" subforum (!?) thanks edit2: obviously, I use the notation M#34 to M#47, like "number", "index", "ordinal", "the 34th or 47th mersenne prime number", to make distinction between M#6 (which would be the sixth mersenne prime number, M#xx is always a prime number) and M6 which is 2^61. In this light, M31 is 2147483647, but M#31 is 2^2160911, a prime, and MM31 is a 646456993digits number. Now someone tells me how many digits in MM#31, and how many in M#M31 and respective in M#M#31, and if they are prime... Last fiddled with by LaurV on 20120928 at 10:52 

20120928, 10:44  #51  
Banned
"Luigi"
Aug 2002
Team Italia
3·1,619 Posts 
Quote:
1  I will update the history page and (try to) arrange a new subpage of the site related to sieving (but not before next week). 2  Meanwhile, if no one else will, I am working on MM47, leaving MM40 and MM44 to volunteers for further sieving. 3  Ernst and axn may test their sievers against LaurV script, and let us know about correlated efficiency. 4  My idea for the next week(s) would be to deliver some webservice to: authenticate a user contact the db download a k and its limit upload k with the the new limit check the result's coherence and update the db Between the upload and the download there should be some program/script apt to sieve, and maybe releasing an output verifiable by the server. We may set limits to the sieving job, and once all candidates have been taken to that limit, decide whether raise the limit, start LLtesting or whatever... Does the idea interest anyone? Luigi 

20120928, 12:02  #52 
Jun 2003
2^{2}·3^{2}·151 Posts 
If you're gonna do it, you might as well do it right.
1. Sieving is much more efficient than "one k at a time" approach. In fact, if we can find an optimal (or pretty good) addition/subtraction chain for all the exponents in question, sieving all the MMps together will be the most efficient. However, the sieving approach would need us to specify the krange of interest (k < 10^6?), such that P95 can efficiently support them (i.e. have a good FFT to test them). 2. None of the scripts/program so far are even close to optimal. If you're gonna throw compute power at it, perhaps it'll pay to invest in some upfront programming. I know that Ken_g6 has tackled k*2^n+1 type sieving  perhaps he can adapt the code for our purpose? [I would anticipate an optimal siever to do a range of 10^12/day/core  so no real advantage in pushing thru with the current scripts] 3. Once we sieve something to a reasonable depth (10^15?), we can then P1 and/or ECM them before doing PRP. Since these would be very large primes on their own right, PRP before MMp trial division sounds right. 
20120928, 12:02  #53  
"Forget I exist"
Jul 2009
Dartmouth NS
10000011100010_{2} Posts 
Quote:
edit:actually (x^a1)=(x^b1) x=2 is true sorry. Last fiddled with by science_man_88 on 20120928 at 12:15 

20120929, 06:58  #54  
Romulan Interpreter
"name field"
Jun 2011
Thailand
24041_{8} Posts 
Quote:
On the bright side, when taking #39 to 10G, k=225 popped out a factor : 7333051961. I am happy about it, I want to get rid of that long line in the table, to make the table smaller Last fiddled with by LaurV on 20120929 at 06:59 

20120929, 08:45  #55  
Romulan Interpreter
"name field"
Jun 2011
Thailand
2821_{16} Posts 
Quote:
(gotcha back ) 

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 