## 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 } def answer = 0 for (a in 1..<10000) { b = sum_of_divisors[a] if ((a != b) && (sum_of_divisors[b] == a)) answer += 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!

**Conclusion**

Straightforward maths processing, Groovy neither helped nor hindered, though I could have used Groovy lists but I don’t think the code would have been any clearer.