mersenneforum.org Are Mersenne numbers more likely tobe prime?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2008-06-13, 11:52 #1 davieddy     "Lucan" Dec 2006 England 2·3·13·83 Posts 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
2008-06-13, 12:40   #2
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3×1,423 Posts

Quote:
 Originally Posted by davieddy 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 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 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

2008-06-13, 12:49   #3
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

1102310 Posts

Quote:
 Originally Posted by Mini-Geek 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

2008-06-13, 12:53   #4
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3×1,423 Posts

Quote:
 Originally Posted by xilman 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)?

2008-06-13, 13:00   #5
davieddy

"Lucan"
Dec 2006
England

2·3·13·83 Posts

Quote:
 Originally Posted by Mini-Geek 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

2008-06-13, 13:03   #6
davieddy

"Lucan"
Dec 2006
England

2×3×13×83 Posts

Quote:
 Originally Posted by xilman 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.

2008-06-13, 13:11   #7
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3×1,423 Posts

Quote:
 Originally Posted by davieddy 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)?"

2008-06-13, 13:22   #8
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

22·32·179 Posts

Quote:
 Originally Posted by davieddy 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.

2008-06-13, 13:23   #9
davieddy

"Lucan"
Dec 2006
England

2×3×13×83 Posts

Quote:
 Originally Posted by Mini-Geek 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

2008-06-13, 13:25   #10
wblipp

"William"
May 2003
New Haven

1001010000012 Posts

Quote:
 Originally Posted by Mini-Geek "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.

2008-06-13, 13:39   #11
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3·1,423 Posts

Quote:
 Originally Posted by davieddy 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 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.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post biwema Math 9 2021-11-17 23:18 sd235 Information & Answers 12 2018-12-06 17:56 devarajkandadai Miscellaneous Math 15 2012-05-29 13:18 kurtulmehtap Math 3 2011-01-19 18:48 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.