views:

1133

answers:

7

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.

+1  A: 
Steve Jessop
A: 

I think you can attack this problem with something like a prime sieve. That's only my first impression though.

Haoest
Given the source, it's more likely there's some smart mathematical relation between sigma-2(n) and sigma-2 of the prime factors of n, which makes the whole thing much, much faster. Ofc you're right that calculating a prime sieve speeds up finding factors significantly.
Steve Jessop
+3  A: 
Svante
+2  A: 

I would attack this by doing the prime factorization of the number (for example: 300 = 2^2 * 3^1 * 5^2), which is relatively fast, especially if you generate this by sieve. From this, it's relatively simple to generate the factors by iterating i=0..2; j=0..1; k=0..2, and doing 2^i * 3^j * 5^k.

5 3 2
-----
0 0 0 = 1
0 0 1 = 2
0 0 2 = 4
0 1 0 = 3
0 1 1 = 6
0 1 2 = 12
1 0 0 = 5
1 0 1 = 10
1 0 2 = 20
1 1 0 = 15
1 1 1 = 30
1 1 2 = 60
2 0 0 = 25
2 0 1 = 50
2 0 2 = 100
2 1 0 = 75
2 1 1 = 150
2 1 2 = 300

This might not be fast enough

FryGuy
It's definitely fast enough, and this is a generic solution that works for many problems... this should be the accepted answer instead ;-)
ShreevatsaR
+9  A: 
ShreevatsaR
To be honest, I've not done 210, I've merely done 67. This one struck my attention, so I tried it out. But thanks for the insight on how to more effectively do this one.
Josh Sandlin
The Möbius inversion formula is very, very beautiful; unfortunately, it is also very, very difficult to intuit. It was covered in my introductory number theory class but less than half of the students were able to apply it properly even when given hints. Some days, it feels like dark magic to me, too. :)
ephemient
A: 

I've reworked the program with some notes taken from the comments here. The 'factors' function is now ever so slightly more efficient and I also had to modify the σ_(2)(n) function to accept the new output.

'factors' went from having an output like:

$ (factors 10) => (1 2 5 10)

to having one like

$ (factors 10) => ((2 5) (1 10))

Revised function looks like this:

(defun o_2 (n)
"sum of squares of divisors"
  (reduce #'+ (mapcar (lambda (x) (* x x)) (reduce #'append (factors n)))))

After the modest re-writes I did, I only saved about 7 seconds in the calculation for 100,000.

Looks like I'm going to have to get off of my ass and write a more direct approach.

Josh Sandlin
You don't have to; you can do as FryGuy said: first write a prime-factors function that does (prime-factors 64000000) => (2 2 2 2 2 2 2 2 2 2 2 2 5 5 5 5 5 5), then generate the list of factors *using* that prime-factors function. This should help you for other Project Euler problems as well.
ShreevatsaR
+1  A: 

The clever trick you are missing is that you don't need to factor the numbers at all How many numbers from 1..N are multiples of 1? N How many numbers from 1..N are multiples of 2? N/2

The trick is to sum each number's factors in a list. For 1, add 1^2 to every number in the list. For 2, add 2^2 to every other number. For 3, add 3^2 to every 3rd number.

Don't check for divisibility at all. At the end, you do have to check whether the sum is a perfect square, and that's it. In C++, this worked in 58 seconds for me.