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

Puzzle-Peter · 2012-04-27, 18:33

Quote:

Originally Posted by biwema

Im am sorry that i did not yet answer about my calculations. I just was busy. I try to do my best and give a detailed answer this weekend.

I simply calculate d^k where d=number of decimal digits and k=length of tuple. I miss your numbers by a factor of ~4-5. Do you aim for a certain probability of the range containing a tuple, say 90%?

henryzz · 2012-04-27, 20:01

Quote:

Originally Posted by Puzzle-Peter

This is very interesting.

If I understood Robert correctly, you need a very large search range for bound_small_primes=19 to be efficient.

I'm really curious what sieve_len will do to performance and memory usage.

sieve_len made very little difference to timings. Doubling it slowed it down a small amount and halfing is didn't make a noticable difference. Memory wise it should hardly make a diffference. 8192*8 is only 64k which is the size of the L1 cache of a lot of AMD cpus. Intel cpus have 32k cache so decreasing to 4096 should have more of an effect speed wise. The real memory hog in this program is when you use a lot of primes. Sieving upto 10M only uses 30MB each core.

I changed hash_bits to 20 which took me down to 20 minutes per 100T. I am now doing 4 lots of 5P overnight. This will take me upto 22P. 730P is the estimate.

Puzzle-Peter · 2012-04-28, 05:49

20 minutes per 100T? Now that's what I call impressive! Using NewPGen we would be talking about weeks...

biwema · 2012-04-30, 12:21

Quote:

Originally Posted by Puzzle-Peter

EDIT: By the way, how do you calculate your "Range per one tuple" figures? I get much higher numbers when I try to estimate the k range needed per tuple.

I am sorry that I did not answer that question for such a long time.
Yesterday I took time to do that, but lost everything after I accidently hit the ‘page back’ key. Trying again…

After sieving to deep limits, the primes in a tuple are independent. It is possible to multiply the probabilities of being prime.

