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


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

(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)