Project Euler Problem #179

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.