I’ll return to my Dawkins series later in the week. But after all our exertions recently trying to resolve the mysteries of the universe, I find myself in the mood for a straight math post. So, inspired by some comments from this post, let’s talk about perfect numbers.
A number is said to be perfect if it is equal to the sum of its proper, positive divisors. By “proper” divisor we mean a divisor not equal to the number itself. For example, the proper divisors of 20 are 1, 2, 4, 5 and 10. But since
we see that 20 is not perfect.
On the other hand, the proper divisors of 28 are 1, 2, 4, 7 and 14, and we have that
So 28 is a perfect number.
From now on I will only refer to the divisors of a number, as opposed to the proper, positive divisors.
The smallest perfect number is 6. The divisors of 6 are 1, 2, 3 and we have that 1+2+3=6. The next perfect number after 28 is 496, and the next one after that is 8128.
There are currently 44 known perfect numbers, the largest having more than nineteen million digits. If you were taking a stroll among the integers, it would be a remarkable thing if you came across even one perfect number. That notwithstanding, it is an open question how many perfect numbers there are. I’m betting there are infinitely many, but I wouldn’t want to have to prove it.
If you look at the four examples I gave, you might notice something interesting:
6=2 x 3
28=4 x 7
496=16 x 31
8128=64 x 127
Why is this interesting? Well, look at the first numbers in the products on the right. We have 2, 4, 16 and 64. These are all powers of 2.
Now look at the second numbers. We have 3, 7, 31 and 127. These are all prime numbers. And if we add one to each of these numbers, we get 4, 8, 32 and 128. These are all powers of two. This is not a coincidence.
It turns out that if n is a positive integer such that 2n-1 is prime, then the number
2(n-1)(2n-1) is perfect. Let us try to prove this.
Let x=2(n-1) (2n-1).
First, notice that 2(n-1) is a power of two. As such, all of its divisors are powers of two. In particular, with the exception of the number 1, they are all even. But 2n-1 is an odd prime number. So all of its divisors are odd. It follows that 2(n-1) and 2n-1 are relatively prime,
which means simply that the only number that divides both is 1.
Consequently, every divisor of x has the form ab, where a divides 2(n-1) and b divides 2n-1.
Next, notice that the only divisors of 2n-1 are 1 and the number itself. The sum of these two numbers is
Now consider the divisors of 2(n-1). They all have the form 2j where j is a positive integer less than n-1. It can be shown that the sum of all such divisors is 2(n-1)-1. This is
straightforward to prove if you are familiar with the formula for the sum of a geometric series. If you are not familiar with that formula, then simply consider the following examples:
- The divisors of 4 are 1 and 2, and 1+2=3 which is one less than 4.
- The divisors of 8 are 1, 2 and 4, and 1+2+4=7 which is one less than 8.
- The divisors of 16 are 1, 2, 4 and 8, and 1+2+4+8=15 which is one less than 16.
- The divisors of 32 are 1, 2, 4, 8 and 16, and 1+2+4+8+16=31, which is one less than 32.
This pattern always holds. However, the number 1 was already counted as a divisor of 2n-1.
Since we do not want to count it twice, we find that the sum of all of these divisors is
Finally, we must consider the divisors of the form ab. The only such divisors we have not yet considered have the form 2j(2n-1), where j is a positive integer less than n-1. The sum of all
such numbers is
2(2n-1)+4(2n-1)+ . . . + 2(n-2)(2 n-1)=
(2n-1)(2+4+. . .+2(n-2))=(2n-1)(2(n-1)-2).
If you do the algebra, you obtain
Now we can show that x is perfect. The sum of the divisors of x is:
Notice that the terms with 2(n-1) cancel out, as do the 2 and the -2. Thus, we can simplify
since the difference between consecutive powers of two is always the smaller of the two powers. (For example, 32-16=16 and 64-32=32.)
Finally, if we do a little factoring we obtain
as was to be shown.
Well, that got a bit complicated. So why don’t we illustrate the main idea of the proof by considering the perfect number 496.
We know that 496=16 x 31.
The only divisors of thirty-one are 1 and 31, and their sum is 32.
The only divisors of sixteen are 1, 2, 4, 8 and 16. But since we have already counted 1 we drop that from the list. Then we find that 2+4+8+16=30.
Finally we consider the divisors obtained by multiplying a divisor of 16 by 31. The only such divisors we have not considered are 2 x 31=62, 4 x 31=124 and 8 x 31=248, and 62+124+248=434.
Putting everything together gives
So we have shown that every number of that form is perfect. It turns out that, actually, every even perfect number has that form, but this is harder to prove.
From this it follows that we can find even perfect numbers simply by finding prime numbers that are one less than a power of two. Such primes are called Mersenne primes, after a seventeenth century French monk and amateur mathematician. The search for perfect numbers is really the search for Mersenne primes.
By now you must be wondering whether there are any odd perfect numbers. No such numbers are known, and a number of results have been proven showing that an odd perfect number would have to have some strange properties indeed. But the fact remains that there is no proof showing that odd perfect numbers are impossible.
Sometimes number theorists talk about abundant numbers, which are numbers that are smaller than the sum of their divisors. As shown at the start of this post, 20 is an abundant number. LIkewise there are deficient numbers, which are larger than the sum of their divisors. Every prime number is deficient, since their only proper divisor is 1. But my favorite notion along these lines is that of an amicable pair of numbers. For example, consider the numbers 220 and 284.
- The proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110.
- The proper divisors of 284 are 1, 2, 4, 71and 142.
- We have 1+2+4+5+10+11+20+22+44+55+110=284
- We also have 1+2+4+71+142=220
And if that doesn’t bring a smile to your face, I don’t know what will. See you tomorrow!