Example: henrzz, 6 Tuple with 1000 Bits (I don’t know the exact number) and 40 bit Mantissa. Sieving to 27 bit (131M);
Probability of a prime is [Bits Sieving depth] / ([Size of Candidate]/2).
Probability (prime): 27 / 520 = 1 in 19.25 or 5.2%.
Twin: 1 in 371
3-Tuple: 1 in 7143
4-Tuple: 1 in 137580
5-Tuple: 1 in 2.65 Million
6-Tuple: 1 in 51 Million
According to the Number of candidates in the sieved array it is possible to extrapolate the array, which is needed.
Of course it is just a probability: After searching that range the probability of success is 1-1/e. (If the range is twice as big, the probability is 1-1/e².

When sieving to low limits, the candidates are not independent:
Having a NewPGen array of k*2^x for 6 Tuple, k odd. One out of 105 candidates is remaining after sieving 3, 5 and 7. Optimized sieves use an array which just use these numbers.
When sieving p for N-Tuple, (p-N)/p candidates are remaining.
6-tuple: sieving 11, 13, 17, 19, 23 removes
5/11 * 7*13 * 11/17 * 13/19 * 17/23 = 8% remaining.
After sieving up to 1023 less than 0.1% of the candidates are remaining. (<0.025% for 7-tuple; sieving to 1048000 : 6-tuple 0.0014%, 7-tuple: 0.000175%)
The reducing number of candidates makes it difficult to keep the sieve efficient.

Up to 4-Tuple, proth (k*2^n) numbers are more efficient than primordial (k*p#).
6 – 10(?) tuple, primorial numbers are faster.
About 5-tuple it depends on the tools used, which is faster.
15+ tuple need completely different algorithms.

henryzz · 2012-04-30, 20:01

I am not sure your formulas are right. I got 1/23 per candidate instead of 1/25 from your formula for the numbers I am testing currently. The odds of a number of the form k*b^n+c being prime(c small) is 1 in (n*ln(b)+ln(k))
The odds of a random candidate surviving sieving upto s is 1 in (1.781*ln(s)).
Thus the odds of each candidate surviving sieving is (1.781*ln(s))/(n*ln(b)+ln(k)).
1.781 is an approximation of exp(gamma) http://www.wolframalpha.com/input/?i...7s+constant%29

I have attached a spreadsheet including these formulas. It closely matches the results I have been getting so far in my search for 7-tuples.

I discovered just after sieving upto 46P that once k reaches a certain level pfgw is forced to resort to more general methods of fft which slows it down by a factor of 2.5. I need to sieve deeper in future.

biwema · 2012-04-30, 20:50

Our Approaches are just different. I did not use a constant, because i just use the quotient between lieve Limit and candidate. So even the base of the log has no influence anymore.

I see one main difference:
I use P(prime) = log(Sievedepth)/(log(Candidate)/2)
You use P(prime) = log(Sievedepth)/log(Candidate)

I am careful with low sieving levels because tuplets are not independant. After sieving to some limit, I think my approximation are more or less accurate.

About the probabilities of 6 and 7 Tuple: Here we should maybe take care about rounding errors: 1-(1-3*10^-10))^150000000
Here there are just a few significant digits raised to a huge power.

Could you tell me some information about your search?
How do you count 150000000 candidates?
k*2^1000+c or ((210*k)+q)*2^1000+c ?
How many candidates were left after sieving how deep (6 tuple and 7 tuple)?

henryzz · 2012-04-30, 23:01

I sieved upto only 10M for most of the range using gsieve. 150M is the number of candidates remaining after the sieving for the range 0-46P. The sieving only took a couple of days on a single quad. My n is exactly 1000.
Each candidate is a k*2^n-1 that needs to be tested(and if prime pfgw will test +1 +5 etc).

It seems that you effectively use 2 instead of 1.781 as your constant. This isn't bad but it does build up when you get to 7-tuples.
2^7=128 while 1.781^7=~57

Cybertronic · 2012-05-03, 06:13

Hello members !

Can everybody of you writing a sieve like APSIEVE (without PRPing) with features:
- sparse sieve like NewPGen
- k-tuplets up to k=10
- sieving up to 10^13...?
- form k*p#+a1,a2,...

?

best,
Norman

henryzz · 2012-05-05, 12:22

I believe it should be possible to modify gsieve to do that. It should pretty much just need the function initprimes modifying. Unfortunately I don't understand that function so I can't do it.

henryzz · 2012-07-21, 21:07

I have tested n=1000 for 7-tuples upto 34P.
I have found 324 quads and 15 quins so far.
I have sieved until 81P so testing should go fast for a bit. I hope to have found a run or two of six primes by then. Note this isn't a 6-tuple as a 6-tuple isn't contained within a 7-tuple.

Puzzle-Peter · 2013-06-22, 19:32

It's me again...

I'm trying to adapt the codes in this thread to a new brain-fart of mine, but it seems to be beyond my capabilities.

I'd like to search for triplets of the form k*x -1, +1, +5 with x being a precomputed constant of several thousands of digits.

I know k has to be a multiple of 6. I also know that for the x I'm using to test this, a must end in 2 or 8. That leaves a = 12, 18, 42, 48, 72, 78 etc. which makes two strings of numbers
a=30*n+12
a=30*n+18
with n = [0...chosenlimit]

I thought about doing two runs, one for the 30*n+12 version and one for 30*n+18. I have a PFGW script to precompute a table (text file) which contains lines of
p, x MOD p
for all primes p below a chosen sieve limit, then use this information to go through an array of booleans and set those to 0 where (a*(x MOD p)) equals +1, p-1 or p-5.
And this is where the fun starts. I seem to be unable to determine which a values to cancel out. I can find them by hand by simply trying from the low end upwards to the first hit, then go up by steps of the size p, but I don't seem to be able to create the formula for finding the first one. Plus this would probably be much more efficient on a bit array rather than booleans.

I know the codes here in this thread contain all the stuff I need. I keep looking at the init_indexes function from Sex_2.pas in post #34, but what is happening there is beyond my grasp. So any hints or help would be greatly appreciated.

In case you're wondering about my motivation for this: I'd like to try and go for a triple too large to prove with PRIMO. So I use a number x that makes a N+1 or N-1 proof possible for all three members of the triple. I tried this for a small example (a few dozen digits) to make sure it works by using PFGW and brute force. For larger numbers I need a good sieve though. I have a working PFGW "sieve" script, but it's based on the FACTORIZE function which makes it too slow for large numbers.

2012-04-28, 05:49	#69
Puzzle-Peter Jun 2009 700₁₀ Posts	20 minutes per 100T? Now that's what I call impressive! Using NewPGen we would be talking about weeks... Last fiddled with by Puzzle-Peter on 2012-04-28 at 05:50

2012-05-03, 06:13	#74
Cybertronic "Norman Luhn" Jan 2007 Germany 2⁸·3 Posts	Hello members ! Can everybody of you writing a sieve like APSIEVE (without PRPing) with features: - sparse sieve like NewPGen - k-tuplets up to k=10 - sieving up to 10^13...? - form kp#+a1,a2,... ? best, Norman Last fiddled with by Cybertronic on 2012-05-03 at 06:15*

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-30, 20:50	#72
biwema Mar 2004 3×127 Posts	Our Approaches are just different. I did not use a constant, because i just use the quotient between lieve Limit and candidate. So even the base of the log has no influence anymore. I see one main difference: I use P(prime) = log(Sievedepth)/(log(Candidate)/2) You use P(prime) = log(Sievedepth)/log(Candidate) I am careful with low sieving levels because tuplets are not independant. After sieving to some limit, I think my approximation are more or less accurate. About the probabilities of 6 and 7 Tuple: Here we should maybe take care about rounding errors: 1-(1-310^-10))^150000000 Here there are just a few significant digits raised to a huge power. Could you tell me some information about your search? How do you count 150000000 candidates? k2^1000+c or ((210k)+q)2^1000+c ? How many candidates were left after sieving how deep (6 tuple and 7 tuple)?

