-   Software (
-   -   How do you efficiently sieve for prime 3/4-tuples? (

Puzzle-Peter 2012-04-08 19:04

How do you efficiently sieve for prime 3/4-tuples?
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 k-range 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.


firejuggler 2012-04-08 19:19

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.

Puzzle-Peter 2012-04-08 19:22

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!

firejuggler 2012-04-08 19:26

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[URL=""][/URL]

Puzzle-Peter 2012-04-08 19:48

OK, I tried a small batch (k-range 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...

Puzzle-Peter 2012-04-09 08:55

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...

ET_ 2012-04-09 10:34

Did you try ppsieve instead?


Puzzle-Peter 2012-04-09 16:18

[QUOTE=ET_;295901]Did you try ppsieve instead?


No. It didn't come to mind even though I think I have used it some time in the past. I'll have a look at it. Thanks for the suggestion!

firejuggler 2012-04-09 16:27

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.

Puzzle-Peter 2012-04-09 16:30

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.

ET_ 2012-04-09 18:23

[QUOTE=Puzzle-Peter;295921]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.[/QUOTE]

I'm using ppsieve for presieving Fermat candidates. I start with fermFact up ro 600G/1T (using NewPGen format), cat all results files into one, then switch to ppsieve.

I also wrote a short program to extract all factors from the master file and recreate a new candidates file without the found factors.


All times are UTC. The time now is 05:38.

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