rjnoe@ihlts.UUCP (Roger Noe) (10/11/83)
There are somewhere between 25 and 30 Mersenne primes known, right? Can someone mail or post a list of them? (Answers in the form Mnnnnnn are just fine.) Which ones are proven, when (except the smallest ones, obviously) and by whom? Which ones are speculated on and currently under investigation? Additionally, how many perfect numbers are known and what are they? Proven when and by whom? Speculated? Thanks much for any info. -- Roger Noe ...ihnp4!ihlts!rjnoe
chongo@nsc.UUCP (10/14/83)
the 29 known Mersenne primes are given below in terms of p where 2^p-1 was prime, and (2^(p-1)*(2^p-1) was perfect: 2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423 9689 9941 11213 19937 21701 23209 44497 86243 132049 chongo /\../\ (2^23209-1 is prime!) p.s. happy prime hunting :-)
stanwyck@ihuxr.UUCP (Don Stanwyck) (10/17/83)
For some of us less knowledgable people on the net, would someone define
a Mersenne prime, and tell what makes a number "perfect"?
THANX!
Don Stanwyck ihnp4!ihuxr!stanwyckrjnoe@ihlts.UUCP (10/18/83)
Briefly, a Mersenne prime is a prime number of the form (2^n - 1) for some integer n. They are named after some monk who wrote about them a long time ago. (Do I look like a history book?) I don't think the definition of Mersenne primes requires n to be prime, yet I believe all known examples follow that rule. I haven't begun to investigate whether or not n MUST be prime for 2^n-1 to be prime. I don't know if it's been proven one way or another, either. (Actually, I should let nsc!chongo respond to this question--he's the expert.) Clearly not all prime numbers are Mersenne primes. Now, a perfect number is a positive integer equal to the sum of its divisors, excluding itself. The first perfect number is 6=1+2+3. The next is 28=1+2+4+7+14. From there we go to 496, then up to 8128 for the next perfect number. As you can see, these are all generated from Mersenne primes: 6=3*2, 28=7*4, 496=31*16, and 8128=127*64. Given any Mersenne prime we can always generate a perfect number of the form [2^(n-1)]*(2^n - 1). (The proof is quite simple.) The question remains whether or not all perfect numbers can be generated this way. I don't know because I haven't followed number theory very closely at all for a few years. If there is a proof either way (counterexample is simplest for the one way) I would love to be pointed to it. -- Roger Noe ...ihnp4!ihlts!rjnoe
halle1@houxz.UUCP (10/18/83)
Roger's statement concerning the relationship between Mersenne primes and perfect numbers is not quite correct. Not all Mersenne primes produce perfect numbers. (This should be obvious just from counting the known number of each.) However, you have to go a ways before you come to the counter example, so he should be forgiven. It has been shown that all EVEN perfect numbers must be of the form Roger gave: (2^n - 1)*(2^(n-1)), where the first term is a Mersenne prime. It has not yet been shown that all perfect numbers are even, although no odd ones have been discovered yet. (Dr. Matrix notwithstanding. :-) )
rjnoe@ihlts.UUCP (Roger Noe) (10/19/83)
I must contend that I was correct in stating that any prime number of the
form (2^n-1) generates a perfect number of the form (2^n-1)*2^(n-1). Note
I did NOT say that every perfect number is so generated. I am aware that
there may or may not be odd perfect numbers. The proof for my statement
follows:
Given a prime number p=2^n-1 for some integer n, p*2^(n-1) is a perfect number.
PROOF
The divisors of p*2^(n-1) must each either contain p as a factor or not,
in which case they would just be powers of two. The divisors of the
number in question which are not multiples of p are:
1, 2, 4, . . ., 2^(n-1) i.e. 2^m for 0<=m<=n-1
and the divisors which are multiples of p are:
p, 2p, 4p, . . ., p*2^(n-2) i.e. p*2^q for 0<=q<=n-2.
Excluding p*2^(n-1) itself but including 1, this is a complete list of
the divisors of p*2^(n-1) and there can be no duplications because p is
a Mersenne prime.
The sum of these divisors is:
n-1 n-2
SIGMA 2^m + SIGMA p*2^q = (2^n - 1) + p*(2^(n-1) - 1)
m=0 q=0
= p*[1 + 2^(n-1) - 1] = p*2^(n-1)
which of course was the original number. Therefore p*2^(n-1) is perfect.
quod erat demonstrandum
--
Roger Noe ...ihnp4!ihlts!rjnoesonnens@mprvaxa (10/20/83)
Roger Noe gave the definition of a Mersenne prime (a prime of the form 2^n - 1), and correctly said: "Given any Mersenne prime we can always generate a perfect number of the form [2^(n-1)]*(2^n - 1). (The proof is quite simple.)" halle1@houxz disputes this, saying: "Not all Mersenne primes produce perfect numbers. (This should be obvious just from counting the known number of each.) However, you have to go a ways before you come to the counter example, so he should be forgiven." Obvious?!! In fact, it would be extremely interesting if halle1@houxz could produce "the counter example", since there is indeed a simple proof of Roger's statement that has been universally accepted since the time of Euclid. In modern notation, it uses the sigma "sum-of-divisors" function and the fact that sigma is multiplicative. A number m is `perfect' iff sigma(m) = 2m (since sigma counts the number itself). Here's the proof: sigma([2^(n-1)]*[2^n - 1]) = sigma(2^[n-1])*sigma(2^n - 1) = (1 + 2 + 2^2 + 2^3 + ... + 2^[n-1]) * 2^n \* since 2^n - 1 is prime = (2^n - 1) * 2^n = 2 * [2^(n-1)] * (2^n - 1). Q.E.D. Roger's statement leaves a few loose ends though. One is "whether or not n MUST be prime for 2^n-1 to be prime." In fact it must, since: 2^ab - 1 = (2^a - 1) * (2^(a[b-1]) + 2^(a[b-2]) + ... + 1). Another thing is that Euler (I believe) proved the more difficult converse on the form of even perfect numbers, namely that every even perfect number is of the above form. This fact was noted by halle@houxz, who also stated that it is still unknown if all perfect numbers are even. Results on this problem usually end up in the form: if it exists, an odd perfect number must be greater than some value (where the value is some enormous number). Dan Sonnenschein, Microtel Pacific Research, ...microsoft!uw-beaver!mprvaxa!sonnens
chongo@nsc.uucp (Curt Noll) (10/21/83)
N
Mersenne number - an integer of the form M = 2 -1 (N is integer)
N
Mersenne prine - a Mersenne number that is prime
(as is the case for n=2,3,5,7,...,132049)
Perfect number - an natural number N such that the factors of N
less than N sum to N.
N (N-1) N
(if 2 -1 is prime, 2 * ( 2 -1 ) is perfect
and all even perfect numbers are of this form)
<from "The 25th and 26th Mersenne Primes; Mathematics of Computation
Vol 25 #152, Oct 1980, pp 1387-1390>
chongo /\../\chongo@nsc.uucp (Curt Noll) (10/21/83)
a p.s. on the subject: N 2 -1 is prime if and only if N is prime. there are only 29 known Mersenne primes and 29 known perfect numbers. no odd perfect number is known and many people suspect that none exist. i dont know quite off hand what the current restrictions on odd perfect numbers are, but they are very harsh. chongo /\../\
leimkuhl@uiuccsb.UUCP (10/27/83)
#R:ihlts:-22100:uiuccsb:9700011:000:238
uiuccsb!leimkuhl Oct 25 13:54:00 1983
In response 5 or 6 here, chongo writes:
2^N - 1 is prime if and only if N is prime.
For those who don't know better, he meant:
2^N - 1 is prime only if (but not neccessarily if) N is prime.
Ben Leimkuhler
(uiucdcs!uiuccsb!leimkuhl)