mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2008-06-13, 11:52   #1
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default Are Mersenne numbers more likely tobe prime?

I have seen it said often that M=2^k-1 (arbitrary k) is a stronger
candidate for primality than other comparably sized numbers.
I've never been convinced, and anyway how much more?

Gauss says the probaility of an arbitrary positive integer n being prime
is 1/ln(n).
Wagstaff and results to date say the probability of an arbitrary
exponent k yielding a prime M=2^k-1 is 2.57/k. (2.57=e^gamma/ln(2)).

Now k = log2(M) = ln(M)/ln(2)

So 2.57/k = e^gamma/ln(M)

gamma=0.5772 so e^gamma=1.78

So if you choose a large integer "at random" the chance
of it being prime is only increased by 1.78 if it happens to
be a Mersenne number.

Comments welcome. (Note that the observation that the number
is odd would double the probability of its being prime).

David

Last fiddled with by davieddy on 2008-06-13 at 12:15
davieddy is offline   Reply With Quote
Old 2008-06-13, 12:40   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3×1,423 Posts
Default

Quote:
Originally Posted by davieddy View Post
Now k = log2(M) = ln(M)/ln(2)
Just thought I'd point out that this isn't exactly right. Since it's 2^k-1, k only approximates log2(M).
Quote:
Originally Posted by davieddy View Post
So if you choose a large integer "at random" the chance
of it being prime is only increased by 1.78 if it happens to
be a Mersenne number.

Comments welcome. (Note that the observation that the number
is odd would double the probability of its being prime).
Since a Mersenne number is, by definition, odd, it seems like this would mean that Mersenne numbers actually have a worse chance than random odd numbers. An odd number would be 2.0 times as likely as random, while a Mersenne number would be 1.78 times? I don't know, it seems like something with my logic is wrong, but that's sure what it looks like.
Quote:
Originally Posted by davieddy View Post
I've never been convinced, and anyway how much more?

Is this poor English, or British English, or just weird but technically proper English? I don't understand the part after the "and" there. What does this mean?

Last fiddled with by Mini-Geek on 2008-06-13 at 12:46
Mini-Geek is offline   Reply With Quote
Old 2008-06-13, 12:49   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1102310 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
Is this poor English, or British English, or just weird but technically proper English? I don't understand the part after the "and" there. What does this mean?
Try punctuating it correctly:

"I've never been convinced and, anyway, how much more?"

Alternatively, try splitting it into two sentences:

"I've never been convinced. Anyway, how much more?"

Paul
xilman is online now   Reply With Quote
Old 2008-06-13, 12:53   #4
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3×1,423 Posts
Default

Quote:
Originally Posted by xilman View Post
Try punctuating it correctly:

"I've never been convinced and, anyway, how much more?"

Alternatively, try splitting it into two sentences:

"I've never been convinced. Anyway, how much more?"

Paul
Is he asking how many more people were never convinced and/or never understood (or rather, as interpreted, stating that many people haven't been convinced/haven't understood)?
Mini-Geek is offline   Reply With Quote
Old 2008-06-13, 13:00   #5
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
Just thought I'd point out that this isn't exactly right. Since it's 2^k-1, k only approximates log2(M).

Since a Mersenne number is, by definition, odd, it seems like this would mean that Mersenne numbers actually have a worse chance than random odd numbers. An odd number would be 2.0 times as likely as random, while a Mersenne number would be 1.78 times? I don't know, it seems like something with my logic is wrong, but that's sure what it looks like.

Is this poor English, or British English, or just weird but technically proper English? I don't understand the part after the "and" there. What does this mean?
Answering repectively:

It was a mild approxiamation.
Your logic was fine. (Hence my post)
Lazy British Engish. Perhaps "anyway" after the "and " might clarify it.

David
davieddy is offline   Reply With Quote
Old 2008-06-13, 13:03   #6
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2×3×13×83 Posts
Default

Quote:
Originally Posted by xilman View Post
Try punctuating it correctly:

"I've never been convinced and, anyway, how much more?"

Alternatively, try splitting it into two sentences:

"I've never been convinced. Anyway, how much more?"

Paul
Thanks Paul. I hadn't read this before I replied to MInigeek.
davieddy is offline   Reply With Quote
Old 2008-06-13, 13:11   #7
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3×1,423 Posts
Default