2012-04-30, 23:01	#73
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 2²·1,553 Posts	I sieved upto only 10M for most of the range using gsieve. 150M is the number of candidates remaining after the sieving for the range 0-46P. The sieving only took a couple of days on a single quad. My n is exactly 1000. Each candidate is a k*2^n-1 that needs to be tested(and if prime pfgw will test +1 +5 etc). It seems that you effectively use 2 instead of 1.781 as your constant. This isn't bad but it does build up when you get to 7-tuples. 2^7=128 while 1.781^7=~57

2012-05-05, 12:22	#75
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 2²·1,553 Posts	I believe it should be possible to modify gsieve to do that. It should pretty much just need the function initprimes modifying. Unfortunately I don't understand that function so I can't do it.

2012-07-21, 21:07	#76
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 2²×1,553 Posts	I have tested n=1000 for 7-tuples upto 34P. I have found 324 quads and 15 quins so far. I have sieved until 81P so testing should go fast for a bit. I hope to have found a run or two of six primes by then. Note this isn't a 6-tuple as a 6-tuple isn't contained within a 7-tuple.

2013-06-22, 19:32	#77
Puzzle-Peter Jun 2009 1010111100₂ Posts	It's me again... I'm trying to adapt the codes in this thread to a new brain-fart of mine, but it seems to be beyond my capabilities. I'd like to search for triplets of the form kx -1, +1, +5 with x being a precomputed constant of several thousands of digits. I know k has to be a multiple of 6. I also know that for the x I'm using to test this, a must end in 2 or 8. That leaves a = 12, 18, 42, 48, 72, 78 etc. which makes two strings of numbers a=30n+12 a=30n+18 with n = [0...chosenlimit] I thought about doing two runs, one for the 30n+12 version and one for 30n+18. I have a PFGW script to precompute a table (text file) which contains lines of p, x MOD p for all primes p below a chosen sieve limit, then use this information to go through an array of booleans and set those to 0 where (a(x MOD p)) equals +1, p-1 or p-5. And this is where the fun starts. I seem to be unable to determine which a values to cancel out. I can find them by hand by simply trying from the low end upwards to the first hit, then go up by steps of the size p, but I don't seem to be able to create the formula for finding the first one. Plus this would probably be much more efficient on a bit array rather than booleans. I know the codes here in this thread contain all the stuff I need. I keep looking at the init_indexes function from Sex_2.pas in post #34, but what is happening there is beyond my grasp. So any hints or help would be greatly appreciated. In case you're wondering about my motivation for this: I'd like to try and go for a triple too large to prove with PRIMO. So I use a number x that makes a N+1 or N-1 proof possible for all three members of the triple. I tried this for a small example (a few dozen digits) to make sure it works by using PFGW and brute force. For larger numbers I need a good sieve though. I have a working PFGW "sieve" script, but it's based on the FACTORIZE function which makes it too slow for large numbers.