20130722, 14:09  #111  
Jun 2009
1010111100_{2} Posts 
Quote:
I am now testing 34, 35 and 36 hash_bits. The best value is probably dependent on pmax as the table updates take more time. So once I know the optimal pmax I can try to find the best hash_bits and q_hash_table_update values. 

20130722, 15:44  #112 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
11×557 Posts 
I think that hash_bits depends on the number of candidates.

20130722, 19:53  #113 
"Robert Gerbicz"
Oct 2005
Hungary
662_{16} Posts 
An impressive fast sieve for a new polynom (the polynom depends on s). With this we avoid all prime divisors less than 50, so we
don't need to sieve them and this gives also more survivors in the same range. Set bound_small_primes=0 (or any value <2), so we can forget the magic 2310*10^9 as a multiple of the optimal range. Code:
Sieve P(s)+a*Q(s)+c for multiple c values, with fixed s=k*b^n+d; P,Q is polynom. Give k: 66735 Give b: 2 Give n: 503 Give d: 1 Give the degree of the P polynom: 3 Give the 0th coefficient of P: 4 Give the 1th coefficient of P: 160 Give the 2th coefficient of P: 77 Give the 3th coefficient of P: 1 Give the degree of the Q polynom: 2 Give the 0th coefficient of Q: 0 Give the 1th coefficient of Q: 1229779565176982820 Give the 2th coefficient of Q: 614889782588491410 Give the number of c values for the sieve: 3 0th c value: 1 1th c value: 1 2th c value: 5 Give start and end value for 'a' (in billions)! 0 18 Give the limit for sieving primes (maxp): 20000000000 Give the name of the file to output the numbers! f503_0_18m0.txt Using primes for wheelsieve up to 0 initialization of all small primes done, primepi(1000000000)=50847534 Prime divisors of Q(s) up to 1000000000: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 initialization of residue and inverse array done up to p=1000000000. In wheel sieve there will be 1 different combinations mod 1 Start sieving for a=0..18000000000. 1/1; #candidates=132548913; 683 sec. so far. Sort the 'a' array. Done the sorting. Sieve for large primes. Use hashbits=31 Use M=1;mres=0; Update the hash table...done Update the hash table...done Update the hash table...done Sieved up to 2000000000; #candidates=120087517; time so far=983 sec. Update the hash table...done Update the hash table...done Update the hash table...done Sieved up to 3000000000; #candidates=113514747; time so far=1162 sec. Update the hash table...done Sieved up to 4000000000; #candidates=109140947; time so far=1315 sec. Update the hash table...done Update the hash table...done Sieved up to 5000000000; #candidates=105902833; time so far=1449 sec. Update the hash table...done Sieved up to 6000000000; #candidates=103346841; time so far=1565 sec. Update the hash table...done Sieved up to 7000000000; #candidates=101250528; time so far=1670 sec. Sieved up to 8000000000; #candidates=99484200; time so far=1769 sec. Update the hash table...done Sieved up to 9000000000; #candidates=97960285; time so far=1862 sec. Update the hash table...done Sieved up to 10000000000; #candidates=96621926; time so far=1951 sec. Sieved up to 11000000000; #candidates=95430272; time so far=2035 sec. Update the hash table...done Sieved up to 12000000000; #candidates=94362206; time so far=2118 sec. Sieved up to 13000000000; #candidates=93392244; time so far=2198 sec. Update the hash table...done Sieved up to 14000000000; #candidates=92506805; time so far=2276 sec. Sieved up to 15000000000; #candidates=91692650; time so far=2351 sec. Sieved up to 16000000000; #candidates=90938256; time so far=2424 sec. Update the hash table...done Sieved up to 17000000000; #candidates=90238817; time so far=2497 sec. Sieved up to 18000000000; #candidates=89584547; time so far=2569 sec. Sieved up to 19000000000; #candidates=88972664; time so far=2639 sec. Update the hash table...done Sieved up to 20000000000; #candidates=88396540; time so far=2709 sec. Output the remaining 'a' values to the abc file, wait... Done. Number of remaining candidates=88396540. Completed in 2736 sec. Let T=614889782588491410=2*3*5*7*11*..*47, the product of primes less than 50. Choose c for that if N=F(c,s) then gcd((N+1)*(N1)*(N+5),T)=1 is true. It gives that if a==c mod T, then for N=F(a,s) it results that N1; N+1 and N+5 is relative prime to T. So choose our polynom F(A*T+c), where A is running. a=A*T+c, plug in this to F(a,s) (replaced s by S): S^3(A*T+c)*S*(S+2)6*S4=(S^3c*S^2+(2*c6)*S4)+A*(T*S^22*T*S)= =(4+(2*c6)*Sc*S^2+S^3)+A*(2*T*ST*S^2) as T=614889782588491410 it means that here all coefficients fits in 63 bits (assuming that c is small). If N=F(A*T+c,S) then (S+2)N and SN+4. (in above post there was a typo for this divisibility). Basically this trick works for every P,Q polynom, just not forget that the coefficients should fit in 63 bits, so in some cases for example you can use only the primes up to 37 and not up to 50. We can say that this is halfway between the pure power and primorial sieves. ps. Still working on a new code, it will use multiple cores in sieve. Using OpenMp to distribute the tasks (gcc supports this). Trivial PariGp script to get a good c value for given s: Code:
fun(s)={T=614889782588491410;c=0;while(1,c++; N=s^3c*s*(s+2)6*s4;p1=N1;p2=N+1;p3=N+5;if(gcd(p1*p2*p3,T)==1,return(c)))} Last fiddled with by R. Gerbicz on 20130722 at 20:05 
20130722, 20:00  #114 
"Robert Gerbicz"
Oct 2005
Hungary
3142_{8} Posts 

