SEAV Softwares: Factors and Perfect Numbers

*Case Study Problem A1*
Factors and Perfect Numbers
Number Theory / Novice to intermediate level

Make a program that inputs a number and prints out all of its integral factors. Use the facts that the factors divide into the number evenly and there cannot be an integral factor that is more than half of the number except the number itself. The factors do not have to be sorted when printed.

For instance, when the user enters 12, the program should display the factors 1, 2, 3, 4, 6, and 12. When the user enters 100, the program should output the numbers 1, 2, 4, 5, 10, 20, 25, 50, and 100.

Using the first program, make another program that tests whether a number is perfect or not. A number is perfect if the sum of its factors, excluding itself, adds up to the same number. For example, the smallest perfect numbers is 6; its factors, 1, 2, and 3 (not including 6 itself) add up to 6. Another perfect number is 28: 1 + 2 + 4 + 7 + 14 = 28.

The Solution

Review of factors. If you have taken up grade school math, you'll know what are factors or divisors of a number. With number, I mean the natural numbers (positive integers). Throughout the rest of the text, we'll be using the word "number" to refer to positive integers. Factors are numbers that divide into the given number evenly. For example, the number 12 has six factors, namely, 1, 2, 3, 4, 6, and 12. A number is a factor in itself and 1 is a factor of every number.

We can classify numbers into two groups (actually three, more on this later) based on the number of their factors: the prime numbers and the composite numbers. Prime numbers are numbers having only two factors, 1 and itself, while composite numbers have more than two factors. The first five prime numbers are 2, 3, 5, 7, and 11. Two is the only even prime. The number one is neither prime nor composite since it has only one factor (1 constitutes the third group, if it can be called a group).

A simple and straightforward solution. Going back to the problem, we can find the factors of a number by simply going through all the numbers from 1 to the given number and testing if the numbers are factors of the given number. Here's the pseudocode for this solution:

Input: Number
For X = 1 to Number
If Number is divisible by X then print X
Next

Checking number divisibility. Now, how does one know if a number is divisible by another? Remember the process you used to do during Math class? You divide the number by the other and see if there's anything left over (i.e., there are fractional parts). I once used the following code to determine divisibility:

IF Num% / Factor% = INT(Num% / Factor%) THEN Divisible = True END IF

The code above is very simple. We check if the number when divided by another has any fractional parts. But to make things more clear, we could use integer division, Num% \ Factor%, for efficiency instead of invoking the INT function, but it would be more efficient to use the MOD or modulus operator. The modulus operator takes two operands, divides the first operand by the second and returns the remainder. Thus, a number is divisible by the other if the remainder returned is zero:

IF Number% MOD Factor% = 0 THEN Divisible = True END IF

It's as simple as that.

First draft. Now we can write the actual code to our program. We won't put any error checking in the input statement (positive integers would be the only values accepted—you can do this easily).

Listing A1.1

CLS INPUT "Enter a positive integer: ", Number% PRINT "The factors of"; Number%; "are:" FOR I% = 1 to Number% IF Number% MOD I% = 0 THEN PRINT I% NEXT

The factors do not have to be sorted in increasing values, but in this program, we made it so. Alternatively, we can store the factors into an array and do all sorts of things on them. We can count them, tabulate them, add them and so on.

Making it more efficient. Our program, being straightforward, would naturally be inefficient. Observe that we are testing numbers greater than half the given number when it is already stated in the problem that there are no factors in that area. So we can reduce the loop to test values up to half the given number.

If you're insightful, you'll notice that if we find a factor, we already have found another factor! That's the quotient of the given number divided by the first factor (i.e., if B is a factor of A, then A/B is also a factor of A). Using this piece of information, we can further reduce the loop values down to the square root of the given number since that is where the factor-pairs converge. For example, let's take 120:

120 =	1	x 120
120 =	2	x 60
120 =	3	x 40
120 =	4	x 30
120 =	5	x 24
120 =	6	x 20
120 =	8	x 15
120 =	10	x 12
120 =	10.954	x 10.954

As you can see, we are already having ideas on making the program more efficient by removing unnecessary computation.

Our somewhat final program is can be found in Listing A1.2. Notice that we check if the factor is the square root of the given number so that we won't display it twice.

Listing A1.2

DEFINT A-Z CLS DO INPUT "Enter a positive integer: ", Number LOOP UNTIL Number > 0 Root! = SQR(Number) PRINT "The factors of"; Number; "are:" FOR I = 1 to Root! ' If the number is a factor IF Number MOD I = 0 THEN ' Print factor and it's "complement" PRINT I IF I <> Root! THEN PRINT Number \ I END IF NEXT

