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))/2

def problem1v2():
    return sumDivBy(3) + sumDivBy(5) - sumDivBy(15)