Project Euler Problem #179

April 10, 2010

Read the details of the problem here

Summary

Consecutive positive divisors.

Solution

I went straight to Java for this problem. I felt that a sieve approach to count the divisors would be better than trying to actually calculate the divisors themselves for such a large range of numbers. Given past performance of Groovy when carrying out such activity I thought it would be a non-starter to use it and I couldn’t see a better algorithm.

Coding was straightforward. I used a simple optimisation to allow the outer-loop to only run to the square-root of LIMIT but nothing extraordinary.

final int LIMIT = 10000000;
int[] sieve = new int[LIMIT+1];
Arrays.fill(sieve, 2);  // don't worry about elements 0 & 1

for (int i = 2; i <= (int)Math.sqrt(LIMIT); i++) {

    int j = i * i;
    sieve[j]--;

    while (j <= LIMIT) {
        sieve[j] += 2;
        j += i;
    }
}

int answer = 0;

for (int i = 2; i < LIMIT; i++) {
    if (sieve[i] == sieve[i+1]) answer++;
}

This runs in 2.16 seconds.

Conclusion

Groovy? A simple ported implementation that doesn’t use any special features runs in 15.3 seconds. So not far out, but not quite there!

Note: After solving this and gaining access to the forum, it seems that there is a technique that solves this in an amazing 312 ms using Java, but porting this to Groovy actually takes longer, at 24.1 seconds, than the simple optimisation. I’ll do some more research into why this is because it seems like a strange pathological behaviour, maybe to do with memory management or array access patterns.

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: