20120408, 19:04  #1 
Jun 2009
2^{2}×173 Posts 
How do you efficiently sieve for prime 3/4tuples?
Hey folks,
after finding a record prime quadruple, I'd like to stay in the field of triples and quadruples a bit longer. But the sieving takes a lot of time. I'm looking for a better way to do it. My problem is that NewPGen splits the sieving range into bits of 485MB, takes them to p=1G and combines them. After combining it's fine, but to get to p=1G takes many days for a krange of 10T (which is only a small part of the range I expect I'll have to search). Interestingly, for the combined file NewPGen can address much more than 485MB. I tried to contact Paul Jobling without success. Two mail addresses bounced, the third gave no reaction at all. So I tried to work around this. I wanted to find a way to quickly create an input file for NewPGen to start from. But all sr(x)sieve versions seem to be for not very many k values but lots of n values. I thought about creating a file which is not sieved at all using a simple awk script but those files would get way too large. APsieve is also limited to rather small chunks. Any suggestions about doing this more efficiently? All I need is a way to speed up the very first stage of sieving but I have run out of ideas. Thanks Peter 
20120408, 19:19  #2 
"Vincent"
Apr 2010
Over the rainbow
2^{2}·11·61 Posts 
Wich form are they? Base 2? if it's base 2 you can use fermfact. it's a siever, so you can sieve the +1 side , specifing kmin and kmax as well as nmin and nmax.
Last fiddled with by firejuggler on 20120408 at 19:43 
20120408, 19:22  #3 
Jun 2009
2^{2}·173 Posts 
Sorry, forgot to mention that. I'm looking at k*2^n 1, +1, +5, (and +7 for quadruples).
I am not familiar with fermfact, I'll take a look at it. Thanks! 
20120408, 19:26  #4 
"Vincent"
Apr 2010
Over the rainbow
2^{2}×11×61 Posts 
It's originally designed to find fermat factor, which are k*2^n+1. Since those prime are included in your tuple, that could work.
Edit : it's availlable on fermatsearch.org Last fiddled with by firejuggler on 20120408 at 19:32 
20120408, 19:48  #5 
Jun 2009
1010110100_{2} Posts 
OK, I tried a small batch (krange of 1e10 sieved to 1G) and I got an ABCD file of 764MB. Sieving only one form of a tuple does not get rid of the candidates very quickly.
I'll do some more testing but I am afraid this might not work as nicely as I hoped. Thanks anyway! EDIT: It seems the range of k is limited to about 5e10. Let's see how far that gets us in a timely manner... Last fiddled with by PuzzlePeter on 20120408 at 19:52 
20120409, 08:55  #6 
Jun 2009
2^{2}×173 Posts 
I'm afraid this won't work. Sieving the +1 form only does not remove enough candidates, so I'm getting files in the 20+ GB size range when trying to use the largest possible k range.
Maybe a twin sieve could do the trick, but those I know are rather limited also. If only NewPGen could be forced to take larger bites at once... 
20120409, 10:34  #7 
Banned
"Luigi"
Aug 2002
Team Italia
1001011100010_{2} Posts 
Did you try ppsieve instead?
Luigi 
20120409, 16:18  #8 
Jun 2009
2^{2}·173 Posts 

20120409, 16:27  #9 
"Vincent"
Apr 2010
Over the rainbow
2^{2}×11×61 Posts 
I'm really sorry it didn't work out with fermfact... well ppsieve will remove from +1 and 1 side. If i remember right there is a version working with cuda.might seep up the process.

20120409, 16:30  #10 
Jun 2009
1264_{8} Posts 
ppsieve does not seem to work as it does not write a candidate file, only a factor file. Plus it requires kmax < pmin so it can't be used to start a sieve.

20120409, 18:23  #11  
Banned
"Luigi"
Aug 2002
Team Italia
2·2,417 Posts 
Quote:
I also wrote a short program to extract all factors from the master file and recreate a new candidates file without the found factors. Luigi 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How/Where to get Jens Kruse Andersen's prime constellation sieve?  Stargate38  And now for something completely different  2  20170428 00:08 
Efficiently finding a linear progression in data  fivemack  Math  27  20151212 18:42 
GPU Prime Sieve  tapion64  GPU Computing  7  20140410 06:15 
Sieve depth vs. prime probability  Unregistered  Information & Answers  2  20100525 20:51 
Prime in Riesel Sieve Project  Sloth  Prime Sierpinski Project  1  20060510 02:02 