Project Euler #211 - efficiency issue

Question

I've been slowly working my way through the list of Project Euler problems, and I've come to one that I know how to solve, but it seems like I can't (given the way my solution was written).

I am using Common Lisp to do this with and my script has been running for over 24 hours (well over their one minute goal).

For the sake of conciseness, here's my solution (it's a spoiler, but only if you have one hell of a fast processor):

(defun square? (num)
  (if (integerp (sqrt num)) T))

(defun factors (num)
  (let ((l '()))
    (do ((current 1 (1+ current)))
        ((> current (/ num current)))
      (if (= 0 (mod num current))
          (if (= current (/ num current))
              (setf l (append l (list current)))
              (setf l (append l (list current (/ num current)))))))
    (sort l #'< )))

(defun o_2 (n)
  (reduce #'+ (mapcar (lambda (x) (* x x)) (factors n))))

(defun sum-divisor-squares (limit)
  (loop for i from 1 to limit when (square? (o_2 i)) summing i))

(defun euler-211 ()
 (sum-divisor-squares 64000000))

The time required to solve the problem using smaller, more friendly, test arguments seems to grow larger than exponentialy... which is a real problem.

It took:

• 0.007 seconds to solve for 100
• 0.107 seconds to solve for 1000
• 2.020 seconds to solve for 10000
• 56.61 seconds to solve for 100000
• 1835.385 seconds to solve for 1000000
• 24+ hours to solve for 64000000

I'm really trying to figure out which part(s) of the script is causing it to take so long. I've put some thought into memoizing the factors function, but I'm at a loss as to how to actually implement that.

For those that want to take a look at the problem itself, here it be.

Any ideas on how to make this thing go faster would be greatly appreciated.

**sorry if this is a spoiler to anyone, it's not meant to be.... but if you have the computing power to run this in a decent amount of time, more power to you.

Answer 1

Here's a solution, keeping in mind the spirit of [Project] Euler. [Warning: spoiler. I've tried to keep the hints slow, so that you can read only part of the answer and think on your own if you want. :)]

When you are confronted with a problem having to do with numbers, one good strategy (as you probably already know from solving 210 Project Euler problems) is to look at small examples, find a pattern, and prove it. [The last part may be optional depending on your attitude to mathematics ;-)]

In this problem, though, looking at small examples -- for n=1,2,3,4,... will probably not give you any hint. But there is another sense of "small examples" when dealing with number-theoretic problems, which you also probably know by now -- primes are the building blocks of the natural numbers, so start with the primes.

For a prime number p, its only divisors are 1 and p, so the sum of the squares of its divisors is 1+p².
For a prime power p^k, its only divisors are 1, p, p², … p^k, so the sum of the squares of its divisors is 1+p+p²+…+p^k=(p^k+1-1)/(p-1).
That was the simplest case: you've solved the problem for all numbers with only one prime factor.

So far nothing special. Now suppose you have a number n that has two prime factors, say n=pq. Then its factors are 1, p, q, and pq, so the sum of the squares of its divisors is 1+p²+q²+p²q²=(1+p²)(1+q²).
What about n=p^aq^b? What is the sum of the squares of its factors?

[............................Dangerous to read below this line...................]

It is ∑_{0≤c≤a, 0≤d≤b}(p^cq^d)² = ((p^a+1-1)/(p-1))((q^b+1-1)/(q-1)).

That should give you the hint, both on what the answer is and how to prove it: the sum of the divisors of n is simply the product of the (answer) for each of the prime powers in its factorization, so all you need to do is to factorize 64000000 (which is very easy to do even in one's head :-)) and multiply the answer for each (=both, because the only primes are 2 and 5) of its prime powers.

That solves the Project Euler problem; now the moral to take away from it.

The more general fact here is about multiplicative functions -- functions on the natural numbers such that f(mn) = f(m)f(n) whenever gcd(m,n)=1, i.e. m and n have no prime factors in common. If you have such a function, the value of the function at a particular number is completely determined by its values at prime powers (can you prove this?)

The slightly harder fact, which you can try to prove[it's not that hard], is this: if you have a multiplicative function f [here, f(n)=n²] and you define the function F as F(n) = ∑_{d divides n}f(d), (as the problem did here) then F(n) is also a multiplicative function.

[In fact something very beautiful is true, but don't look at it just yet, and you'll probably never need it. :-)]