Largest nonmersenne prime - Page 2

xilman · 2013-05-31, 06:36

Quote:

Originally Posted by CRGreathouse

Sure, but that doesn't give nearly as many non-Mersennes as the PNT.

They both give ${\aleph}_0_$ primes. How many more do you expect to find?

literka · 2013-05-31, 08:18

Quote:

Originally Posted by literka

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

Here we used the fact that P(x) is comparable with x/log(x). This is an advanced theorem and it is not necessary to use it.

To every Mercenne number 2ⁿ-1 corresponds a power of 2 equal 2^n-1 and the correspondence is 1-1.
The sum of reciprocals of prime Mercenne is less than the sum of reciprocals of all Mercenne numbers. Hence it is less than
1+1/2+1/4+...+1/2ⁿ+...=2
So, the sum of reciprocals of prime Mercenne numbers is a convergent series. This shows that there are infinitely many non-Mercenne primes, since series of reciprocals of all primes is divergent.

dash1729 · 2020-08-15, 20:03

Quote:

Originally Posted by Unregistered

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

The exponent of a Mersenne prime must itself be prime. So if we assume there are only finitely many non-Mersenne primes, then all primes except a finite number must be in the form $2^{2^n-1}-1$ for $n\ge 2$ . Let the product of those finitely many primes not in that form be $K$ , and pick $M$ so that $2^{M-1}>K$ . Consider (as in the standard proof that there are infinitely many primes) adding $1$ to the product of all primes up to and including $2^{2^M-1}-1$ --that number must be no greater than:

$1+K\prod_{n=2}^M (2^{2^n-1}-1)$

This is less than:

$1+K\prod_{n=2}^M (2^{2^n-1})$

Given that $2^{M-1}>K$ this in turn is less than:

$1+2^{M-1}\prod_{n=2}^M (2^{2^n-1})=1+\prod_{n=2}^M 2^{2^n}=1+2^{2^{M+1}-3}\lt 2^{2^{M+1}-1}-1$

However, using a similar argument as in the standard proof of the infinitude of primes, any prime divisor of this number must be greater than $2^{2^{M}-1}-1$ and hence must be at least $2^{2^{M+1}-1}-1$ . This is a contradiction, so the assumption that there are only finitely many non-Mersenne primes is incorrect. Hence there are infinitely many non-Mersenne primes.

retina · 2020-08-16, 14:16

Quote:

Originally Posted by dash1729

... any prime divisor of this number must be greater than $2^{2^{M}-1}-1$ ...

How do you know that there is a divisor? Perhaps all sufficiently large Mersenne numbers are prime?

Or, of course, perhaps I just misunderstand something?

BudgieJane · 2020-08-16, 15:58

Quote:

Originally Posted by retina

How do you know that there is a divisor? Perhaps all sufficiently large Mersenne numbers are prime?

You seem to have misunderstood. If your sufficiently large Mersenne number is 2^N-1, where N is even then the number is composite. If the Mersenne number is prime then N is prime, so you should take a look at 2^N+1-1, which will be composite.

dash1729 · 2020-08-16, 17:38

Quote:

Originally Posted by retina

How do you know that there is a divisor? Perhaps all sufficiently large Mersenne numbers are prime?

Or, of course, perhaps I just misunderstand something?

I know that because all numbers except $1$ have a prime divisor. That divisor in some cases will be the number itself (i.e. the number is prime) but this doesn't affect the proof. "The number" referred to here is one plus the product of all prime numbers (Mersenne or not) up to and including a given large Mersenne prime. That number certainly has a prime divisor, as do all numbers greater than one.

All sufficiently large Mersenne numbers certainly cannot be prime, since for a Mersenne number in the form $2^n-1$ to be prime it requires that $n$ also be prime. My proof relies heavily on the fact that if "most" primes are Mersenne primes, then said Mersenne primes will themselves be especially sparse due to that requirement that $n$ be prime.

a1call · 2020-08-16, 19:05

Nice proof. But I wished people would start including numeric examples or textual descriptions in addition to mathematical symbols. I am not particularly bright and was completely lost in your formulaic proof until you decided it in simple text.

Assuming that all primes are Mersennes except for 2 and 5 then
2.5.3.7.31+/-1 will be an even number with a prime factor different from 3, 5, 7, or 31. But not necessary smaller than 31. So it could still be a Mersenne prime.

Unless your formulaic proof addresses that then it needs more work. Or am I missing something as is the usual case.
ETA Replaced 3 with 5

dash1729 · 2020-08-16, 19:45

Quote:

Originally Posted by a1call

Nice proof. But I wished people would start including numeric examples or textual descriptions in addition to mathematical symbols. I am not particularly bright and was completely lost in your formulaic proof until you decided it in simple text.

