News from sub-project Deep Sieving

[ET_]

Originally Posted by Batalov

Here's the Pari interactive sieving script. It can be stopped periodically, the sieve array saved, and then the sieving can be continued.

# 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

[Batalov]

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:

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.

[ET_]

Originally Posted by Batalov

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:

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

[Batalov]

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.

[ET_]

Originally Posted by Batalov

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

[Batalov]

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]

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)

[ET_]

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

[Batalov]

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

2^1398269-1

Then you run

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)

[ET_]

Originally Posted by Batalov

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

2^1398269-1

Then you run

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

[aketilander]

Originally Posted by Batalov

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!