mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2011-05-08, 19:30   #1
aketilander
 
aketilander's Avatar
 
"Ã…ke Tilander"
Apr 2011
Sandviken, Sweden

2×283 Posts
Angry The BIG gap?

Searching for Mersenne Primes is in one sense similar to waiting for an earthquake in Los Angeles. When it comes it will destroy all the fun for a long time. A BIG gap in the series of exponents of Mersenne Primes will also destroy the fun in a similar way I suppose.

It has been more than two years now since the latest discovery of a Mersenne Prime on 2009 April 12. (this is the second biggest timegap between discoveries since 1996 September 3)

If we contemplate the following:

M12 - 127
M13 - 521
4,10

M14 - 607
M15 - 1,279
2,11

M20 - 4,423
M21 - 9,689
2,19

M31 - 216,091
M32 - 756,839
3,50

M35 - 1,398,269
M36 - 2,976,221
2,13

M37 - 3,021,377
M38 - 6,972,593
2,31

We can see that there have been quite a lot of big gaps relatively speaking. The "wave" is now around 53,000,000. And the progress is around 3M a year. So what is the probability that the next Mersenne prime will be larger than M100,000,000. That is, that we won't find the next Mersenne prime in 16-17 years?

It would be even worse if the relative gap between exponents would be as large as between M12 and M13. In that case the next Mersenne Prime would be M176,863,549. And I will most probably be dead when they find it.

Even if we find the next Mersenne Prime tomorrow it would be interesting to know if there will be more big gaps in the series of exponents of the Mersenne primes, and if so how frequently?

Last fiddled with by aketilander on 2011-05-08 at 19:32
aketilander is offline   Reply With Quote
Old 2011-05-08, 20:08   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10AC16 Posts
Default

Speaking of "gaps" and "bunches" as if they mean anything concrete in the context of randomly-distributed data like primes is sure to draw the criticism of some of the serious mathematicians around here. Gaps and bunches happen in any randomly-distributed data, but it means nothing. Trying to predict how big a gap will be, and whether or not that makes it part of a bunch, is only possible in the most general terms.
Quote:
Originally Posted by aketilander View Post
The "wave" is now around 53,000,000. And the progress is around 3M a year. So what is the probability that the next Mersenne prime will be larger than M100,000,000.
For simplicity's sake, let's say the question is precisely, "what is the chance of finding a Mersenne prime with 50,000,000 < p < 100,000,000?".
According to http://primes.utm.edu/notes/faq/NextMersenne.html, (I recommend you read that page, it has lots of details on this subject) "The expected number of Mersenne primes 2[I]p[/I]-1 with p between x and 2x is about egamma." e is Euler's number, the base of the natural logarithm, about 2.718, and gamma is the Euler–Mascheroni constant, about 0.5772. This is not known to be exact, (it's not proven that there are infinite Mersenne primes or composites, let alone how they're distributed) but is conjectured.
That comes to ~1.781 expected primes per doubling of p. The probability of finding at least one prime given that is 1-e^(-1.781), or 83.15%. So the probability that the next largest Mersenne prime after 50M is over 100M is about 16.85%.
Quote:
Originally Posted by aketilander View Post
Even if we find the next Mersenne Prime tomorrow it would be interesting to know if there will be more big gaps in the series of exponents of the Mersenne primes, and if so how frequently?
My educated guess: almost exactly as large and frequently as you'd expect in any Poisson distribution.

Last fiddled with by Mini-Geek on 2011-05-08 at 20:17
Mini-Geek is offline   Reply With Quote
Old 2011-05-08, 21:35   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by aketilander View Post

<senseless numerology deleted>

Even if we find the next Mersenne Prime tomorrow it would be interesting to know if there will be more big gaps in the series of exponents of the Mersenne primes, and if so how frequently?
The current conjecture is that the number of primes between
2^x and 2^(2x) is Poisson distributed with mean exp(gamma) as
x --> oo.

While there is no proof (and no hope of a proof for the near future)
the conjecture is supported by some fairly strong heuristics.

The conjecture gives an exact answer to your question.
R.D. Silverman is offline   Reply With Quote
Old 2011-05-08, 21:37   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post

much common sense deleted...........


My educated guess: almost exactly as large and frequently as you'd expect in any Poisson distribution.
Bingo!
R.D. Silverman is offline   Reply With Quote
Old 2011-05-09, 02:13   #5
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5·359 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Bingo!
Bob:
You need to go see a doctor tomorrow...something is clearly wrong with you, your attitude is much too positive!!!!

It is also going to get a bit easier to find M48; TF has just had a two order of magnitude upgrade.
Christenson is offline   Reply With Quote
Old 2011-05-09, 13:43   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Bingo!
A bit of clarification for those who have not had a course in
probability theory.

The Poisson distribution is a (necessarily discrete) counting function.
It is the counting function that counts the number of arrivals in a given
random interval defined by the exponential waiting time density function
(also known as the Erlang distribution). The actual gaps between M_p are
determined by the Erlang distribution. The count of the number
of M_p in any interval of given length is governed by the Poisson distribution.
R.D. Silverman is offline   Reply With Quote
Old 2011-05-09, 16:27   #7
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

26×37 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
the exponential waiting time density function (also known as the Erlang distribution).
An Erlang distribution is a sum of identical exponential distributions. The number in the sum is called the shape parameter or the stage parameter. So an exponential distribution is a particular case of the Erlang distribution, with 1 stage. The counting function for Erlang distributions with more stages is not Poisson.
wblipp is offline   Reply With Quote
Old 2011-05-10, 09:55   #8
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

11001010010102 Posts
Default

Quote:
Originally Posted by Christenson View Post
Bob:
You need to go see a doctor tomorrow...something is clearly wrong with you, your attitude is much too positive!!!!
Indeed.
A serious case.
If he carries on like this, he'll probably scratch me off
his copious "ignore" list by mistake.

David
davieddy is offline   Reply With Quote
Old 2011-05-10, 10:36   #9
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

Quote:
Originally Posted by Christenson View Post
It is also going to get a bit easier to find M48; TF has just had a two order of magnitude upgrade.
Yes but no need to wet your pants.

An extra 2 bits, say 68-70 (vintage years for me)
will find a factor 2 times in 70, and if no such factor is found,
increase the chance of primality accordingly.

David

BTW do you mean x2 or x10 when you say "order of magnitude"?
davieddy is offline   Reply With Quote
Old 2011-05-10, 12:41   #10
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default Whom the Gods Love Die Young

Quote:
Originally Posted by aketilander View Post
If we contemplate the following:

M12 - 127
M13 - 521
4,10

It would be even worse if the relative gap between exponents would be as large as between M12 and M13. In that case the next Mersenne Prime would be M176,863,549. And I will most probably be dead when they find it.
Indeed.
Alan Turing had 1024 bits of RAM at his disposal, so missed M13.

Mersenne(???), Fermat, Euler and Lucas may also have had
to wait for the news of a new MP from heaven.


That'll be the Day


David

Last fiddled with by davieddy on 2011-05-10 at 12:44
davieddy is offline   Reply With Quote
Old 2011-05-10, 12:47   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

http://oeis.org/A002515 seems to knock out a lot of them ( if it's as simple as in the title then over 100000 under 43112609) is there a 4n+1 equivalent ?
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 06:50.


Fri Oct 22 06:50:26 UTC 2021 up 91 days, 1:19, 1 user, load averages: 1.26, 1.36, 1.32

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.