dxm@lanl.ARPA (11/29/85)
In an assembler programming class once we were asked to write a program
that determined if a given integer was perfect or not. I took a short cut
past the obvious method of finding and adding all the divisors by noticing
that numbers of the form
x = 2^(n-1) * (2^n - 1)
are perfect if n is a prime number. This was true up to the largest
integer the machine could represent. This does not constitute a proof
though, and so I lay the problem before all you net.math.wizards to see if
anyone knows of or can think of a way to prove or disprove the statement
that all numbers of the above form are perfect if n is prime.
Doug Miller dxm@lanl.arpa
....!ihnp4!lanl!dxmbs@faron.UUCP (Robert D. Silverman) (11/30/85)
> In an assembler programming class once we were asked to write a program > that determined if a given integer was perfect or not. I took a short cut > past the obvious method of finding and adding all the divisors by noticing > that numbers of the form > > x = 2^(n-1) * (2^n - 1) > > are perfect if n is a prime number. This was true up to the largest > integer the machine could represent. This does not constitute a proof > though, and so I lay the problem before all you net.math.wizards to see if > anyone knows of or can think of a way to prove or disprove the statement > that all numbers of the above form are perfect if n is prime. > > > Doug Miller dxm@lanl.arpa > ....!ihnp4!lanl!dxm The theorem as you have stated is incorrect. It is necessary that n be prime but that is NOT sufficient. In addition 2^n -1 must also be prime. In fact the interest in Mersenne primes (primes of this form) derives historically from interest in perfect numbers. To see that 2^(n-1) * (2^n -1) is perfect when 2^n-1 is prime simply substitute this expression into the expression for the sum of the divisors which is: S = (p^a+1 -1)/(p-1) * (q^b+1 - 1)/(q-1) * ... a b where the number is question N = p *q *..... To see this we see that the sum of all divisors is: (1 + p + p^2 + p^3 + ...)(1 + q + q^2 + q^3 +...)(...) If we substitute N = 2^(n-1) * (2^n -1) where 2^n -1 is PRIME we obtain: (2^n-1)/(2-1) * ((2^n-1)^2 -1)/(2^n - 2) = (2^n - 1)*2^n = 2N That is to say N is perfect. It is trivial to see that n must be prime else 2^n-1 will factor into say pq and the above substitution won't necessarily work. It is also easy to prove the converse: if N is an even number and it is perfect then it is of the form 2^(n-1)*(2^n -1 ). I'll leave this latter proof as a simple exercize and post the proof in a couple of days. A simple numerical counter example is to note that if n = 11 then 2^11 - 1 = 23.89 and 2^10*23*89 is not perfect. By the way note that both factors of 2^11 - 1 are of the form 2*11n + 1. This is not coincidence. ALL primitive factors of numbers of the form A^n + B^n must be of the form 2kn + 1. This follows trivially from Fermat's little theorem. Bob Silverman (they call me Mr. 9)
cmpbsdb@gitpyr.UUCP (Don Barry) (11/30/85)
In article <34080@lanl.ARPA>, dxm@lanl.ARPA writes: > .... numbers of the form > > x = 2^(n-1) * (2^n - 1) > > are perfect if n is a prime number..... Actually, the result you have hit upon only holds true for those values of n that yield the Mersenne primes. For every mersenne prime, there exists a perfect number - a result established by Euler long ago. Of course, your "x" above goes up so rapidly with n that you can only test the first few values, where the mersennes are happily populated. -- Don Barry (Chemistry Dept) CSnet: cmpbsdb%gitpyr.GTNET@gatech.CSNET Georgia Institute of Technology BITNET: CMPBSDB @ GITVM1 Atlanta, GA 30332 ARPA: cmpbsdb%gitpyr.GTNET%gatech.CSNET@csnet-relay.ARPA UUCP: ...!{akgua,allegra,amd,hplabs,ihnp4,seismo,ut-ngp}!gatech!gitpyr!cmpbsdb
victor@klipper.UUCP (L. Victor Allis) (11/30/85)
In article <34080@lanl.ARPA> dxm@lanl.ARPA writes: >In an assembler programming class once we were asked to write a program >that determined if a given integer was perfect or not. I took a short cut >past the obvious method of finding and adding all the divisors by noticing >that numbers of the form > > x = 2^(n-1) * (2^n - 1) > >are perfect if n is a prime number. This was true up to the largest >integer the machine could represent. This does not constitute a proof >though, and so I lay the problem before all you net.math.wizards to see if >anyone knows of or can think of a way to prove or disprove the statement >that all numbers of the above form are perfect if n is prime. > > > Doug Miller dxm@lanl.arpa > ....!ihnp4!lanl!dxm The restriction is a little stronger : x = 2^(n-1) * (2^n - 1) is perfect if and only if 2^n - 1 is prime. (this implies that n is prime, but not vice versa (take n=11, 2047=23*89) These primes are called Mersenne primes and it is easy to find something about those primes in literature. It is also proved that all even perfect numbers are of this form. It is not known if there are any odd perfect numbers. It is rather easy to proof that x (in the formula above) is prime if and only if 2^n - 1 is prime. Proof: Since 2^n - 1 is prime, the only divisors of x are 1, 2, 4, ..., 2^(n-1), and 1*(2^n - 1), 2*(2^n - 1), 4*(2^n - 1), ... ,2^(n-1)*(2^n - 1). (all divisors of 2^(n-1) multiplied, or not, by 2^n - 1) Since: (1 + 2 + 4 + ... + 2^(n-1)) = 2^n - 1, the sum of all the divisors is: 2^n - 1 + (2^n - 1)*(2^n - 1) = 2^n * (2^n - 1) = 2*x Thus x is perfect (x is counted as a divisor here, thus the sum of the real divisors is 2x - x = x). If 2^n - 1 is not prime, the sum of the divisors is greater than the just obtained result, therefore x is perfect if and only if 2^n - 1 is prime. I believe, it is much harder to proof that all even perfect numbers are of this form, which result is due to Euler if I'm not mistaking. Victor Allis. Free University of Amsterdam The Netherlands.
bill@milford.UUCP (bill) (12/02/85)
> In article <34080@lanl.ARPA> dxm@lanl.ARPA writes: > I believe, it is much harder to proof that all even perfect numbers > are of this form, which result is due to Euler if I'm not mistaking. > Not >that< much harder: let s(n) = the sum of the divisors of n, so s(n) = 2n if and only if n is 'perfect'. We are given that 2n = s(n) and n = k*2^a; so k*2^(a+1) = s(n) = ((2^(a+1)) - 1)*s(k) or s(k) = (k*2^(a+1)) ----------- (2^(a+1)-1) from (k*(2^(a+1)) = (k*(2^(a+1)) - k + k gives: s(k) = k + k ----------- (2^(a+1) - 1) and both parts of the right side divide k (*) but s(k) is the sum of the divisors of k (including k); so there are only two divisors and 1 = (k/(2^(a+1) -1)) or k = 2^(a+1) - 1 is prime. To push on to bigger and better things beyond elementary algebra: a)The proof breaks for n odd at the line marked (*) because then the two parts of the right side represent the same number (k), and the question of odd perfect numbers is still up in the air. b)Anyone want to investigate values n for which the equation s(x) - x = n has no solutions? n=5 apparently is the only odd 'untouchable' number. c)Generalize perfect numbers from s(n) = 2*n to s(n) = i*n; is there any similar formulae for these i-ply perfect numbers? Is there an i for which it can be proven there are an infinite number of i-ply perfect numbers? Is there an upper bound to i?
dole@spar.UUCP (Harry Dole) (12/02/85)
In article <34080@lanl.ARPA> dxm@lanl.ARPA writes: >that numbers of the form > > x = 2^(n-1) * (2^n - 1) > >are perfect if n is a prime number. This was true up to the largest >integer the machine could represent. > > > Doug Miller dxm@lanl.arpa > ....!ihnp4!lanl!dxm This looks like the standard characterization of perfect numbers but not quite: If 2^n - 1 is prime, then x = ( 2^n - 1 ) * ( 2^(n-1) ) is perfect and every even perfect number has this form. It is rumoured that even Euclid knew the first part of this one. Note that for n=4 we have x = 120. Let sigma(y) denote the sum of all positive divisors of y - e.g., sigma(6)=1+2+3+6. Then y is perfect if sigma(y)=2*y. However, sigma(120)=3*120 so 120 is referred to as 3-perfect, not perfect. Did you run this on a 2 bit computer? Harry Dole - Long Live the Categorical Imperative
bill@milford.UUCP (bill) (12/02/85)
> > b)Anyone want to investigate values n for which the equation s(x) - x = n > has no solutions? n=5 apparently is the only odd 'untouchable' number. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Whoops! I guess I forgot the definition of these 'untouchables', for any prime x s(x) - x is obviously = 1; and there's a lot of other odd numbers.
dxm@lanl.ARPA (12/03/85)
> In article <34080@lanl.ARPA> dxm@lanl.ARPA writes: > >that numbers of the form > > > > x = 2^(n-1) * (2^n - 1) > > > >are perfect if n is a prime number. This was true up to the largest > >integer the machine could represent. > > > It is rumoured that even Euclid knew the first part of this one. Note > that for n=4 we have x = 120. Let sigma(y) denote the sum of all > positive divisors of y - e.g., sigma(6)=1+2+3+6. Then y is perfect > if sigma(y)=2*y. However, sigma(120)=3*120 so 120 is referred to as > 3-perfect, not perfect. Did you run this on a 2 bit computer? Actually I ran it on a Radio Shack Color Computer ( Motorola 6809 ) using a simple 16 bit integer representation scheme. I think the reason I didn't catch the "n=4, therefore x=120 which isn't perfect" error is that 4 isn't prime to begin with....so of course I didn't use it. Yours for care in reading the question, :-) Doug Miller
tim@ISM780C.UUCP (Tim Smith) (12/05/85)
In article <687@spar.UUCP> dole@max.UUCP (Harry Dole) writes: >In article <34080@lanl.ARPA> dxm@lanl.ARPA writes: >> >>are perfect if n is a prime number. This was true up to the largest > >that for n=4 we have x = 120. Let sigma(y) denote the sum of all I was not aware that 4 was a prime! -- Tim Smith ihmp4!cithep!tim || ima!ism780!tim || sdcrdcf!ism780c!tim
dole@spar.UUCP (Harry Dole) (12/07/85)
In article <103@ISM780C.UUCP> tim@ISM780C.UUCP (Tim Smith) writes: >In article <687@spar.UUCP> dole@max.UUCP (Harry Dole) writes: >>In article <34080@lanl.ARPA> dxm@lanl.ARPA writes: >>> >>>are perfect if n is a prime number. This was true up to the largest >> >>that for n=4 we have x = 120. Let sigma(y) denote the sum of all > >I was not aware that 4 was a prime! >-- >Tim Smith ihmp4!cithep!tim || ima!ism780!tim || sdcrdcf!ism780c!tim Quite true! Four is not a prime number. Must have been a faulty frontal lobe on Monday. Also, as previously reported, for n=11 the precision on the given machine would be exhausted. As penance, I shall display ignorance and ask questions: How well does the Mersenne formula do as a generator of k-perfect numbers? Are there formulas similar to the Mersenne one that use other primes as a base and generate k-perfects or is the characteristic 2 essential? Harry Dole {decwrl,hplabs}!spar!dole