Starting Over

When in doubt, use brute force.

—Ken Thompson

We can attack this in the most straightforward manner possible to define

(defun euler-1-brute-force (n)
  (loop for i from 1 to (1- n)
	when (or (zerop (mod i 3))
		 (zerop (mod i 5)))
	  summing i))

Now we can answer the original question

CL-USER> (euler-1-brute-force 1000)
233168

with reasonable speed. For a one-off problem of the stated size, the linear performance is no problem at all. But what about for values larger than 1000? As $n$ increases, the time to compute the answer increases proportionally, until, at an $n$ of 1 billion, the time is approximately 7 seconds on the machine in front of me. Can we do better?

For the example given, we have two sets of numbers to consider, the multiples of 3 (i.e., 3, 6, and 9) and the sole multiple of 5. Considering only the multiples of 3, we have

The upper bound of the summation is the number of multiples of 3 below 10, which we can find as

$$\lfloor \frac{10-1}{3}\rfloor$$

Generalizing, we can write

(defun num-multiples-below (k n)
  (floor (/ (1- n) k)))

The summation itself can be found using

$$\sum _{i=1}^n=\frac{n(n+1)}{2}$$

or, in Lisp,

(defun sum-to (n)
  (/ (* n (1+ n)) 2))

Now, to find the sum of the multiples of any $k$ below $n$ , we can write

(defun sum-multiples-below (k n)
  (* k (sum-to (num-multiples-below k n))))

For the example

CL-USER> (+ (sum-multiples-below 3 10)
	    (sum-multiples-below 5 10))
23

will suffice. However, for going up to 1000, we have to avoid double counting the multiples of 15 (i.e., of both 3 and 5):

CL-USER> (- (+ (sum-multiples-below 3 1000)
	       (sum-multiples-below 5 1000))
	    (sum-multiples-below 15 1000))
233168

That leads us to our faster, final form:

(defun euler-1-better (n)
  (- (+ (sum-multiples-below 3 n)
	(sum-multiples-below 5 n))
     (sum-multiples-below 15 n)))

But how much faster is this creatively named version?

CL-USER> (time (euler-1-brute-force 1000000000))
Evaluation took:
  6.975 seconds of real time
  6.975762 seconds of total run time (6.967762 user, 0.008000 system)
  100.01% CPU
  26,508,368,282 processor cycles
  0 bytes consed

233333333166666668
CL-USER> (time (euler-1-better 1000000000))
Evaluation took:
  0.000 seconds of real time
  0.000004 seconds of total run time (0.000004 user, 0.000000 system)
  100.00% CPU
  12,806 processor cycles
  0 bytes consed

233333333166666668

Going off the total run time (the one we humans care about most), the brute force method takes 1.7 million times as long as the improved approach when $n$ hits 1 billion. For 10 billion, the brute force method will take well over an hour; the fast method will still take a fraction of a second.