mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-05-17, 14:14   #1
Unregistered
 

41·103 Posts
Default Largest nonmersenne prime

How many digits are there in the largest nonmersenne prime?
  Reply With Quote
Old 2011-05-17, 14:47   #2
rajula
 
rajula's Avatar
 
"Tapio Rajala"
Feb 2010
Finland

32×5×7 Posts
Default

The correct answer would be that there is no upper bound, but largest known nonmersenne prime has 3918990 digits.
rajula is offline   Reply With Quote
Old 2013-05-30, 10:45   #3
Unregistered
 

1001100001102 Posts
Default

Actually, is there a proof that there are infinite non-Mersenne primes?
  Reply With Quote
Old 2013-05-30, 10:58   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default

Yes, an ancient one.
jasonp is offline   Reply With Quote
Old 2013-05-30, 16:51   #5
cuBerBruce
 
cuBerBruce's Avatar
 
Aug 2012
Mass., USA

2×3×53 Posts
Default

Quote:
Originally Posted by Unregistered View Post
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.
cuBerBruce is offline   Reply With Quote
Old 2013-05-30, 18:10   #6
TheMawn
 
TheMawn's Avatar
 
May 2013
East. Always East.

11·157 Posts
Default 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.
TheMawn is offline   Reply With Quote
Old 2013-05-30, 20:35   #7
literka
 
literka's Avatar
 
Mar 2010

A616 Posts
Default

Quote:
Originally Posted by Unregistered View Post
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
literka is offline   Reply With Quote
Old 2013-05-30, 20:52   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

17·349 Posts
Default

Quote:
Originally Posted by TheMawn View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2013-05-30, 22:36   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

236238 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
xilman is offline   Reply With Quote
Old 2013-05-30, 23:13   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

17×349 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2013-05-31, 04:17   #11
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×7×317 Posts
Default

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
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED! dabaichi News 571 2020-10-26 11:02
probable largest prime. sudaprime Miscellaneous Math 11 2018-02-05 08:10
Largest known prime Unregistered Information & Answers 24 2008-12-13 08:13
Largest 64 bit prime? amcfarlane Math 6 2004-12-26 23:15
need Pentium 4s for 5th largest prime search (largest proth) wfgarnett3 Lounge 7 2002-11-25 06:34

All times are UTC. The time now is 05:04.

Sat Oct 31 05:04:14 UTC 2020 up 51 days, 2:15, 2 users, load averages: 2.20, 1.85, 1.79

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.