mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operazione Doppi Mersennes

Reply
 
Thread Tools
Old 2013-09-07, 19:40   #12
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×29×83 Posts
Default

Quote:
Originally Posted by Batalov View Post
Here's the Pari interactive sieving script. It can be stopped periodically, the sieve array saved, and then the sieving can be continued.
Code:
# gp -p 2000000
#sieve limit:
M=2000000;
#the P in MMp:
P=1398269;


allocatemem(800000000)
K=vector(M);
forprime(p=5,M, k=Mod((p-1)/2,p)/(Mod(2,p)^P-1);forstep(i=lift(k)+1,M,p,K[i]=1));
p=M;
while(p=nextprime(p+1), if((i=lift(Mod((p-1)/2,p)/(Mod(2,p)^P-1)))<M,K[i+1]=1);K[1]=p);
# can stop with Ctrl-C

#write the sieve file
write("si13y",P); write("si13y","#"K[1]);
forstep(i=5,M-1,[3,1,3,5],if(K[i+1]==0,write("si13y",i)))

#go on
p=K[1];
while(p=nextprime(p+1), if((i=lift(Mod((p-1)/2,p)/(Mod(2,p)^P-1)))<M,K[i+1]=1);K[1]=p);
#etc, after a while stop  with Ctrl-C, write, continue
This probably can be gp2c'd. I didn't bother, the speed was satisfactory for me.
Thank you. Serge, I had a different PARI sieving script. I will test yours and proceed.

I am "stuck on sieving" because my old PARI script was run up to 1G (50" for a full test on K), then I passed the survivors on Ernst's program up to 20G, and each candidate required less than 15 minutes to reach 20G.

A test on MM34 with pfgw requires about one hour, so I decided to presieve candidates up to 800G (less than one hour) to eliminate some more Ks.

As the MM exponent grows, the time required by pfgw grows more, so the bigger the exponent, the higher the sieve level.

Finally, I only sieve when I have spare time (that's why it seems I'm "stuck").

Let me try your script, and see if the method can be reworked.

Just a last question: did you test if LLR is faster than pfgw on these numbers?

Luigi
ET_ is offline   Reply With Quote
Old 2013-09-07, 20:16   #13
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·5·17·37 Posts
Default

Well, I meant "stuck" figuratively. And surely not just you but the whole team, - the plural "you". I'd expect that more people ventured into actually, testing, without a need to nudge.

Re: your question about PFGW vs LLR: I didn't check; in LLR a typical test for MM35 is ~40 minutes. We can benchmark on this toy plain looking example:
Code:
ABC $a*$b^$c$d
1433553 2 1398270 -2867105
Sieving a range of k's is nearly as fast as "sieving" (read, "TF") a single k. The only additional implementational detail is modular division (or inversion). I clearly admit that I am as lazy as the next guy, that's why I didn't write any code, just winged it in Pari. This can surely be made much faster in plain C, and this is still just a dumb sieve. Geoff or Ben could use some tricks to make it much faster still.
Batalov is offline   Reply With Quote
Old 2013-09-07, 20:55   #14
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×29×83 Posts
Default

Quote:
Originally Posted by Batalov View Post
Well, I meant "stuck" figuratively. And surely not just you but the whole team, - the plural "you". I'd expect that more people ventured into actually, testing, without a need to nudge.

Re: your question about PFGW vs LLR: I didn't check; in LLR a typical test for MM35 is ~40 minutes. We can benchmark on this toy plain looking example:
Code:
ABC $a*$b^$c$d
1433553 2 1398270 -2867105
Sieving a range of k's is nearly as fast as "sieving" (read, "TF") a single k. The only additional implementational detail is modular division (or inversion). I clearly admit that I am as lazy as the next guy, that's why I didn't write any code, just winged it in Pari. This can surely be made much faster in plain C, and this is still just a dumb sieve. Geoff or Ben could use some tricks to make it much faster still.
I'm playing with your code: I let it run with "gp -p 2000000 bata.gp" for a couple of minutes, break, rename the file (because otherwise it appends the results to itself), copy the K value on the si13y file, paste it into the script as p, reload the script with "gp -p 2000000 bata.gp" and... get confused, because the file shrinks and swells with no apparent reason.

I am not fluent with PARI, so I may have lost something in translation...

You assign M=2000000, start the forprime cycle with p=5 to create the primes array, then reassign M to p (this is the value I change in your script after each break). What am I losing?

Luigi

Last fiddled with by ET_ on 2013-09-07 at 21:00
ET_ is offline   Reply With Quote
Old 2013-09-07, 21:00   #15
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

943510 Posts
Default

After the break, you use
p=K[1];

This value is also saved in the sieve file (in the 2nd line).

And yes, you have to rename the file (or change the script slightly).
It is easier for you to rename it externally, right after it is done writing.
Batalov is offline   Reply With Quote
Old 2013-09-07, 21:08   #16
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

113168 Posts
Default

Quote:
Originally Posted by Batalov View Post
After the break, you use
p=K[1];

This value is also saved in the sieve file (in the 2nd line).

And yes, you have to rename the file (or change the script slightly).
It is easier for you to rename it externally, right after it is done writing.
Fine, I was doing right.

In my opinion, the fle should shrink after each break, as the sieve proceeds. It didn't. Maybe I let the whole thing run for too little time?

Luigi
ET_ is offline   Reply With Quote
Old 2013-09-07, 21:39   #17
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×5×17×37 Posts
Default

It is an interactive script - you don't call it. You throw in batches of lines into a working pari shell.

You can, of course, modify it to be parametrized and sieve to a certain limit: replace "while(p=nextprime(p+1)," with "while((p=nextprime(p+1))<some_limit," and run it through. It was not my intention to make it a finished script.
Batalov is offline   Reply With Quote
Old 2013-09-09, 01:19   #18
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×5×17×37 Posts
Default

Oh, when it rains, it pours.
This one is luckier still than the previous one.

But there we go: 374568*(2^3021377-1)+1 is prime.
MM3021377 division test is in progress...
...it doesn't divide MM3021377 (no surprise here)

Last fiddled with by Batalov on 2013-09-09 at 05:31
Batalov is offline   Reply With Quote
Old 2013-09-09, 08:20   #19
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×29×83 Posts
Default

Nice one! You are rocking on MM34, MM35, MM36 and MM37!
May I ask you to communicate the range of exponents you test from time to time, so that I can keep the ranges updated?

I've seen that you used OpenPFGW for this one, using Mp as helper for N-1.
Would you mind sharing to the forum the command line you used?

Meanwhile, I am using your script to extend the sieving limits to MM38, MM47 and MM48 for the first 2,000,000 candidates.

I plan to update the table for all double Mersennes > MM33, so that we can concentrate on searching candidates instead of "sieving".

Luigi
ET_ is offline   Reply With Quote
Old 2013-09-09, 19:33   #20
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×5×17×37 Posts
Default News from sub-project Deep Sieving

Luigi,

I will wrap up all results and email them to you. (Too big for attachments.)

Re: the proof. You prepare a separate file, let's call it "Help139", where you put a single line
Code:
2^1398269-1
Then you run
Code:
pfgw -f1 -l -t -hHelp139 -q"507568*(2^1398269-1)+1"
That's it.

I've proven many near-repunits for M.Kamada's site and had used very large helper files from time to time. In the helper file, every line should be a prime (and formulae are accepted, too). If you run a -tc proof, you put factors for both N-1 and N+1 side in the same file. The routine will simply use try them after short trial factoring (that's why you don't have to put the 507568 factors, 2 * 2 * 2 * 2 * 31723: a) they are small, b) the N-1 factorization is already way over 33%.) Here's another example: http://primes.utm.edu/primes/page.php?id=115087 (note that all factors were supplied only once)
Batalov is offline   Reply With Quote
Old 2013-09-10, 09:57   #21
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2·29·83 Posts
Default

