Read the entire assignment before you start.
A proper divisor of a positive integer n is a number k where 0 < k < n and k is a divisor of n. For example, 2 is a proper divisor of 6, but 6 is not a proper divisor of 6. A perfect number is a positive integer that is equal to the sum of its proper divisors. For example, 6 is a perfect number because the proper divisors of 6 are 1, 2 and 3, and 6 = 1 + 2 + 3.
Write a program that finds and writes the first four perfect numbers. It should not just show the numbers, but should say what they are. For example, it might start by writing
The first four perfect numbers are:
Write definitions of the following functions. Write a clear, precise and concise contract for each one, and at least two examples for each.
isDivisor(k, n) should yield true if k is a divisor of n, and false if not.
sumDivisorsRange(n, a, b) should yields the sum of all numbers k where k is a divisor of n and a <= k <= b. For example, sumDivisorsRange(8, 2, 7) = 2 + 4 = 6 since 2 and 4 are the only divisors of 8 in the range from 2 to 7 (including 2 and 7).
Use isDivisor in this function to tell if one number is a divisor of another.
Use recursion for this. Think about how doing sumDivisorsRange(n, a, b) has a smaller problem of the same kind inside it. Do not forget about a base case, where the function does not use recursion. What is sumDivisors(8, 5, 4)?
sumDivisors(n) should yield the sum of the proper divisors of n. For example, sumDivisors(8) = 1 + 2 + 4 = 7. Use sumDivisorsRange to do this.
isPerfect(n) should yield true if n is a perfect number, false if not. You have the sumDivisors function. Read the definition again of a perfect number. Make your function definition transparently correct, assuming that other functions are correct.
Now write an execute block that uses a loop. It should keep track of two things that change as the loop runs.
It needs to keep track of the number that it will check next. Just check the numbers 2, 3, 4, ... to see whether each one is perfect.
It also needs to keep track of how many perfect numbers it has shown. The loop stops after it has shown four perfect numbers. How should this variable be initialized? (How many perfect numbers has the program shown when it is just getting started?) When do you update this number?
To diagnose what is wrong with a patient, a doctor might run some tests. Similarly, automobile repairers run diagnostics on cars. In fact, modern cars have diagnostics built in. For the same reason, programs often have diagnostics built in. A well written program is designed for testing, right from the outset, with the assumption that things will go wrong.
Before you try to run this program, add a diagnostic part. Near the top of the program, add line
Define debugging = true.In the loop of your Execute block, add a part that shows the value of n, surrounded by brackets, whenever n is divisible by 100, but only if debugging is true. Here is a statement that does that, assuming that the number is called n.
If debugging and isDivisor(100, n) then
Display "[".
Display n.
Displayln "]".
%If
Run the program with this in place. You get extra information.
After the program works, and you want
to get rid of the extra information, do not remove the part that shows
that information. You might want it again later. Just change the definition
of debugging to false. The extra information will not be shown.
(When the auto repair person fixes your car, he or she does not remove
the diagnostic support from the car!)
This material is beyond the scope of this class, and you will not be tested on it. But it introduces you to some of the ideas that are employed when people think very carefully about what computers can do and what they cannot do.
You will find that your program runs for a long time. Can you tell if it will ever stop? Are there four perfect numbers? An interesting question is whether you can examine a program carefully and tell whether it will ever stop. Or, better yet, since you prefer to let computers do work like that for you, can you design a computer that examines a program and tells you whether that program will ever stop?
Researchers in the theory of computation managed to prove that you can never create a computer program that reads another computer program and tells you whether that other program will ever stop. It is not just a difficult problem, but an impossible one. See notes on the termination problem for how the argument goes. So you are stuck with seat-of-the-pants thought about that kind of thing. You might run the program for a while and make a good guess whether it will ever stop. Often, your guesses are right. Sometimes, they will be wrong.