mersenneforum.org How do you efficiently sieve for prime 3/4-tuples?
 Register FAQ Search Today's Posts Mark Forums Read

2012-04-27, 18:33   #67
Puzzle-Peter

Jun 2009

2AB16 Posts

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%?

2012-04-27, 20:01   #68
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

5,857 Posts

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.

 2012-04-28, 05:49 #69 Puzzle-Peter     Jun 2009 683 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-04-30, 12:21   #70
biwema

Mar 2004

3·127 Posts

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.

2012-04-30, 20:01   #71
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

133418 Posts

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.
Attached Files
 odds of prime3.zip (10.0 KB, 94 views)

Last fiddled with by henryzz on 2012-04-30 at 20:12 Reason: explanation of 1.781

 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-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)?
 2012-04-30, 23:01 #73 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 5,857 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-03, 06:13 #74 Cybertronic     Jan 2007 Germany 22·3·52 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 k*p#+a1,a2,... ? best, Norman Last fiddled with by Cybertronic on 2012-05-03 at 06:15
 2012-05-05, 12:22 #75 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 5,857 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 Cambridge (GMT/BST) 16E116 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 10101010112 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 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 And now for something completely different 2 2017-04-28 00:08 fivemack Math 27 2015-12-12 18:42 tapion64 GPU Computing 7 2014-04-10 06:15 Unregistered Information & Answers 2 2010-05-25 20:51 Sloth Prime Sierpinski Project 1 2006-05-10 02:02

All times are UTC. The time now is 17:50.

Thu Apr 15 17:50:18 UTC 2021 up 7 days, 12:31, 1 user, load averages: 2.15, 1.93, 2.02