WARNING- This blog contains math and mathematical concepts. Do not attempt these dangerous equations without the supervision of a trained mathematician.
Ah, I remember the good ol’ days back in high school. And contrary to what Carrie might think, I wasn’t doing homework back then on stone tablets and using an abacus for a calculator. But this was back when the school’s computer lab got its first Macintosh computer (surrounded by a small fleet of Apple IIe and Apple IIgs computers). My fellow computer geeks and I thought we were so clever bypassing the school’s program filtering utility exploiting a bug in Printshop. This was long before there were flash drives, so we were carrying our computer programs around on floppy discs which were measured in KILO-bytes. And this was way before anyone in my town knew what an Internet or a smart phone was. If we wanted to network, we used actual phone lines to call other computers directly. To some, these were the Dark Ages indeed. To others, it was a simpler time, the stuff of nostalgic excitement.
I remember a time in class when one of the math teachers challenged me and another programmer to some extra credit. In those days, they didn’t really have a dedicated teacher for computer science. Computer class was usually either taught by a math teacher or someone in the business department. At any rate, that teacher wanted to see who could write a program that would list out the most “perfect numbers” over a given period of time.
Let me start by explaining what a perfect number is. A perfect number is a number that is the sum of its proper positive divisors (or its aliquot sum). This sounds confusing, I realize. So let’s break it down even further and define what a divisor is. A divisor is a number that divides evenly into a number. The divisors of the Number 6 for example are 1, 2, 3, and 6 because those numbers divide evenly into the number 6. The Number 4 is not a divisor of 6, because it divides into 6 once with a remainder. Now let’s look at proper positive divisors (or aliquot). The proper positive divisors of the Number 6 are 1, 2, 3 because you don’t include the number itself. So the sum of the proper positive divisors for the Number 6 is 1 + 2 + 3 or 6. Since 6 matches the original number; that means 6 is a perfect number.
Now that I have you thoroughly confused, let’s move on. Our task was to find the next numbers that could be considered “perfect”. Not only that, but the “extra credit” would only go to the person that could produce the most numbers over a given amount of time. The teacher then threw us a curve, because he wanted us to experience what it would be like in real life, where we would need to compete against other highly skilled programmers. So he put himself into the challenge as well. Unfortunately, I was at a disadvantage now, because the teacher was programming on the new Macintosh computer, and I was working with my old Commodore 64 at home. The teacher thought he would win the challenge of course because his computer ran 8 times faster than mine and 4 times faster than the other guy’s computer. Oh, by way of comparison, the old Commodore computers ran at 1 mhz, which is about 2000 times slower than the computer I’m writing this blog on and that’s not factoring in what’s called a bit rate (which I might need to explain in a later blog).
So what am I trying to say with this flashback? Basically, it comes down to limited resources can sometimes sparks innovative thinking. You see, if I were to write a computer program using the same technique as my teacher or the other programmer, there would be no way of beating them without sabotaging their computers somehow. They simply would outperform my poor little machine at home. They had the better resources that I did. So instead, I had to come up with innovative solutions and tricks to make my code better and faster than theirs.
Let’s look at how the teacher tackled the problem. His program selected a number, divided that number by 1, 2, 3, 4 … etc, until he found all the numbers that would divide evenly into it. He would then add those numbers together (minus the last divisor) and see if he got the original number back. For example, his program would take the Number 14 and see if 1 would divide into it evenly. It does (it always does), so the program would save that number. He would then check to see if 2 would divide into it evenly. It does, so the program would save that number. He would check to see if 3 would divide into 14 evenly. It doesn’t, so he would go to the next number. He will eventually check 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, and finally 14. The program would eventually record that 1, 2, 7, and 14 worked. It would then say that 1 + 2 + 7 = 10 which is not 14, so 14 is not a perfect number. The program would then go on to the Number 15 and repeat the process again. You can see where eventually, as the numbers would get larger and larger, his program would start to take longer and longer to check each number.
My solution took less time to find a result, because I saw that when you divided something evenly into a number, the answer of that division problem could in turn be divided evenly into the number. Basically, I found what I called divisor pairs. I also figured that I didn’t need to test the Number 1, because that number always works. So in my program, when looking at the Number 14, I only started with the number 2 and found 2 and 7 where divisors. This also meant that I only need to check up to the number 6, because after 7, the numbers would already be paired up with some other number (its divisor pair). So for this example, I would find that 3-6 are not divisors and would say that 1 (which is always a divisor) + 2 + 7 = 10 (and not 14) and therefore not perfect. Instead of looking at fourteen numbers separately, I only needed to check five to come to the same result.
That was a lot of math and programming logic, so let’s look at another example. The next perfect number happens to be 28. In my teacher’s program, he would have checked numbers 1 through 28 to find divisors (or aliquots). My program only needed to look at numbers 2-7. Because I could say that 2 pairs with 14 and that 4 pairs with 7. I could stop at 7, because it is already paired with 4. Any number after 7 would have to have been paired with something I already found. Innovative huh?
The lesson I want all you to get from this blog is simple. Sometimes, limiting what you have to work with may force you to become innovative and creative. It’s easy to just say, “I don’t have the tools to do my job” and give up. But try playing around with the tools you do have. Force yourself to discover what you are really capable of doing. As for the extra credit challenge, I did win the challenge. My program ran for 1 night and found 4 perfect numbers (6, 28, 496, and 8128). The other programmer gave up because he couldn’t get his program to factor the divisors correctly. And my teacher, who had far better resources than I, ran for 5-8 days and only came up with 3 numbers.
image link http://en.wikipedia.org/wiki/Aliquot_sum#Definition
