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

[Puzzle-Peter]

Originally Posted by R. Gerbicz

Peter, could you rerun your test, or post the input parameters? It should be the same output file, no matter what was
the bound_small_primes. Don't know what would be the error, maybe the new code eliminated that also. Now the code prints more information.

Well, whatever happened last week, I could not reproduce it with the new code. The output file is exactly the same no matter what I use for bound_small_primes.

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.

[henryzz]

I think that hash_bits depends on the number of candidates.

[R. Gerbicz]

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.

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 0-th coefficient of P: -4
Give the 1-th coefficient of P: -160
Give the 2-th coefficient of P: -77
Give the 3-th coefficient of P: 1
Give the degree of the Q polynom: 2
Give the 0-th coefficient of Q: 0
Give the 1-th coefficient of Q: -1229779565176982820
Give the 2-th coefficient of Q: -614889782588491410
Give the number of c values for the sieve: 3
0-th c value: 1
1-th c value: -1
2-th 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.

Start with my basic polynom: F(a,s)=-4-6*s-a*s*(s+2)+s^3.

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)*(N-1)*(N+5),T)=1 is true. It gives that if a==c mod T, then for N=F(a,s) it results that N-1; 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*S-4=(S^3-c*S^2+(-2*c-6)*S-4)+A*(-T*S^2-2*T*S)=
=(-4+(-2*c-6)*S-c*S^2+S^3)+A*(-2*T*S-T*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 S|N+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 half-way 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 Pari-Gp script to get a good c value for given s:

fun(s)={T=614889782588491410;c=0;while(1,c++;
N=s^3-c*s*(s+2)-6*s-4;p1=N-1;p2=N+1;p3=N+5;if(gcd(p1*p2*p3,T)==1,return(c)))}

then use just the polynom: (-4+(-2*c-6)*S-c*S^2+S^3)+A*(-2*T*S-T*S^2), where A is running.

[R. Gerbicz]

Originally Posted by henryzz

I think that hash_bits depends on the number of candidates.

No, but I hope the new code will use the number of candidates and the size of memory (what you give the program) to setup different hashtables.

[henryzz]

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.

[R. Gerbicz]

Originally Posted by henryzz

Would it be possible to automate that trick? These polys are fiddly enough without having to do this each time.

That is possible, I'll add that option.

See the entry of PolySieve on http://primes.utm.edu/bios/page.php?id=3934

[henryzz]

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 11-tuples and smaller. I have found a few 12-tuples but finding them is much harder. I am not getting anywhere near as many candidates for 12-tuples as 11-tuples after sieving.

[MattcAnderson]

Hi people interested in k-tuples,

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

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

[henryzz]

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

[Puzzle-Peter]

Originally Posted by henryzz

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

I never programmed C and I'm having problems compiling this. I downloaded gmp.h and managed to modify the include path accordingly. But now I get a lot of "undefined reference" messages for all the mpz_xxx commands. Could anybody please point me to what I need to do? Or provide a 64bit Linux build (static)?

[henryzz]

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.