Perfect numbers. A number is perfect if the sum of its proper divisors (factors not including the number) is the number itself. The ancient Greeks only knew the first four such numbers: 6, 28, 496, and 8128. The number 1 is not perfect since it has no proper divisors. Now, there are at least thirty numbers discovered, the thirtieth having 130,100 digits. All of them are even and nobody has proven if there is an odd perfect number.

Using the program we made for the first subproblem, we change it so that it becomes a perfect number tester. Instead of displaying the factors of the given number, we add them using an accumulator variable. Then we test if the sum is equal to the original number. Remember that the sum does not include the number itself.

Listing A1.3

DEFINT A-Z CLS DO INPUT "Enter a positive integer: ", Number LOOP UNTIL Number > 0 Root! = SQR(Number) PRINT "The factors of"; Number; "are:" FOR I = 1 to Root! ' If the number is a factor IF Number MOD I = 0 THEN ' Add factor and it's "complement" Sum = Sum + I IF I <> Root! AND I <> 1 THEN Sum = Sum + Number \ I END IF END IF NEXT ' Print verdict IF Sum = Number AND Number <> 1 THEN PRINT Number; "is perfect" ELSE PRINT Number; "is not perfect" END IF

Near the end of the program, we test if the number entered is 1 or else, the program will say that it is perfect, when it is not.

Challenge: Modify this program so that it will find the fifth perfect number. A clue: it's greater than 33.55 million. Also, you need to use long integers.

Beyond the Problems

More about perfect numbers. Perfect numbers have aroused a lot of interest from mathematicians. They have discovered and proven all sorts of things about them. For instance, Euclid discovered that the first four perfect numbers are generated by the formula 2^n - 1(2ⁿ - 1):

For n = 2, 2¹(2² - 1) = 6
For n = 3, 2²(2³ - 1) = 28
For n = 5, 2⁴(2⁵ - 1) = 496
For n = 7, 2⁶(2⁷ - 1) = 8128

Noticing that 2ⁿ - 1 is prime in all computations, Euclid proved that the formula 2^n - 1(2ⁿ - 1) gives a perfect even number whenever 2ⁿ - 1 is prime.

The ancient mathematicians made many assumptions about perfect numbers based on the four numbers they knew. Most of the assumptions were wrong. One of these assumptions was that since n is also prime for the four computations and the first four primes to boot, they thought that the fifth perfect number would be obtained when n = 11, the fifth prime. It didn't. For when n = 11, 2ⁿ - 1 is not a prime and it should be for the formula to produce a perfect number. It's true that n should be a prime but it does not mean that 2ⁿ - 1 is automatically a prime. Nowadays, prime numbers generated by the formula 2ⁿ - 1 are known as Mersenne numbers, after the seventeenth-century monk, Marin Mersenne, who studied number theory and perfect numbers.

Here are two other wrong assumptions the ancients had:

1.	The fifth perfect number would have five digits since the first four had 1, 2, 3, and 4 digits respectively.
2.	The perfect numbers would always end in 6 or 8 and that they would alternate repeatedly.

The fifth perfect number has 8 digits, thus debunking the first assumption. For the second assumption, the fifth perfect number indeed ends with a 6. However, the sixth also ends in a 6. It's hasn't been proven that all perfect even numbers always end in a 6 or 8, but so far, the first thirty do. Also, the perfect numbers that end in 8, really ends in 28.

Two millennia after Euclid, Leonard Euler proved that the formula 2^n - 1(2ⁿ - 1) will yield all the even perfect numbers. Now, the question number theorists are trying to solve is whether there exists odd perfect numbers! (As if perfect numbers aren't odd already.)

Friendly or amicable numbers. Mathematicians, as they always do, have extended the concept of perfect numbers to such things called friendly or amicable numbers. These are number pairs that have the special property that when one adds the proper divisors of one of the numbers, one will get the other number and vice versa. The first such pair is 220 and 284. When you add the proper divisors of 220: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110, you'll get 284. The same goes for the proper divisors of 284: 1 + 2 + 4 + 71 + 142 = 220. Perfect numbers are their own friends (they're so perfect that they don't need friends!).

The Pythagoreans knew about the friendly pair 220 and 284, but nobody has discovered a second pair until the year 1636 when Pierre de Fermat found the numbers 17,296 and 18,416. It was however in the year 1866 that the second smallest pair, 1,184 and 1,210, was discovered by a sixteen-year-old boy! Today, mathematicians have discovered at least sixty pairs of friendly numbers.