Re: probability of primeness (was: Re: Mersenne: splitting up 10m digit primes)
Some of this is likely to be based on the density of primes. The "Prime Number Theorem" shows that the asymptotic density of primes is x / ln x. This density is often written pi(x) [the lower case Greek letter, btw] with pi(x) = (the number of primes less than or equal to x) / x. This is not a trivial result and it has been over 30 years since I looked at it. There is an "elementary" proof [nothing more than calculus] that takes about 40 pages, as I recall. This spends a lot of time on Mobius inversions -- but the details are gone without going back to sources. [It might be just the number of primes less than x, but for large x this is pretty similar.] AFAIK, the question of the number of Mersenne primes is open. (That is: finite or infinite set.) Joth - Original Message - From: Walt Mankowski [EMAIL PROTECTED] To: mersenne [EMAIL PROTECTED] Sent: Tuesday, October 12, 1999 8:33 PM Subject: Re: probability of primeness (was: Re: Mersenne: splitting up 10m digit primes) On Tue, Oct 12, 1999 at 10:53:18PM -0400, Darxus wrote: I'm hoping what I have to say in this email might be important. On Tue, 12 Oct 1999, George Woltman wrote: At 04:12 PM 10/12/99 -0400, you wrote: And how is the probability of finding a prime calculated ? It is roughly how-far-factored-in-bits * 2 / exponent Okay.. what's "how-far-factored-in-bits" mean ? I think trial factoring is done to 2^68 for an exponent around 33 million. Thus your chance is 2 * 68 / 3300. Okay, so as far as we know, each number is equally likely to be prime, and this probability is just based on how much has already been tested ? No, they're saying the probability is based on how deeply they've tried to factor the number before trying the LL test. The more numbers N you rule out as potential factors of M, the more likely M is to be prime. Also, although there are an infinite number of primes, their density thins out considerably as they get large because there are so many more potential factors below them. This applies to primes in general; I don't know if it applies to Mersenne primes. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: splitting up 10m digit primes
At 11:00 AM 10/12/99 -0400, you wrote: I'm okay with that. But I think, if possible, it'd be good to break up primes into like, 1 month chunks, distribute them. I'm sure it'd be possible, I just don't know if/how much it'd impact speed. Not possible. Well, POSSIBLE, but it would actually slow the effort down. The problem is that the test you're performing uses the results of the last "loop" to compute the next value. To make the math simpler, I won't use the actual LL test, but something much simpler: X = 0; DO 32,722,124 times X = X + 1; Now, if you're running this prgram, forget for a moment that you and I can easily look ahead and see that after a thousand times, X is 1000. Unfortunately, there's no "shortcut" in the Lucas-Lehmer test whereby one can look ahead. You have to do this: X = 0 Prior result was 0 so 0 + 1 = 1 Prior result was 1 so 1 + 1 = 2 Prior result was 2 so 2 + 1 = 3 Prior result was 3 so 3 + 1 = 4 Prior result was 4 so 4 + 1 = 5 Prior result was 5 so 5 + 1 = 6 etc. Note that you cannot just "jump ahead" to the 120th loop, because you need to know what the RESULT of the 119th loop was before you can start. And you need the 118th loop to start the 119th, etc, all the way back to loop # 1. If you're testing an exponent of 32,361,147 (for example), you *must* do all 32,361,144 calculations, and they have to be done in order. If you tried to "break them up", with, say, 100,000 "iterations" per user, then the person with 100,001 through 200,000 cannot even start 100,001 until all 100,000 iterations of the last person had been finished. If you tried this, you'd only slow things down, because you'd have to send the "mid-test results" back to Entropia, and then out to the next tester, before they can start. That's what would slow things down -- the back-and-forth of the intermediate results. Yes, it takes a while, but its very much best for one person to just do the whole test, even though it's going to take two years. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: splitting up 10m digit primes
On Tue, 12 Oct 1999, George Woltman wrote: I admire your patience! Thank you :) I think it said 1 in 250,000 chance if finding a prime. So.. on average, it would probably take that one computer, by itself, 241,250 years to find a 10m digit prime. Right ? Define "probably". 241,250 years gives you a 50% chance. Actually it will take longer since the exponents get bigger and bigger. Mathmatical probability... on average, it'll take 50% of the whole thing. At the time I didn't know it took longer toward the end. it'd be good to break up primes into like, 1 month chunks, distribute them. A good idea but the Lucas-Lehmer primality test is a "serial" algorithm. That is, I can't have 33 machines each do a million iterations and get the answer in a month. The second million iterations can't start until the first million complete. I see. Well, we need more people involved either way :) Other thing I gotta calculate... how long it would probably take us if we converted everyone from distributed.net to GIMPS. This is actually the biggest reason why I wanna calculate prize/probability ratio of the 2. I also think it would have been better to award $5k per new prime, of any length. But that's just my opinion. The prize fund was set up by the EFF and the anonymous donor. I agree with you and have tried to encourage an orderly progression by awarding $5,000 to all smaller Mersenne primes (but only if we also find the 10 million digit prime). I understand the contest was not set up by you, but it's good to hear you're trying to incourage $5k/prime. I doubt there are many people who's input could be more valued for this. And how is the probability of finding a prime calculated ? It is roughly how-far-factored-in-bits * 2 / exponent Okay.. what's "how-far-factored-in-bits" mean ? I wanna do a comparison of the prize money to probability ratio between distributed.net's rc5-64 project ($2k prize), GIMPS 10m digit prime ($55k prize). But it'll take me a chunk of time. Any estimates ? There is now a prize for factoring Fermat numbers too. Neat. Where's the info ? Also, the link pertaining to the EFF $100k award on the GIMPS page goes directly to the EFF rules page, instead of http://www.mersenne.org/prize.htm. I think it'd be nice to have a link from the main GIMPS page to something w/ info on all prizes which could be won with GIMPS. You were probably planning on doing that though... However, the best investment is probably to turn off your computer and pocket the $30 you save in electricity! Of course, that's no fun. So pick whichever project gives you the biggest thrill. Alright then, it's a gamble, not an invenstment. Wait, no, I'd leave my computer on all the time anyway. It's still an investment. Yeah yeah, so if I didn't run one of these, the CPU would be off less draw less power. It doesn't matter, I like distributed processing. I'm not in it for the money. __ PGP fingerprint = 03 5B 9B A0 16 33 91 2F A5 77 BC EE 43 71 98 D4 [EMAIL PROTECTED] / http://www.op.net/~darxus Join the Great Internet Mersenne Prime Search http://www.mersenne.org/prime.htm _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: splitting up 10m digit primes
From: [EMAIL PROTECTED] How about an option when you hit "QUIT GIMPS" to upload your P and Q files to Primenet, so someone can at least finish the job? I'm running an exponent in the 33 million area and the save-files are over seven megabytes in size! That would require no small amount of server space... Rick. -+--- [EMAIL PROTECTED] http://www.alienshore.com/ _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: splitting up 10m digit primes
There is now a prize for factoring Fermat numbers too. Neat. Where's the info ? I think Richard Crandall is offering a prize for Fermat factors (http://www.perfsci.com). John Selfridge is also anouncing a prize for factors of various numbers which "ought to be prime". I don't think that there is a website yet. I'll repost the list if you are interested. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: splitting up 10m digit primes
On Tue, 12 Oct 1999, Rick Pali wrote: From: [EMAIL PROTECTED] How about an option when you hit "QUIT GIMPS" to upload your P and Q files to Primenet, so someone can at least finish the job? I'm running an exponent in the 33 million area and the save-files are over seven megabytes in size! That would require no small amount of server space... Wow. I'd been assuming this was basically being done. How unfortunate. I believe I would not have stopped processing the number I was working on to start a 10m digit number if I'd known this... I would have just set it to work on a 10m digit number as soon as it finished the current one. It might be good to make this very clear.. maybe in the client or something, when somebody opts to give up on a number, that their work so far on it will be lost. __ PGP fingerprint = 03 5B 9B A0 16 33 91 2F A5 77 BC EE 43 71 98 D4 [EMAIL PROTECTED] / http://www.op.net/~darxus Join the Great Internet Mersenne Prime Search http://www.mersenne.org/prime.htm _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: splitting up 10m digit primes
As I posted some days back; Anyone who wants to quit an exponent after investing a PII-400-month or more, please contact me, and we'll try to carry it on, using it for the QA effort. It could take some major bandwidth-minutes if more than a few exponents are quit, however. Ken At 04:15 PM 1999/10/12 EDT, [EMAIL PROTECTED] wrote: Well, as completion time gets longer and longer, it becomes more likely that a user will give up in disgust. This could be after several months of work is already complete. How about an option when you hit "QUIT GIMPS" to upload your P and Q files to Primenet, so someone can at least finish the job? _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: probability of primeness (was: Re: Mersenne: splitting up 10m digit primes)
On Tue, Oct 12, 1999 at 10:53:18PM -0400, Darxus wrote: I'm hoping what I have to say in this email might be important. On Tue, 12 Oct 1999, George Woltman wrote: At 04:12 PM 10/12/99 -0400, you wrote: And how is the probability of finding a prime calculated ? It is roughly how-far-factored-in-bits * 2 / exponent Okay.. what's "how-far-factored-in-bits" mean ? I think trial factoring is done to 2^68 for an exponent around 33 million. Thus your chance is 2 * 68 / 3300. Okay, so as far as we know, each number is equally likely to be prime, and this probability is just based on how much has already been tested ? No, they're saying the probability is based on how deeply they've tried to factor the number before trying the LL test. The more numbers N you rule out as potential factors of M, the more likely M is to be prime. Also, although there are an infinite number of primes, their density thins out considerably as they get large because there are so many more potential factors below them. This applies to primes in general; I don't know if it applies to Mersenne primes. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: probability of primeness (was: Re: Mersenne: splitting up 10m digit primes)
I think trial factoring is done to 2^68 for an exponent around 33 million. Thus your chance is 2 * 68 / 3300. Okay, so as far as we know, each number is equally likely to be prime, and this probability is just based on how much has already been tested ? Umm, no. The probability that a number is prime is inversly proportional to the number of digits (or more precisely, the probability that a number on the interval [1,x] is prime is asomtotically 1/ln(x)). However, the probability that a number is prime increases with the amount that has been trial factored (without finding a factor). The precise estimation is based on Mertel's theorem. Ugh... I apparently had bad math teachers, and GIMPS is really making me feel it. I *really* wanna play with these numbers, but I feel intellectually cripled. You certainly seem to have done a good job! You found the two big conjectures about Mersenne distribution. That is Curt Noll's (poorly defined) island theory (your pairs observation), and your observation about it being roughly exponetial (a conjecture due to Wagstaff, and others, though Wagstaff's has hueristic evidence to back it up). I took the numbers from http://www.utm.edu/research/primes/mersenne.shtml#known See http://www.utm.edu/research/primes/notes/faq/NextMersenne.html, as well as http://www.tasam.com/~lrwiman/FAQ-mers, Q4.2. Does anybody see what I'm talking about ? Is there any significance to this ? Has somebody already written extensive papers on this ? Yes, see above. Good work! -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
