PDA

View Full Version : Programming Puzzle 16 - Perfect Numbers ?


ABC123

Tom Cone Jr
07-10-2011, 12:27 AM
This is a bit harder.

Don't work on this while your manager is around.

A positive integer is called a "perfect number" if it is equal to the sum of all of its positive divisors, excluding itself. For example, 6 is the first perfect number because 6 = 3 + 2 + 1. The next is 28 = 14 + 7 + 4 + 2 + 1. There are four perfect numbers less than 10000.

Instructions:

a) Write an xbasic program to find all four of the perfect numbers.

b) Display your answer in a message box on screen. Show the divisors
for each perfect number, so we can easily check your sums.

c) Post your solution by attaching the "exported" script to your reply here.

d) Have fun.

StephenP
07-10-2011, 11:33 AM
Professor Cone,

Here is my homework. Not quite as difficult as you suggested. I tried to comment heavily to show my thought process (a scary venture at the best of times). I hope you like my solution. By the way, I had a lot of fun with it, and tried searching up to 100,000, but there are still only four perfect sums. But that took six minutes, as opposed to the 8.5 seconds for up to 10,000. Does that mean 1,000,000 would take 4-5 hours?

Thanks for doing these. I've been trying to think up one myself.

Keith Hubert
07-10-2011, 01:46 PM
Nice bit of code Stephen, my machine must be getting very old, it took 10.688 seconds.

Tom Cone Jr
07-10-2011, 03:47 PM
Stephen,

very nice!

In developing my own solution I struggled with:

a) figuring out an efficient way to determine the integer divisors of the candidate numbers. I used the MOD() function which I think may be a tiny bit more efficient than your "i/j = int(i/j)" test. Each time through the loop your approach must do two divisions and then the int() function is called. Haven't profiled the code yet, so can't say for sure.

b) my code runs through a far greater number of loops. ( n / 2 )
because I didn't have the wisdom to use the integer root to set the upper limit of the loop counter, nor would I have realized that each divisor has a complementary value that's also a divisor. Your approach is very clever.

c) even better, I struggled with storing my divisors in an array, and then processing the array to get the sum. Very messy. Your use of the eval() function running against the divisors arranged in a simple arithmetic string expression is ingenious!

Prof. Pickypicky is ready to move you to the head of the class!

jeb richardson
08-15-2011, 12:40 PM
Prof. Pickypicky,
My script contains two loops each going to 10000. I do believe my answer is correct, however it takes a while to generate the answers. Check it out when you have the time.


29072