Quote:
Originally Posted by davieddy View Post
Answering repectively:

It was a mild approxiamation.
Your logic was fine. (Hence my post)
Lazy British Engish. Perhaps "anyway" after the "and " might clarify it.

David
Ah, so the point of your post is that it at least seems that Mersenne numbers are less likely to be prime than random odd numbers.

It's probably the combination of Lazy and British that's confusing me. I can usually tell what people mean with Lazy or British English, but those together is too much. I'm still not really sure what you mean...is this guess correct (from my earlier post):
"Is he asking how many more people were never convinced and/or never understood (or rather, stating that many people haven't been convinced/haven't understood)?"
Mini-Geek is offline   Reply With Quote
Old 2008-06-13, 13:22   #8
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

22·32·179 Posts
Default

Quote:
Originally Posted by davieddy View Post
I have seen it said often that M=2^k-1 (arbitrary k) is a stronger
candidate for primality than other comparably sized numbers.
I've never been convinced, and anyway how much more?
That's a conjecture I'd have trouble believing, since 2^k-1 for composite k is guaranteed not to be prime, and almost all k are composite.

2^p-1 for prime p is a fairly strong candidate for primality because of the various Lagrange's-Theorem results about the shape of its factors; for example, for p>50 it's guaranteed not to be divisible by any prime less than 100, whilst 88% of random numbers are divisible by a prime less than 100.
fivemack is offline   Reply With Quote
Old 2008-06-13, 13:23   #9
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2×3×13×83 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
Ah, so the point of your post is that it at least seems that Mersenne numbers are less likely to be prime than random odd numbers.

It's probably the combination of Lazy and British that's confusing me. I can usually tell what people mean with Lazy or British English, but those together is too much. I'm still not really sure what you mean...is this guess correct (from my earlier post):
"Is he asking how many more people were never convinced and/or never understood (or rather, stating that many people haven't been convinced/haven't understood)?"
I meant "how much more stronger candidate for primality"
or
"I've never been convinced that Mersenne numbers were more
likeky to be be prime. If they are, then by what factor?"
Which I then proceeded to discuss.
I hope to find out how many people agree with me (us?) from
response to this thread.

Last fiddled with by davieddy on 2008-06-13 at 13:32
davieddy is offline   Reply With Quote
Old 2008-06-13, 13:25   #10
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

1001010000012 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
"Is he asking how many more people
No. He is asking how much more likely it is that a Mersenne number is prime. The question is being asked in the context of the assumption that "Mersenne numbers are stronger candidates" means they are more likely to be prime.

However, I think Mersenne numbers are stronger candidates because there is cheap powerful primality test.
wblipp is offline   Reply With Quote
Old 2008-06-13, 13:39   #11
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3·1,423 Posts
Default

Quote:
Originally Posted by davieddy View Post
I meant "how much more stronger candidate for primality"
or
"I've never been convinced that Mersenne numbers were more
likeky to be be prime. If they are, then by what factor?"
Which I then proceeded to discuss.
I hope to find out how many people agree with me (us?) from
response to this thread.
Ok, I get it now.
Quote:
Originally Posted by wblipp View Post
I think Mersenne numbers are stronger candidates because there is cheap powerful primality test.
I don't think there's a doubt that Mersenne numbers are the best to test (with what we know, at least), because it must be 2^p-1 (prime p) and there's very efficient algorithms to factor and test them, but there's still the question of a 2^k-1 with random k being more or less likely than a random odd number of the same size.
After reading the things in this thread, I think that random k is less likely than a random odd number of the same size, but that random p is more likely than a random odd number of the same size, not to mention that it's far easier to test.
Mini-Geek is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ECM on Mersenne numbers with prime exponents biwema Math 9 2021-11-17 23:18
Why have ECM testing for known non-prime Mersenne numbers? sd235 Information & Answers 12 2018-12-06 17:56
Mersenne prime factors of very large numbers devarajkandadai Miscellaneous Math 15 2012-05-29 13:18
Sum of prime divisors for Mersenne Numbers? kurtulmehtap Math 3 2011-01-19 18:48
A property of prime Mersenne numbers under LLT T.Rex Math 12 2005-09-12 07:56

All times are UTC. The time now is 13:57.


Sat Nov 27 13:57:31 UTC 2021 up 127 days, 8:26, 0 users, load averages: 0.66, 0.88, 0.99

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.