Find the sum of all n, 0 < n < 64,000,000 such that σ2(n) is a perfect square.

Question

I have been working on Project Euler problem 211 for quite some time, and I am stuck. I'm not looking for an answer, I'm simply looking for some guidance. I've written and tested the following code, which literally has run for days on my machine without completing.

System.out.println(IntStream.range(1, LIMIT).filter(input -> isPerfectSquare(phi(input))).sum());

static long phi(final int n) {
    return streamedDivisors(n).map(x -> x * x).sum();
}

static LongStream streamedDivisors(final int n) {
    return LongStream.range(1, n + 1).parallel().filter(input -> input == 1 || n % input == 0);
}

static boolean isPerfectSquare(final long n)
{
    if (n < 0)
        return false;

    long tst = (long)(Math.sqrt(n) + 0.5);
    return tst*tst == n;
}

and I've concluded there must be a shortcut that I'm not seeing. Can someone point me in the right direction?

What I'm trying to pick up is the reasoning behind whatever shortcut one could take for not calculating the divisors for each of the 64 million numbers, which computationally is the most expensive part of this exercise (and what I assume is the key!)

Answer 1

The most expensive part in your algorithm is a factorization of the given number. If you want maximum speed and you have enough memory, you can maintain an array of prime-residue pairs which may help you to quickly find prime factors in [1..n] sequence.

Example:

n=2, array=[(2 0)], 2 is a prime, 0=n mod 2
n=3, array=[(3 0) (2 1)]
n=4, array=[(3 1) (2 0)]
n=5, array=[(5 0) (3 2) (2 1)], 0=5 mod 5, 2 = 5 mod 3, 1 = 5 mod 2 
n=6, array=[(5 1) (3 0) (2 0)]

etc.

The algorithm for building that array is simple: you need just to increment residues by 1 and if the result equals to the corresponding prime, you need to make that residue zero. Also, if after this operation there is no residue equal to 0 you need to add another pair (n 0) to that array and n would be the next prime.

Prime divisors for a given n number are those primes, which residues would be 0. Maintaining that array in for-loop will eliminate the most expensive operation in your algorithm - prime factorization of a given number with much less expensive straightforward addition and comparison operations.

P.S.: Given that prime and residue are 32-bit numbers, max size for that array for max(n)=64000000 is 3785086 of prime-residue pairs or 15140344 bytes or <15Mb which is not that much.

P.P.S.: In that problem you'll need to find all the divisors of a given number but it is much less complicated task as long as you have all the prime factors.