Friday, August 03, 2007
Perfect numbers
What is a perfect number?
Perfect numbers are positive integers n such that
n==s(n),
(1)
where s(n) is the restricted divisor function (i.e., the sum of proper divisors of n), or equivalently
sigma(n)==2n,
(2)
where sigma(n) is the divisor function (i.e., the sum of divisors of n including n itself). For example, the first few perfect numbers are 6, 28, 496, 8128, ... (Sloane's A000396), since
6 = 1+2+3
(3)
28 = 1+2+4+7+14
(4)
496 = 1+2+4+8+16+31+62+124+248,
(5)
etc. The first few perfect numbers P_n are summarized in the following table together with their corresponding indices p (see below).
n p_n P_n
1 2 6
2 3 28
3 5 496
4 7 8128
5 13 33550336
6 17 8589869056
7 19 137438691328
8 31 2305843008139952128
Perfect numbers were deemed to have important numerological properties by the ancients, and were extensively studied by the Greeks, including Euclid.
Perfect numbers are also intimately connected with a class of numbers known as Mersenne primes, which are prime numbers of the form M_p==2^p-1. This can be demonstrated by considering a perfect number P of the form P==q.2^(p-1) where q is prime. By definition of a perfect number P,
sigma(P)==2P.
(6)
Now note that there are special forms for the divisor function sigma(n)
sigma(q)==q+1
(7)
for n==q a prime, and
sigma(2^alpha)==2^(alpha+1)-1
(8)
for n==2^alpha. Combining these with the additional identity
sigma(p_1^(alpha_1)p_2^(alpha_2)...p_r^(alpha_r))==sigma(p_1^(alpha_1))sigma(p_2^(alpha_2))...sigma(p_r^(alpha_r)),
(9)
where n==p_1^(alpha_1)p_2^(alpha_2)...p_r^(alpha_r) is the prime factorization of n, gives
sigma(P) = sigma(q.2^(p-1))
(10)
= sigma(q)sigma(2^(p-1))
(11)
= (q+1)(2^p-1).
(12)
But sigma(P)==2P, so
(q+1)(2^p-1)==2q.2^(p-1)==q.2^p.
(13)
Solving for q then gives
q==2^p-1.
(14)
Therefore, if P is to be a perfect number, q must be of the form q==2^p-1. Defining M_p as a prime number of the form M_P=q==2^p-1, it then follows that
P_p==1/2(M_p+1)M_p==2^(p-1)(2^p-1)
(15)
is a perfect number, as stated in Proposition IX.36 of Euclid's Elements (Dickson 1957, p. 3; Dunham 1990).
While many of Euclid's successors implicitly assumed that all perfect numbers were of the form (15) (Dickson 1952, pp. 3-33), the precise statement that all even perfect numbers are of this form was first considered in a 1638 letter from Descartes to Mersenne (Dickson 2005, p. 12). Proof or disproof that Euclid's construction gives all possible even perfect numbers was proposed to Fermat in a 1658 letter from Frans van Schooten (Dickson 2005, p. 14). In a posthumous paper, Euler (Euler 1849) provided the first proof that Euclid's construction gives all possible even perfect numbers (Dickson 2005, p. 19).
It is not known if any odd perfect numbers exist, although numbers up to 10^(300) have been checked (Brent et al. 1991; Guy 1994, p. 44) without success.
All even perfect numbers P>6 are of the form
P==1+9T_n,
(16)
where T_n is a triangular number
T_n==1/2n(n+1)
(17)
such that n==8j+2 (Eaton 1995, 1996). In addition, all even perfect numbers are hexagonal numbers, so it follows that even perfect numbers are always the sum of consecutive positive integers starting at 1, for example,
6 = sum_(n==1)^(3)n
(18)
28 = sum_(n==1)^(7)n
(19)
496 = sum_(n==1)^(31)n
(20)
(Singh 1997), where 3, 7, 31, ... (Sloane's A000668) are simply the Mersenne primes. In addition, every even perfect number P is of the form 2^(p-1)(2^p-1), so they can be generated using the identity
sum_(k==1)^(2^((p-1)/2))(2k-1)^3==2^(p-1)(2^p-1)==P.
(21)
It is known that all even perfect numbers (except 6) end in 16, 28, 36, 56, 76, or 96 (Lucas 1891) and have digital root 1. In particular, the last digits of the first few perfect numbers are 6, 8, 6, 8, 6, 6, 8, 8, 6, 6, 8, 8, 6, 8, 8, ... (Sloane's A094540), where the region between the 38th and 41st terms has been incompletely searched as of June 2004.
The sum of reciprocals of all the divisors of a perfect number is 2, since
n+...+c+b+a_()_(n)==2n
(22)
n/a+n/b+...==2n
(23)
1/a+1/b+...==2.
(24)
If s(n)>n, n is said to be an abundant number. If s(n)1, n is said to be a multiperfect number of order k.
The only even perfect number of the form x^3+1 is 28 (Makowski 1962).
Ruiz has shown that n is a perfect number iff
sum_(i==1)^(n-2)i|_n/i_|==1+sum_(i==1)^(n-1)i|_(n-1)/i_|.
Perfect numbers are positive integers n such that
n==s(n),
(1)
where s(n) is the restricted divisor function (i.e., the sum of proper divisors of n), or equivalently
sigma(n)==2n,
(2)
where sigma(n) is the divisor function (i.e., the sum of divisors of n including n itself). For example, the first few perfect numbers are 6, 28, 496, 8128, ... (Sloane's A000396), since
6 = 1+2+3
(3)
28 = 1+2+4+7+14
(4)
496 = 1+2+4+8+16+31+62+124+248,
(5)
etc. The first few perfect numbers P_n are summarized in the following table together with their corresponding indices p (see below).
n p_n P_n
1 2 6
2 3 28
3 5 496
4 7 8128
5 13 33550336
6 17 8589869056
7 19 137438691328
8 31 2305843008139952128
Perfect numbers were deemed to have important numerological properties by the ancients, and were extensively studied by the Greeks, including Euclid.
Perfect numbers are also intimately connected with a class of numbers known as Mersenne primes, which are prime numbers of the form M_p==2^p-1. This can be demonstrated by considering a perfect number P of the form P==q.2^(p-1) where q is prime. By definition of a perfect number P,
sigma(P)==2P.
(6)
Now note that there are special forms for the divisor function sigma(n)
sigma(q)==q+1
(7)
for n==q a prime, and
sigma(2^alpha)==2^(alpha+1)-1
(8)
for n==2^alpha. Combining these with the additional identity
sigma(p_1^(alpha_1)p_2^(alpha_2)...p_r^(alpha_r))==sigma(p_1^(alpha_1))sigma(p_2^(alpha_2))...sigma(p_r^(alpha_r)),
(9)
where n==p_1^(alpha_1)p_2^(alpha_2)...p_r^(alpha_r) is the prime factorization of n, gives
sigma(P) = sigma(q.2^(p-1))
(10)
= sigma(q)sigma(2^(p-1))
(11)
= (q+1)(2^p-1).
(12)
But sigma(P)==2P, so
(q+1)(2^p-1)==2q.2^(p-1)==q.2^p.
(13)
Solving for q then gives
q==2^p-1.
(14)
Therefore, if P is to be a perfect number, q must be of the form q==2^p-1. Defining M_p as a prime number of the form M_P=q==2^p-1, it then follows that
P_p==1/2(M_p+1)M_p==2^(p-1)(2^p-1)
(15)
is a perfect number, as stated in Proposition IX.36 of Euclid's Elements (Dickson 1957, p. 3; Dunham 1990).
While many of Euclid's successors implicitly assumed that all perfect numbers were of the form (15) (Dickson 1952, pp. 3-33), the precise statement that all even perfect numbers are of this form was first considered in a 1638 letter from Descartes to Mersenne (Dickson 2005, p. 12). Proof or disproof that Euclid's construction gives all possible even perfect numbers was proposed to Fermat in a 1658 letter from Frans van Schooten (Dickson 2005, p. 14). In a posthumous paper, Euler (Euler 1849) provided the first proof that Euclid's construction gives all possible even perfect numbers (Dickson 2005, p. 19).
It is not known if any odd perfect numbers exist, although numbers up to 10^(300) have been checked (Brent et al. 1991; Guy 1994, p. 44) without success.
All even perfect numbers P>6 are of the form
P==1+9T_n,
(16)
where T_n is a triangular number
T_n==1/2n(n+1)
(17)
such that n==8j+2 (Eaton 1995, 1996). In addition, all even perfect numbers are hexagonal numbers, so it follows that even perfect numbers are always the sum of consecutive positive integers starting at 1, for example,
6 = sum_(n==1)^(3)n
(18)
28 = sum_(n==1)^(7)n
(19)
496 = sum_(n==1)^(31)n
(20)
(Singh 1997), where 3, 7, 31, ... (Sloane's A000668) are simply the Mersenne primes. In addition, every even perfect number P is of the form 2^(p-1)(2^p-1), so they can be generated using the identity
sum_(k==1)^(2^((p-1)/2))(2k-1)^3==2^(p-1)(2^p-1)==P.
(21)
It is known that all even perfect numbers (except 6) end in 16, 28, 36, 56, 76, or 96 (Lucas 1891) and have digital root 1. In particular, the last digits of the first few perfect numbers are 6, 8, 6, 8, 6, 6, 8, 8, 6, 6, 8, 8, 6, 8, 8, ... (Sloane's A094540), where the region between the 38th and 41st terms has been incompletely searched as of June 2004.
The sum of reciprocals of all the divisors of a perfect number is 2, since
n+...+c+b+a_()_(n)==2n
(22)
n/a+n/b+...==2n
(23)
1/a+1/b+...==2.
(24)
If s(n)>n, n is said to be an abundant number. If s(n)
The only even perfect number of the form x^3+1 is 28 (Makowski 1962).
Ruiz has shown that n is a perfect number iff
sum_(i==1)^(n-2)i|_n/i_|==1+sum_(i==1)^(n-1)i|_(n-1)/i_|.
// posted by Kritidas @ 2:54 AM 
