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

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.

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: