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

Puzzle-Peter · 2012-04-08, 19:04

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.

Thanks
Peter

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

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?

Luigi

Puzzle-Peter · 2012-04-09, 16:18

Quote:

Originally Posted by ET_

Did you try ppsieve instead?

Luigi

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:

Originally Posted by Puzzle-Peter

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.

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.

Luigi

2012-04-08, 19:04	#1
Puzzle-Peter Jun 2009 2²·5²·7 Posts	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. Thanks Peter

2012-04-08, 19:19	#2
firejuggler "Vincent" Apr 2010 Over the rainbow B63₁₆ 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 2012-04-08 at 19:43

2012-04-08, 19:26	#4
firejuggler "Vincent" Apr 2010 Over the rainbow 5×11×53 Posts	It's originally designed to find fermat factor, which are k2^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 2012-04-08 at 19:32*

2012-04-08, 19:48	#5
Puzzle-Peter Jun 2009 2BC₁₆ Posts	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... Last fiddled with by Puzzle-Peter on 2012-04-08 at 19:52

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	2017-04-28 00:08
Efficiently finding a linear progression in data	fivemack	Math	27	2015-12-12 18:42
GPU Prime Sieve	tapion64	GPU Computing	7	2014-04-10 06:15
Sieve depth vs. prime probability	Unregistered	Information & Answers	2	2010-05-25 20:51
Prime in Riesel Sieve Project	Sloth	Prime Sierpinski Project	1	2006-05-10 02:02

2012-04-08, 19:22	#3
Puzzle-Peter Jun 2009 2²×5²×7 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!

2012-04-09, 08:55	#6
Puzzle-Peter Jun 2009 2BC₁₆ 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...

2012-04-09, 10:34	#7
ET_ Banned "Luigi" Aug 2002 Team Italia 2×11×13×17 Posts	Did you try ppsieve instead? Luigi

2012-04-09, 16:27	#9
firejuggler "Vincent" Apr 2010 Over the rainbow 5×11×53 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.

2012-04-09, 16:30	#10
Puzzle-Peter Jun 2009 1274₈ 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.