Quote:
Originally Posted by Batalov View Post
Luigi,

I will wrap up all results and email them to you. (Too big for attachments.)

Re: the proof. You prepare a separate file, let's call it "Help139", where you put a single line
Code:
2^1398269-1
Then you run
Code:
pfgw -f1 -l -t -hHelp139 -q"507568*(2^1398269-1)+1"
That's it.

I've proven many near-repunits for M.Kamada's site and had used very large helper files from time to time. In the helper file, every line should be a prime (and formulae are accepted, too). If you run a -tc proof, you put factors for both N-1 and N+1 side in the same file. The routine will simply use try them after short trial factoring (that's why you don't have to put the 507568 factors, 2 * 2 * 2 * 2 * 31723: a) they are small, b) the N-1 factorization is already way over 33%.) Here's another example: http://primes.utm.edu/primes/page.php?id=115087 (note that all factors were supplied only once)
I see Thanks!

Luigi
ET_ is offline   Reply With Quote
Old 2013-09-10, 20:02   #22
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

2×283 Posts
Default

Quote:
Originally Posted by Batalov View Post
Oh, when it rains, it pours.
This one is luckier still than the previous one.

But there we go: 374568*(2^3021377-1)+1 is prime.
MM3021377 division test is in progress...
...it doesn't divide MM3021377 (no surprise here)
This is a really BIG one!!! Congratulations again!
aketilander is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Deep Sieving MM49 in parallel ET_ Operazione Doppi Mersennes 22 2016-07-28 11:23
Deep Hash diep Math 5 2012-10-05 17:44
The news giveth, the news taketh away... NBtarheel_33 Hardware 17 2009-05-04 15:52
Question on going deep and using cores MercPrime Software 22 2009-01-13 20:10
Deep Sieving 10m Digit Candidates lavalamp Open Projects 53 2008-12-01 03:59

All times are UTC. The time now is 13:28.

Sun May 16 13:28:31 UTC 2021 up 38 days, 8:09, 0 users, load averages: 1.94, 1.98, 1.93

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.