mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

View Poll Results: Will GIMPS Ever Discover a New Prime Through Doublecheck?
Yes 29 45.31%
No 35 54.69%
Voters: 64. You may not vote on this poll

Reply
 
Thread Tools
Old 2006-10-02, 03:14   #1
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2×3×293 Posts
Default Will GIMPS Ever Discover a New Prime Through Doublecheck?

The question says it all. What do you think?
jinydu is offline   Reply With Quote
Old 2006-10-02, 12:44   #2
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

22·112 Posts
Default

Isn't it true that 1% of first time LL tests end up being wrong?
JuanTutors is offline   Reply With Quote
Old 2006-10-02, 13:17   #3
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2·33·149 Posts
Default

Quote:
Originally Posted by dominicanpapi82 View Post
Isn't it true that 1% of first time LL tests end up being wrong?
I hope not, then there would be about 1000 more primes out there. About 1% have an incorrect risidual.
Uncwilly is offline   Reply With Quote
Old 2006-10-02, 15:43   #4
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
I hope not, then there would be about 1000 more primes out there. About 1% have an incorrect risidual.
I haven't seen any analisys lately, but i seem to remember that this percentage is actually higher, and only gets higher as exponents get larger.

I remember something like 3-4%
smh is offline   Reply With Quote
Old 2006-10-02, 20:00   #5
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10000101010112 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
Quote:
Originally Posted by dominicanpapi82 View Post
Isn't it true that 1% of first time LL tests end up being wrong?
I hope not, then there would be about 1000 more primes out there. About 1% have an incorrect risidual.
You're both right. 1% of them are wrong, meaning that they have an incorrect residual. Uncwilly just thought dominicanpapi82 meant that 1% are incorrectly saying that it's composite.

I voted that another prime wouldn't be found, btw, since saying there is another prime is saying that out of the already extremely low chance of any exponent being prime, you add that a computer already, with 99% certainty, found that it's composite.
Mini-Geek is offline   Reply With Quote
Old 2006-10-03, 02:38   #6
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

22·112 Posts
Default

Well if the probability of an erroneous result stays at 1%, then the probability that a given set of exponents that would yeild a Mersenne primes actually give us at least one incorrect result goes above 50% only after about 69 exponents.
JuanTutors is offline   Reply With Quote
Old 2006-10-03, 10:20   #7
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3×277 Posts
Default

So far, only 44 such exponents have been found. I'd argue that only the last few (say, those 10 found by GIMPS) have the 1% error rate; maybe it was lower in the beginning.
Hence, we would have a way less than 50% chance that we've already missed a prime.
Mystwalker is offline   Reply With Quote
Old 2006-10-08, 06:24   #8
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by dominicanpapi82 View Post
Well if the probability of an erroneous result stays at 1%, then the probability that a given set of exponents that would yeild a Mersenne primes
What is meant by a set of exponents that "would" yield a Mersenne prime? That the set actually does include a Mersenne prime, or that we haven't yet determined for sure that it does not contain a Mersenne prime? (I'll assume the latter for my next remarks.)

Quote:
actually give us at least one incorrect result goes above 50% only after about 69 exponents.
... but only if you remember that "incorrect result" does not mean that a number has been erroneously reported to be composite when it is actually prime.

As explained above, the 1% error rate refers to incorrect residues, not to a prime-versus-composite determination. Such errors will almost always (99.999+ %) be a matter of two different nonzero residues (composite either way), not a nonzero residue (composite) vs. a zero residue (prime).

If there's no evidence that an incorrect nonzero residue is more or less likely than average to correspond to a zero residue when corrected, then it's just as if that number had not been LL-tested. So the probability of finding a Mersenne prime among exponents whose only LL tests were incorrect is just the same as the probability of finding a Mersenne prime among numbers of similar size that have not been tested at all. That implies that about 1% of all Mersenne primes (assuming the error rate stays 1%) may be found among exponents whose first LL tests were reported with an incorrect residue.

(However, I stll voted "No" in the poll above because I think there's a high probability that GIMPS will dissolve before a Mersenne prime is found by a DC.)

Last fiddled with by cheesehead on 2006-10-08 at 06:40
cheesehead is offline   Reply With Quote
Old 2006-10-09, 06:31   #9
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

1111001002 Posts
Default

Quote:
Originally Posted by cheesehead View Post
What is meant by a set of exponents that "would" yield a Mersenne prime?
What I meant was looking at the set of primes p such that Mp is actually a Mersenne prime.
JuanTutors is offline   Reply With Quote
Old 2006-10-10, 00:34   #10
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts
Default

Quote:
Originally Posted by dominicanpapi82 View Post
What I meant was looking at the set of primes p such that Mp is actually a Mersenne prime.
Oh, so you mean that all the exponents in the set correspond to Mersenne primes.

Yes, in that case, as you wrote, "the probability that a given set of exponents that would yield a Mersenne primes actually give us at least one incorrect result goes above 50% only after about 69 exponents". But that's true of any set of exponents whether or not any exponent in the set corresponds to a Mersenne prime, as long as "incorrect result" is understood to mean "incorrect residue".

That is, for any set of 69 or more L-L tests each of which has an error probability of 1%, the probability of at least one erroneous result (residue) from that set is above 50%.

So, getting back to your special case of all exponents corresponding to Mersenne primes, if we LL-test all Mersenne primes from M45 through M113 once each, the chance that one of those residues will be erroneous (= nonzero, in this special case), and thus the chance that the primality would be discovered only on a doublecheck (or later), is greater than 50%.

Last fiddled with by cheesehead on 2006-10-10 at 01:28
cheesehead is offline   Reply With Quote
Old 2006-10-10, 14:50   #11
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

23×3×227 Posts
Default

So far 10 primes found, so only 59 primes to go to get >50% chance of a bad result returned for a real prime. So after M103rd we expect >50% chance that one was missed by the first time check? All other exponents can be ignored because false positives (ie. zero residual) are excluded and incorrect negatives (non-zero but wrong residual) are discarded.

To answer the question given in the topic title, at a rate of 1 prime discovered each year (the current average rate) that would be 59 years to give >50% probability. So I predict year 2065 will be the year a DC finds a prime.
retina is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Nothing left to discover? Flatlander Science & Technology 3 2011-09-22 11:19
Which Discover magazine article is the fake? jasong jasong 3 2011-04-06 21:25
Will GIMPS Ever Discover Two Primes Out of Sequence? jinydu Lounge 11 2009-06-06 16:40
Will Mike Discover M41? jinydu Lounge 7 2004-05-29 00:55
Who'll discover M41? 1260 Lounge 9 2004-05-18 13:43

All times are UTC. The time now is 07:52.

Fri Jun 5 07:52:57 UTC 2020 up 72 days, 5:26, 0 users, load averages: 1.39, 1.33, 1.20

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.