Largest nonmersenne prime

How many digits are there in the largest nonmersenne prime?

[rajula]

The correct answer would be that there is no upper bound, but largest known nonmersenne prime has 3918990 digits.

Actually, is there a proof that there are infinite non-Mersenne primes?

[jasonp]

Yes, an ancient one.

[cuBerBruce]

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.

[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.

[literka]

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)).

[CRGreathouse]

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.

[xilman]

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. F_n = 2^2[sup]n[/sup]+1 so F_n-2 is the difference of two squares with factorization (F_n-1) * (F_n-1 - 2), from which we see that no two Fermat numbers share a factor in common, hence the infinitude of primes.

[CRGreathouse]

Originally Posted by xilman

Another proof uses Fermat Numbers. F_n = 2^2[sup]n[/sup]+1 so F_n-2 is the difference of two squares with factorization (F_n-1) * (F_n-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.

[LaurV]

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.