Sieving

[robert44444uk]

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

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

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.

[Citrix]

Have you guys thought of sieving all the k's together. It would be much much much... faster than using newpgen.?

Citrix

[wblipp]

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.

[geoff]

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.

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.

[wblipp]

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

[rogue]

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.

[geoff]

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

[wblipp]

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