## April 12, 2008

Project Euler is a website that contains a series of challenging mathematical and computer science problems. The problems are a great way to strengthen your mind and learn how to program. Plus, they’re fun! Though I would like to solve all the problems, I plan on working on them in my spare time.

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

The most practical solution is the simple brute force method.

In Common Lisp:

`(defun problem-1 ()(loop for i from 3 to 999 when (or (zerop (mod i 3))                                             (zerop (mod i 5)))   sum i))`

In Python:

`def problem1():    sum = 0    for i in range(3, 1000):        if i%3 == 0 or i%5 == 0:            sum += i    return sum`

But is there a more efficient way? Of course! Let’s look at the sum of multiples of 3 that are less than 1000:

3+6+9+12…+999 = 3*(1+2+3+4+…333)

If we realize that 1+2+3+…x = (x*(x+1))/2, the above equation can be written as

3*((999/3)*((999/3)+1))/2

Now we can make the above equation into a function fn(n), and the answer will be fn(3) + fn(5) – fn(15). We need to subtract multiples of 15 because the lowest common denominator of 3 and 5 is 15. No looping is required, so this solution is more efficient.

In Common Lisp:

` (defun sum-div-by (num)  (let* ((max 999) (x (floor (/ max num))))    (/ (* num (* x (+ x 1)))        2)))(defun problem-1v2 ()  (- (+ (sum-div-by 3) (sum-div-by 5)) (sum-div-by 15)))`

In Python:
`def sumDivBy(num):    top = 999    x = top / num    return num*(x*(x+1))/2def problem1v2():    return sumDivBy(3) + sumDivBy(5) - sumDivBy(15)`