Project Euler Problem #21

February 9, 2010

Read the details of the problem here


Evaluate the sum of all amicable pairs under 10000.


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 ints, 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!


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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: