mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2007-09-04, 14:04   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

66618 Posts
Default odds of a Mers. prime being found in a range of n.

Is the following true? Or, at least, assumed to be true?

odds of a random n yielding a Mersenne prime:

ln(n)*ln(2^n-1)

I had a hell of a time coming up with the qualifier(the second line). Corrections are appreciated and encouraged.

Btw, I put this in Information and Answers because it's fairly simple math, and I feel that a lot of people that might not normally visit the Math forum might be interested in this, since it has to do with Mersenne numbers.

Edit: Another question: Assuming GIMPS throughput increases at a sustained rate, basically a parabolical curve, will our speed at finding primes be likely to increase, decrease, or stay exactly the same? (Maybe this one should go in Math, and the answer should come back here when it's decided upon)

Last fiddled with by jasong on 2007-09-04 at 14:15 Reason: Added second question
jasong is offline   Reply With Quote
Old 2007-09-04, 15:15   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10000101010112 Posts
Default

Quote:
Originally Posted by jasong View Post
Is the following true? Or, at least, assumed to be true?

odds of a random n yielding a Mersenne prime:

ln(n)*ln(2^n-1)

I had a hell of a time coming up with the qualifier(the second line). Corrections are appreciated and encouraged.

Btw, I put this in Information and Answers because it's fairly simple math, and I feel that a lot of people that might not normally visit the Math forum might be interested in this, since it has to do with Mersenne numbers.

Edit: Another question: Assuming GIMPS throughput increases at a sustained rate, basically a parabolical curve, will our speed at finding primes be likely to increase, decrease, or stay exactly the same? (Maybe this one should go in Math, and the answer should come back here when it's decided upon)
Quote:
Originally Posted by http://www.mersenne.org/math.htm
What are the chances that the Lucas-Lehmer test will find a new Mersenne prime number? A simple approach is to repeatedly apply the observation that the chance of finding a factor between 2X and 2X+1 is about 1/x. For example, you are testing 210000139-1 for which trial factoring has proved there are no factors less than 264. The chance that it is prime is the chance of no 65-bit factor * chance of no 66 bit factor * ... * chance of no 5000070 bit factor. That is:
64 65 5000069
-- * -- * ... * -------
65 66 5000070
This simplifies to 64 / 5000070 or 1 in 78126. This simple approach isn't quite right. It would give a formula of how_far_factored divided by (exponent divided by 2). However, more rigorous work has shown the formula to be (how_far_factored-1) / (exponent times Euler's constant (0.577...)). In this case, 1 in 91623. Even these more rigourous formulas are unproven.
.
Mini-Geek is offline   Reply With Quote
Old 2007-09-04, 16:42   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
.
This question is anything BUT simple math. The question involves
VERY deep questions in analytic number theory and the true answer
isn't even known, let alone proven. It is *conjectured* on the basis
of some heuristics that Mersenne primes are Poisson distributed and that
the expected number of Mersenne primes between 2^n and 2^(n+1) is
exp(gamma) as n --> oo. However this conjecture is not very "firm".
It is more of an open question than a true conjecture (like (say) the
twin prime conjecture).
R.D. Silverman is offline   Reply With Quote
Old 2007-09-05, 23:35   #4
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default

I apologize,
Quote:
odds of a random n yielding a Mersenne prime
should've been
Quote:
odds of a random n being a Mersenne prime
jasong is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Odds of prime discussion TheCount Conjectures 'R Us 30 2014-09-08 15:26
Odds of prime / expected # of primes gd_barnes Riesel Prime Search 15 2010-10-14 22:00
Odds that a Random Prime is a Number? R.D. Silverman Homework Help 60 2010-10-13 10:31
odds of random number being prime jasong jasong 32 2009-12-01 06:43
Found Octoproths - Range Archive ValerieVonck Octoproth Search 0 2007-02-14 07:24

All times are UTC. The time now is 20:24.

Thu Dec 3 20:24:56 UTC 2020 up 16:36, 1 user, load averages: 1.05, 1.27, 1.23

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.