2

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

Amir Afghani
  • 145
  • There are indeed shortcuts. One way to speed it up is to use the prime factorisation to find the divisors. (One can do much better still.) Another hint is that arrays are cool, the best data structure invented to date. But with a different algorithm, you can get faster than with arrays. – Daniel Fischer Jun 01 '14 at 16:34
  • Hi Daniel. Thank you for your comment. Can you please elaborate on the prime factorization? – Amir Afghani Jun 01 '14 at 17:59

1 Answers1

2

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.

Alex
  • 174
  • Hi Alex, thanks for your answer. Now that I have the prime factorization of a given number N, what do I do? Can I easily derive it's factors from that? – Amir Afghani Jun 02 '14 at 15:37
  • If I understood your problem correctly you'll need to find all the divisors of the given number. The approach given in my answer above gives you all the prime factors of the given number with O(pi(n)) complexity. This works fast cause it uses addition and comparison operation. Division and taking modulo is way expensive even on the modern hardware. As an illustration of that algorithm, for n=100 you should get 2 and 5 as prime factors. By using those prime factors the only thing you need to do is to infer the other non-prime divisors of 100 such as 22=4, 25=10, 5*5=25, etc. – Alex Jun 02 '14 at 18:02