mersenneforum.org Largest nonmersenne prime
 Register FAQ Search Today's Posts Mark Forums Read

 2011-05-17, 14:14 #1 Unregistered   2·2,017 Posts Largest nonmersenne prime How many digits are there in the largest nonmersenne prime?
 2011-05-17, 14:47 #2 rajula     "Tapio Rajala" Feb 2010 Finland 32·5·7 Posts The correct answer would be that there is no upper bound, but largest known nonmersenne prime has 3918990 digits.
 2013-05-30, 10:45 #3 Unregistered   25·33·7 Posts Actually, is there a proof that there are infinite non-Mersenne primes?
 2013-05-30, 10:58 #4 jasonp Tribal Bullet     Oct 2004 3×1,163 Posts
2013-05-30, 16:51   #5
cuBerBruce

Aug 2012
Mass., USA

2·3·53 Posts

Quote:
 Originally Posted by Unregistered Actually, is there a proof that there are infinite non-Mersenne primes?
I don't think that ancient proof actually proves there are infinite non-Mersenne primes.

In any case, From Bertrand's Postulate (which is actually a theorem), we know there is always a prime between some integer n and 2n - 2 (with n > 3). Choose any integer k (> 1) and pick n = 2^k. Then, there must be a prime in the range 2^k and 2^(k+1)-2. Clearly this prime can not be a Mersenne prime since there is no Mersenne number in that interval. Since we have infinite choices for k, and the interval defined for each k is disjoint from the others, there must be an infinite number of non-Mersenne primes.

 2013-05-30, 18:10 #6 TheMawn     May 2013 East. Always East. 11·157 Posts Interesting Cuber Bruce does actually bring up an interesting point. If Bertrand's Postulate is in fact true (I've never really looked into it) then he is correct. Without that, though, one could have argued that while there is no largest prime, every prime past a certain bound may be a Mersenne number.
2013-05-30, 20:35   #7
literka

Mar 2010

A616 Posts

Quote:
 Originally Posted by Unregistered Actually, is there a proof that there are infinite non-Mersenne primes?

Another proof:
Assume that every prime is Mersenne from some point.
Let P(x) be the number of prime numbers less than n. This number would be less than all powers of 2 less than x plus some fixed number. In other words, P(x)<C*log(x) for some constant C. This is impossible since log(x)=o(x/log(x))=O(P(x)).

Last fiddled with by literka on 2013-05-30 at 20:58 Reason: Error in text

2013-05-30, 20:52   #8
CRGreathouse

Aug 2006

172616 Posts

Quote:
 Originally Posted by TheMawn Cuber Bruce does actually bring up an interesting point. If Bertrand's Postulate is in fact true (I've never really looked into it) then he is correct. Without that, though, one could have argued that while there is no largest prime, every prime past a certain bound may be a Mersenne number.
Bertrand's postulate is correct, but much more is true: the Prime Number Theorem. Using that it can be shown that almost all primes are non-Mersenne and that the n-th non-Mersenne prime is about n log n.

2013-05-30, 22:36   #9
xilman
Bamboozled!

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

236028 Posts

Quote:
 Originally Posted by CRGreathouse Bertrand's postulate is correct, but much more is true: the Prime Number Theorem. Using that it can be shown that almost all primes are non-Mersenne and that the n-th non-Mersenne prime is about n log n.
Another proof uses Fermat Numbers. Fn = 22[sup]n[/sup]+1 so Fn-2 is the difference of two squares with factorization (Fn-1) * (Fn-1 - 2), from which we see that no two Fermat numbers share a factor in common, hence the infinitude of primes.

2013-05-30, 23:13   #10
CRGreathouse

Aug 2006

2·2,963 Posts

Quote:
 Originally Posted by xilman Another proof uses Fermat Numbers. Fn = 22[sup]n[/sup]+1 so Fn-2 is the difference of two squares with factorization (Fn-1) * (Fn-1 - 2), from which we see that no two Fermat numbers share a factor in common, hence the infinitude of primes.
Sure, but that doesn't give nearly as many non-Mersennes as the PNT.

 2013-05-31, 04:17 #11 LaurV Romulan Interpreter     Jun 2011 Thailand 22·3·11·67 Posts That would work for mersenne numbers too, as Mx and My do not share a common factor if x and y do not share one. So, another simpler proof would be to take any odd composite number z=xy, its correspondent Mz will be composite, and at least one of its prime factors is not mersenne number (easy to prove by binary patterning, you need no math for it), so you get a new prime for every combination of distinct x and y odd primes. Ex: start with 3 and 5, you get M15=32767=7*31*151, from which you got a new non-mersenne prime, 151. You will now get a new non-mersenn prime as a factor of M(3*151) and/or M(5*151). You could use M9, or M11 alone, but assuming we don't know which one is prime and which not, we can take the next odd numbers, 7 and 9, they can't share common factors (as they are consecutive odds, difference is 2), make M63, this can't be prime, as its expo is composed, so its split would give a new prime (in fact, 73, 337, etc, many factors) which is not mersenne. Last fiddled with by LaurV on 2013-05-31 at 04:23

 Similar Threads Thread Thread Starter Forum Replies Last Post sudaprime Miscellaneous Math 11 2018-02-05 08:10 dabaichi News 561 2013-03-29 16:55 Unregistered Information & Answers 24 2008-12-13 08:13 amcfarlane Math 6 2004-12-26 23:15 wfgarnett3 Lounge 7 2002-11-25 06:34

All times are UTC. The time now is 10:02.

Thu Oct 22 10:02:01 UTC 2020 up 42 days, 7:12, 0 users, load averages: 1.44, 1.34, 1.41