## Project Euler Problem #21

### February 9, 2010

Read the details of the problem here

Summary

Evaluate the sum of all amicable pairs under 10000.

Solution

The only tricky bit of this question was in finding a reasonably time-efficient way of determining the sum of the divisors but a little reflection on how prime sieves are built resolved that (though it can still be tweaked a little). The question requires that both numbers in the amicable pair be added together in the total but rather than tracking pairs I just ran through the whole number range and summed the lead numbers in each pair (each pair being seen twice).

```def sum_of_divisors = new int[30000]
Arrays.fill(sum_of_divisors, 1)

for (i in 2..<10000) {
def sqrt = (int)Math.sqrt(i)
for (j in 2..sqrt) {
if (i % j == 0)
sum_of_divisors[i] += j + i.intdiv(j)
}
if (sqrt * sqrt == i) sum_of_divisors[i] -= sqrt
}

for (a in 1..<10000) {
b = sum_of_divisors[a]
if ((a != b) && (sum_of_divisors[b] == a))
Spot the explicit `intdiv()` on line 8, without this runtime doubles! Note also that the `sum_of_divisors` array has to be sized appropriately to accommodate the generated values (max is 25320 for `i=9240`) to prevent the matching operation checking an non-existent cell. I did initially use a Groovy list rather than creating an array and it worked OK, and meant that I didn’t have to pre-assign an array, but performance was better if I did it this way. (The handling of this array could be better, in that the divisor sums for all values >9999 are left as 1 rather than their real values, but it suffices for this purpose.)
Runs in 1.24 seconds so well inside my 15s limit. A Java equivalent, using `int`s, runs in 17 ms (70x faster). I just don’t know what Groovy gets up to in it’s spare time – I must dig under the covers one day!