20050316, 19:35  #1 
Jun 2003
Oxford, UK
11110001000_{2} Posts 
Sieving
I thought I would give the group my thoughts about sieving.
I have been sieving the range from n=25228 to 200000. There is either at least one prime in that range or there are none. Geoff or someone else should be able to provide statistics on the average first occurrence prime we have encountered and the probability that a prime can be found in the range of n up to the average occurrence. It seems to me that it is not worth over sieving up to too high, because there is a statistically important chance that a prime will appear before n gets too high. If no prime is found up to a given level, then the remaining file can be sieved further. Typically I only sieve up to 1 billion (for k with a low weight) 2 billion (high weight) before I decide it is worth running pfgw, and this I usually run up to n = 50000 or so. Saves a lot of sieving time and still produces the primes! Regards Robert Smith 
20050325, 01:38  #2 
Mar 2003
New Zealand
10010000101_{2} Posts 
I don't know how to get a formula for the probability of finding a prime in a given interval, if anyone else can do this then it would be useful.
As a rough estimate from looking at the Sierpinski data so far, about one third of the k which survive testing up to exponent N will have a prime between N and 2N. 
20050330, 22:28  #3 
Jun 2003
1,579 Posts 
Have you guys thought of sieving all the k's together. It would be much much much... faster than using newpgen.?
Citrix 
20050331, 15:51  #4  
"William"
May 2003
New Haven
3×787 Posts 
Quote:
Last fiddled with by wblipp on 20050331 at 15:53 

20050402, 15:23  #5  
Mar 2003
New Zealand
2205_{8} Posts 
Quote:
Quote:


20050402, 17:07  #6  
"William"
May 2003
New Haven
3×787 Posts 
Quote:
The weights happen because of the partial coverings that change the probability of divisibility. The weights can be approximated from knowledge of the coverage, but people usually use a sieve of small primes and ratio the number passing the sieve to the random expected remainder. For Base 2, Jack Brennan's Java based Proth Weight Calculator is the best method I know  you can get weights for Riesel numbers by entering negative k values. If you get the source, you could probably adapt it to base 5. I can't find the link for Jack's calculator  I hope it's still online. William 

20050402, 18:14  #7 
"Mark"
Apr 2003
Between here and the
2^{3}×11×71 Posts 
I recommend starting with Paul Jobling, the author of NewPGen and also involved with prothsieve. Another option would be Phil Carmody, who wrote newbgon, which was was by the SOB project before prothsieve.

20050402, 18:48  #8  
Mar 2003
New Zealand
13·89 Posts 
Quote:
Assuming we can do the same for base 5 weights (?), then take W as the Nash weight for k (given in the reservations threads), and the chance of some k*5^n+1 being prime for a < n < b is about W/1750/ln(5)*ln(b/a). For an average base 5 Sierpinski candidate with Nash weight 526, this puts the chance of finding a prime between n=25000 and n=100000 at about 26%. 

20050402, 22:30  #9 
"William"
May 2003
New Haven
939_{16} Posts 
There's probably a factor of 2 error. If I recall correctly, Jack scales his weights so that weight 1 is the probability a random ODD integer is prime, and the weight in the formula needs to be the probability a random integer is prime.
I'd have to dig into then definitions to be sure about the conversion details, but converting Nash weights to Proth weights should be simple once the definitions are clear. William 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Going over 100% during sieving  wombatman  Msieve  4  20130711 15:41 
NFS sieving?  Dubslow  Factoring  8  20120928 06:47 
Line sieving vs. lattice sieving  JHansen  NFSNET Discussion  9  20100609 19:25 
10^420 + 1 sieving  juno1369  Factoring  20  20100428 01:11 
Sieving  OmbooHankvald  Prime Sierpinski Project  4  20050630 07:51 