20130722, 20:21  #115 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
11·557 Posts 
Would it be possible to automate that trick? These polys are fiddly enough without having to do this each time.
2310*10^9 was only the magic number for bound_small_primes=11. For bound_small_primes=7 it is 210*10^9 etc. 
20130722, 20:58  #116  
"Robert Gerbicz"
Oct 2005
Hungary
2·19·43 Posts 
Quote:
See the entry of PolySieve on http://primes.utm.edu/bios/page.php?id=3934 Last fiddled with by R. Gerbicz on 20130722 at 21:28 

20140131, 00:46  #117 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
17EF_{16} Posts 
I had a look at the code again tonight and in post #113 n# is limited by the coefficients of p and q.
As far as I can see coeff_p and coeff_q are only used %q which is a lli. coeff_p and coeff_q could be converted to a arbitrary precision number and used with only a small performance penalty. You mentioned a couple of bits of new code in the last few posts. Any news? I have been able to find a good few 11tuples and smaller. I have found a few 12tuples but finding them is much harder. I am not getting anywhere near as many candidates for 12tuples as 11tuples after sieving. 
20140203, 04:06  #118 
"Matthew Anderson"
Dec 2010
Oregon, USA
2^{3}×149 Posts 
Hi people interested in ktuples,
I have been working on this problem as well. I have tabulated the smallest known tuples for several patterns, and submitted it to the Online Encyclopedia of Integer Sequences. Lately, I have been working on the 4 different patterns for 9tuples. I have a bit of Maple code that works for me. It is linked here  https://oeis.org/A022546 Also, my page on prime constellations  https://sites.google.com/site/primeconstellations/ Regards, Matt 
20140204, 19:56  #119 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
11×557 Posts 
I have modified polysieve such that it uses gmp for the the coefficients of p and q. This has allowed me to use much larger factorials. It is a little slower in the second stage and is currently limited to 512 bits(just needs a recompile).
I also exposed some more parameters to the cmd line(first stage p limit, primes in wheel sieve). 
20140317, 15:18  #120  
Jun 2009
2^{2}×5^{2}×7 Posts 
Quote:


20140317, 15:53  #121 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
6127_{10} Posts 
To compile with gmp add lgmp into the compile string.
This is the command I use: gcc O3 o polysieve3072_gmp.exe polysieve.c lgmp The order of the commands can make a difference. The wrong order means the lgmp won't be detected. Hopefully cygwin and linux will need the same order. The gmp.h you added might interfere. 
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 