This is basically a personal post to Todd, but anyone is allowed to join in. Feel privileged. Or you can use this time to listen to my latest song, "Should Be Sleeping", at the bottom of this page.

I did some research on amicable numbers, and tried and succeeded to write a program that calculates an amicable number given a number. Then I tried to write it so it loops for a while, listing any amicables it finds. The problem is it's slower than death. The key, obviously, is finding the right function to calculate a sum of divisors of a number. It's brutal. This is what I have so far.

    private int sumOfDivisors(int n){
        int sum = 1;
        int max = (n/2)-1;
        for (int i = 2; i < max; i++){
                int x = (n/i);
            if (n % i == 0 && i < x){
                sum += i + x;
                max = x-1;
            }
        }
        return sum;
    }

I adjust "max" based on the last divisor, so, knowing that (for instance) 3 divides into the number 81 times, it should now only loop up to 80. Then, later on if it finds that 9 divides into it 27 times, then it will only loop up to 26. This is just knowing that basically, since we're counting up, there will be no number above 27 that divides into the number that hasn't already been accounted for. Try it out. Then, to take care of that number, I add it to the sum and just adjust the max loop amount, significantly dropping the iterations needed to get the sum of the divisors, improving overall performance by a factor of around .00000001 :) Here are some results.

(NOTE: It takes 50 seconds because I'm looping from 10,000 to 11,000, checking each number for an amicable twin. To find out if a single number has an amicable twin isn't *that* bad :p )

10744 has an amicable number of 10856
from 10000 to 11000 took 50178 milliseconds.

Then from running it without adjusting the max loop

10744 has an amicable number of 10856
from 10000 to 11000 took 50228 milliseconds.

So, that's the key. If there's a formula out there for getting the sum of the divisors, it would greatly help, but I searched for a while and couldn't find it.

The general function body looks like this

        int amicable = 0;
        int sum = sumOfDivisors(n);
        amicable = sumOfDivisors(sum);
        if (n == amicable) {
            // We have an amicable number stored in "sum" (not "amicable", since it will be the same as "n" if they are amicable)
       }

50 seconds sucks. There should be something better out there. I even tried to save the trouble of searching numbers later on in the sequence that have already been determined to have or not have an "amicable twin". Anywho. It was fun.

[Update] I just remembered that division on a computer is like painting. It doesn't like to do it at all, but is asked to do it because the person who usually has to do it doesn't feel like it either, but the person asked is pretty good at it. Anyway, I changed the function so that it's faster. It doesn't divide as much. I just ran it on my laptop (1.5 GHz, 1GB ram, Linux), and it did the loop (10,000 - 11,000) in 125 milliseconds. I'd say that's a bit improved... unless it's just Linux :)

Found amicable (28,28)
28 is also a perfect number
Found amicable (220,284)
Found amicable (284,220)
Found amicable (496,496)
496 is also a perfect number
Found amicable (1184,1210)
Found amicable (1210,1184)
Found amicable (2620,2924)
Found amicable (2924,2620)
Found amicable (5020,5564)
Found amicable (5564,5020)
Found amicable (6232,6368)
Found amicable (6368,6232)
Found amicable (8128,8128)
8128 is also a perfect number
Found amicable (10744,10856)
Found amicable (10856,10744)
Found amicable (12285,14595)
Found amicable (14595,12285)
Found amicable (17296,18416)
Found amicable (18416,17296)
time took was 3266 milliseconds

(NOTE again... Description of Perfect Numbers)

That can't be Linux. 3.2 seconds?!? That's a loop from 2 to 25,000!! The other function took 50+ seconds to go from 10,000 - 11,000. The machine at work is a 1.7 GHz (faster than this laptop) with a GB RAM running Windows XP SP2 and the same version of Java. 4 divisions cut to 2 doesn't normally shave off 50 seconds... now I'm curious.

[Update] Forget it. I forgot I was throwing in a sleep everytime it looped... idiot. Anyway, Windows is still slower on a faster machine. 171 ms for 10k - 11k, vs 125 on Linux.