Assuming that all primes are Mersennes except for 2 and 5 then
2.5.3.7.31+/-1 will be an even number with a prime factor different from 3, 5, 7, or 31. But not necessary smaller than 31. So it could still be a Mersenne prime.

Unless your formulaic proof addresses that then it needs more work. Or am I missing something as is the usual case.
ETA Replaced 3 with 5

I agree that a numeric example always helps. However in this specific case the numbers get very large very fast making it tough to write them out in full. I'm claiming that if the set of all non-Mersenne primes is finite, then "almost all" primes must be not just Mersenne primes--primes in the form $2^p-1$ for some prime $p$ --but double Mersenne primes in the form $2^{2^p-1}-1$ . In practice, only four double Mersenne primes are known, the largest of which has $38$ digits, so it is tough to illustrate the concept with real numbers written out in full.

In the example you give, $2*5*3*7*31 \pm 1$ , it happens that $3$ , $7$ , and $31$ are Mersenne primes as I think you intended, but they aren't double Mersenne primes except for $7$ . Also $2*5*3*7*31 \pm 1$ is odd, not even.

A better example might be $2*3*5*31*7*127 \pm 1$ where the last two primes $7$ and $127$ are double Mersenne primes. If we assume that $2$ , $3$ , $5$ , and $31$ are the only primes that aren't double Mersenne primes, then $K=930$ as in my proof and we can set $M=11$ . The problem is that even starting with these relatively small numbers, my proof will then involve the double Mersenne number (not a prime though) $2^{2^{12}-1}-1$ which is tough to write out in full. So being comfortable with a certain level of abstraction is necessary to understand the proof.

a1call · 2020-08-16, 20:54

Quote:

Originally Posted by dash1729

I agree that a numeric example always helps. However in this specific case the numbers get very large very fast making it tough to write them out in full. I'm claiming that if the set of all non-Mersenne primes is finite, then "almost all" primes must be not just Mersenne primes--primes in the form $2^p-1$ for some prime $p$ --but double Mersenne primes in the form $2^{2^p-1}-1$ . In practice, only four double Mersenne primes are known, the largest of which has $38$ digits, so it is tough to illustrate the concept with real numbers written out in full.

In the example you give, $2*5*3*7*31 \pm 1$ , it happens that $3$ , $7$ , and $31$ are Mersenne primes as I think you intended, but they aren't double Mersenne primes except for $7$ . Also $2*5*3*7*31 \pm 1$ is odd, not even.

A better example might be $2*3*5*31*7*127 \pm 1$ where the last two primes $7$ and $127$ are double Mersenne primes. If we assume that $2$ , $3$ , $5$ , and $31$ are the only primes that aren't double Mersenne primes, then $K=930$ as in my proof and we can set $M=11$ . The problem is that even starting with these relatively small numbers, my proof will then involve the double Mersenne number (not a prime though) $2^{2^{12}-1}-1$ which is tough to write out in full. So being comfortable with a certain level of abstraction is necessary to understand the proof.

Thanks for putting up with me so far and thank you for the odd/even correction.

I think I can follow up to 2^(2^12-1)-1.
Can you please continue with the numeric example (without actually calculating the values) from then on. How does that result in non-double-Mersenne which is different from 2, 3, 5 and 31.
I will reread your proof in case I can figure it out on my own.
Thank you for your patience.

ETA Please use text instead of LaTex to save time and typing.
ETA II I think I'm just not going to get it. So please feel free ti ignore my post.

a1call · 2020-08-16, 21:08

Please ignore my post. Thanks.

retina · 2020-08-16, 23:35

Quote:

Originally Posted by BudgieJane

You seem to have misunderstood. If your sufficiently large Mersenne number is 2^N-1, where N is even then the number is composite. If the Mersenne number is prime then N is prime, so you should take a look at 2^N+1-1, which will be composite.

Got it. Thanks.

2020-08-16, 19:05	#18
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 2063₁₀ Posts	Nice proof. But I wished people would start including numeric examples or textual descriptions in addition to mathematical symbols. I am not particularly bright and was completely lost in your formulaic proof until you decided it in simple text. Assuming that all primes are Mersennes except for 2 and 5 then 2.5.3.7.31+/-1 will be an even number with a prime factor different from 3, 5, 7, or 31. But not necessary smaller than 31. So it could still be a Mersenne prime. Unless your formulaic proof addresses that then it needs more work. Or am I missing something as is the usual case. ETA Replaced 3 with 5 Last fiddled with by a1call on 2020-08-16 at 19:10

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

2020-08-16, 21:08	#21
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 2,063 Posts	Please ignore my post. Thanks.