mersenneforum.org Sieving
 Register FAQ Search Today's Posts Mark Forums Read

 2005-03-16, 19:35 #1 robert44444uk     Jun 2003 Oxford, UK 77016 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
 2005-03-25, 01:38 #2 geoff     Mar 2003 New Zealand 100100001012 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.
 2005-03-30, 22:28 #3 Citrix     Jun 2003 110001001112 Posts Have you guys thought of sieving all the k's together. It would be much much much... faster than using newpgen.? Citrix
2005-03-31, 15:51   #4
wblipp

"William"
May 2003
New Haven

22×32×5×13 Posts

Quote:
 Originally Posted by geoff 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.
You may find this message helpful. It shows that the probability a "random" number will have no factor between c^a and c^b is a/b. The Sierpinski and Riesel numbers have strong effects from partial covering sets for small numbers, but the residual numbers after high levels of trial factoring seem to follow this pattern. I would expect the residual Base 5 numbers to follow the pattern, too.

Last fiddled with by wblipp on 2005-03-31 at 15:53

2005-04-02, 15:23   #5
geoff

Mar 2003
New Zealand

100100001012 Posts

Quote:
 Originally Posted by Citrix Have you guys thought of sieving all the k's together.
Yes we will have to do that eventually. First we need a sieve program, and also an admin/database system to collect the factors and hand out assignments. Does anyone (rogue?) know what would be involved in writing a sieve to do for base 5 numbers what proth_sieve does for base 2 numbers? It sounds like a fair bit of work to me. For the admin system, a plain textfile database program might be enough, but a web form for submitting results would be nice.

Quote:
 Originally Posted by wblipp You may find this message helpful. It shows that the probability a "random" number will have no factor between c^a and c^b is a/b.
This refers to the probability that k*5^n+1 will have a factor p in the interval c^a < p < c^b, but I don't know how to relate this to the probability that some k*5^n+1 will be prime for n in the interval a < n < b.

2005-04-02, 17:07   #6
wblipp

"William"
May 2003
New Haven

44448 Posts

Quote:
 Originally Posted by geoff the probability that some k*5^n+1 will be prime for n in the interval a < n < b.
Sorry - in the midst of a sieving discussion I thought you were asking about the probability of sieving finding a factor. The probability a number is prime will be w(k)/ln(k*5^n+1). Once you have the weight w(k), you can adequately approximate by the integral of w(k)/(n*ln(5)) dn.

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

 2005-04-02, 18:14 #7 rogue     "Mark" Apr 2003 Between here and the 2·5·601 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.
2005-04-02, 18:48   #8
geoff

Mar 2003
New Zealand

13·89 Posts

Quote:
 Originally Posted by wblipp The probability a number is prime will be w(k)/ln(k*5^n+1). Once you have the weight w(k), you can adequately approximate by the integral of w(k)/(n*ln(5)) dn.
Thank you very much! I found Jack Brennan's proth weight calculator, it is base 2 only, but we have the base 5 Nash weights calculated by psieve, it is just a matter of converting them. It seems that dividing the psieve weight of a base 2 k by 1750 gives a similar value to Jack Brennan's calculator. Does anyone know if it is valid to convert the Nash weights given by psieve like this?

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

 2005-04-02, 22:30 #9 wblipp     "William" May 2003 New Haven 234010 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

 Similar Threads Thread Thread Starter Forum Replies Last Post wombatman Msieve 4 2013-07-11 15:41 Dubslow Factoring 8 2012-09-28 06:47 JHansen NFSNET Discussion 9 2010-06-09 19:25 juno1369 Factoring 20 2010-04-28 01:11 OmbooHankvald Prime Sierpinski Project 4 2005-06-30 07:51

All times are UTC. The time now is 05:43.

Sat Nov 28 05:43:58 UTC 2020 up 79 days, 2:54, 3 users, load averages: 1.75, 1.38, 1.31