## April 12, 2008

at
Saturday, April 12, 2008
Labels:
Computer Science,
Lisp,
Project Euler,
Python
Posted by
Billy

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)

Subscribe to:
Post Comments (Atom)

## 0 comments:

Post a Comment