-- The Rape of Lucrece Ver. 124 by William Shakespeare
"It is reasonable to have perfection in our eye ; that we may always advance towards it"
-- Samuel Johnson in letters to The Adventurer
Few things in life can be said to be perfect, but in mathematics there do exist numbers which are said to be perfect. A perfect number is a number who's sum of its divisors (other than its self) is equal to its self.
For exemplification, the number 6 is a perfect number. Why is 6 perfect?
- 6 is divisible by 1
- 6 is divisible by 2
- 6 is divisible by 3
The sum of 1, 2, and 3 is 6 (e.g. 1 + 2 + 3 = 6). Thus by the definition of a perfect number given above, 6 is a perfect number. In fact 6 is the first perfect number (1 is never include in the realm of special numbers).
In order to say that a number is perfect we would need to do the following.
- Find all of the divisors of the given number
- Sum up the divisors found in step 1
- Compare the sum found in step 2 to the input
Above is an example of what the flow would look like with the number 6. We would take the numbers 1 - 5 as a list of possible divisors. Filter down to 1, 2, and 3. Sum 1, 2, and 3 giving us 6. Last comparing the sum we got from the summing step to the input. Since 6 equals 6, we would return true.
Hmmm, step 1 sounds a lot like a filter and step 2 sounds like folding. I bet we can write a simple F# function that can find perfect numbers using a filter and a fold (using fsi.exe and Mono).
> let isPerfect x =
- match x with
- | x when x <= 1 -> false
- | _ -> [1 .. x-1] |> List.filter (fun n -> x % n = 0) |> List.sum = x
- ;;
val isPerfect : int -> bool
In the function above we pattern match anything less than and including 1 as false, since by definition those numbers are not perfect numbers (if we wanted we could go up to and including 5 since 6 is the first perfect number). Succeeding we just need to create a list of numbers up to the number x that we are checking for perfection. We take this list and filter out the numbers that are not divisors leaving just the divisors. Then we use the built in folding of summing with the List.sum function. Finally we compare the sum of the divisors against the input number x.
Now lets test out the function with the perfect numbers 6, 28, and 496. We'll also test with the less than perfect numbers of 5 and 99.
> isPerfect 6;;
val it : bool = true
> isPerfect 28;;
val it : bool = true
> isPerfect 496;;
val it : bool = true
> isPerfect 5;;
val it : bool = false
> isPerfect 99;;
val it : bool = false
In fact if we wanted to we could use this function with List.filter against all of the numbers from 1 to 9999!
> [1 .. 9999] |> List.filter isPerfect
- ;;
val it : int list = [6; 28; 496; 8128]
That is in fact the first 4 perfect numbers which were known to the Greeks.
Note, this code is made to be readable not to be fast a few changes should be made to make it fast.
