title: Project Euler #211 - efficiency issue
body: <p>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).</p>
  
  <p>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).</p>
  
  <p>For the sake of conciseness, here's my solution (it's a spoiler, but only if you have one hell of a fast processor):</p>
  
  <pre><code>(defun square? (num)
    (if (integerp (sqrt num)) T))
  
  (defun factors (num)
    (let ((l '()))
      (do ((current 1 (1+ current)))
          ((&gt; 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 #'&lt; )))
  
  (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))
  </code></pre>
  
  <p>The time required to solve the problem using smaller, more friendly, test arguments seems to grow larger than exponentialy... which is a real problem.</p>
  
  <p>It took:</p>
  
  <ul>
  <li>0.007 seconds to solve for 100</li>
  <li>0.107 seconds to solve for 1000</li>
  <li>2.020 seconds to solve for 10000</li>
  <li>56.61 seconds to solve for 100000</li>
  <li>1835.385 seconds to solve for 1000000</li>
  <li>24+ hours to solve for 64000000</li>
  </ul>
  
  <p>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.</p>
  
  <p>For those that want to take a look at the problem itself, <a href="http://projecteuler.net/index.php?section=problems&amp;id=211" rel="nofollow noreferrer">here it be</a>.</p>
  
  <p>Any ideas on how to make this thing go faster would be greatly appreciated.</p>
  
  <p>**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.</p>