Project Euler Problem #23

February 9, 2010

Read the details of the problem here

Summary

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Solution

FAIL. Sad to say but this one defeated me – I just couldn’t get it to break the 15 second limit when using Groovy. My initial implementation used various Groovy features like adding isAbundant() and sumOfProperDivisors() methods to the Integer class and accumulating abundant numbers in lists, etc. but the runtime was 55 seconds. Gradually removing these syntactical niceties and using more inline code got me back to 21.2 seconds. I could have opted again for a multi-threaded approach similar to that which I took for Solution #14 and that would have probably got me down to below 15 seconds but I took the easy way out and ported it over to Java.

import java.util.Arrays;

final int LO_VAL = 12;
final int HI_VAL = 28123+1;

boolean[] isAbundant = new boolean[HI_VAL-LO_VAL+1];
Arrays.fill(isAbundant, false);

for (int i = LO_VAL; i <= HI_VAL-LO_VAL; i++) {
    int sum = 1;
    int sqrt = (int)Math.sqrt(i);
    for (int d = 2; d <= sqrt; d++) {
        if (i % d == 0) sum += d + i / d;
    }
    if (sqrt * sqrt == i) sum -= sqrt;
    isAbundant[i] = (sum > i);
}

boolean[] nums = new boolean[HI_VAL];
Arrays.fill(nums, false);

for (int i = LO_VAL; i < isAbundant.length; i++) {
    if (isAbundant[i]) {
        for (int j = i; j  < isAbundant.length; j++) {
            if (isAbundant[j]) {
                int sum = i + j;
                if (sum >= HI_VAL) break;
                nums[sum] = true;
            }
        }
    }
}

int answer = 0;

for (int i = 0; i < HI_VAL; i++) {
    if (!nums[i]) answer += i;
}

This code runs in 0.80 seconds. As you’d expect, the vast majority of the time is being spent in the nested loop running through the sums of abundant numbers.

Conclusion

Groovy just isn’t as performant as Java for this sort of work!

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: