mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Sierpinski/Riesel Base 5

Reply
 
Thread Tools
Old 2005-03-16, 19:35   #1
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

77016 Posts
Default 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
robert44444uk is offline   Reply With Quote
Old 2005-03-25, 01:38   #2
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

100100001012 Posts
Default

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.
geoff is offline   Reply With Quote
Old 2005-03-30, 22:28   #3
Citrix
 
Citrix's Avatar
 
Jun 2003

110001001112 Posts
Default

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

Citrix
Citrix is offline   Reply With Quote
Old 2005-03-31, 15:51   #4
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×32×5×13 Posts
Default

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
wblipp is online now   Reply With Quote
Old 2005-04-02, 15:23   #5
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

100100001012 Posts
Default

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.
geoff is offline   Reply With Quote
Old 2005-04-02, 17:07   #6
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

44448 Posts
Default

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
wblipp is online now   Reply With Quote
Old 2005-04-02, 18:14   #7
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2·5·601 Posts
Default

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.
rogue is offline   Reply With Quote
Old 2005-04-02, 18:48   #8
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

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%.
geoff is offline   Reply With Quote
Old 2005-04-02, 22:30   #9
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

234010 Posts
Default

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
wblipp is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Going over 100% during sieving wombatman Msieve 4 2013-07-11 15:41
NFS sieving? Dubslow Factoring 8 2012-09-28 06:47
Line sieving vs. lattice sieving JHansen NFSNET Discussion 9 2010-06-09 19:25
10^420 + 1 sieving juno1369 Factoring 20 2010-04-28 01:11
Sieving 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.