This post solves Project Euler problem 1 in Python and Clojure.

Problem:

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.

Python Solution

As a first Python solution, we simple sum over a list constructed out of integers having the desired property: they are either divisible by 3 or 5.

#!/usr/bin/python
 
import time
 
start = time.time()
 
s = sum([i for i in range(1000) if (i % 3 == 0 or i % 5 == 0)])
 
elapsed = time.time() - start
 
print "result %s returned in %s seconds" % (s,elapsed)

This finds the result relatively quickly.

result 233168 returned in 0.000147819519043 seconds

There are some downsides to that solution though. Namely, every integer between 0 and 999 is being checked to see if it is divisible by 3 or 5. We can improve on this by explicitly constructing a few lists. First, we’ll look at all multiples of 3 in the given range. Then, we’ll consider all multiples of 5 which are not multiples of 3. (If we considered all multiples of 5, we’d be counting twice those numbers which happen to be divisible by 5 and divisible by 3 – as they’ve already been counted.)

#!/usr/bin/python
 
import time
 
start = time.time()
 
s = 0
 
# add in all multiples of 3
for i in range(3,1000,3): s += i
 
# Add in multiples of 5 that are no also multiples of 3.
# This includes numbers of the form 5+15n and 10+15n between 0 and 1000.
for i in range(5,1000,15): s += i
for i in range(10,1000,15): s += i
 
elapsed = time.time() - start
 
print "result %s returned in %s seconds" % (s,elapsed)

This does indeed speed up the process a bit, as shown here:

result 233168 returned in 4.79221343994e-05 seconds

In fact, that’s roughly 3 times as fast as the original. There are some other tricks that we can throw at this. One option is to use Python sets instead of lists.

#!/usr/bin/python
 
import time
 
start = time.time()
 
s1 = set(range(0,1000,3))
s2 = set(range(0,1000,5))
ss = s1.union(s2)
s = sum(ss)
 
elapsed = time.time() - start
 
print "result %s returned in %s seconds" % (s,elapsed)

In this example, we’re using the union of two sets (those integers divisble by 3 and those divisible by 5) to get around the problem of integers that are divisible by both 3 and 5 being counted twice. Let’s see how fast that runs.

result 233168 returned in 3.31401824951e-05 seconds

That’s slightly faster than our best list method yet.

There’s a much better way to tackle this problem though. Another approach is to realize that the sum of all numbers between 1 and 1000 being divisible by 3 is

\[\sum_{j=1}^{333}3j = 3\sum_{j=1}^{333}j=3\times\frac{333(333+1)}{2}=3\times 55611=166833\]

and the sum of all numbers in the same range divisible by 5 is
\[\sum_{j=1}^{199}5j=5\sum_{j=1}^{199}j=5\times\frac{199(199+1)}{2}=5\times 19900=99500.\]

The integers that would be counted twice by doing the above sums are numbers that are both multiples of 3 and 5. If we take the two sums and then subtract every number that is both a multiple of 3 and 5, we will obtain the result.

\[15+30+45+\cdots+990=(3\cdot 5)\times(1+2+\cdots+66)\]

In closed form, that’s

\[15\sum_{j=1}^{66}j=15\times\frac{66(66+1)}{2}=15\times 2211=33165.\]

Encoded in Python, we have the following, which should find our result nice and quickly.

#!/usr/bin/python
 
import time
 
 
# The sum of all numbers from 1 to n is (n*(n+1))/2. Using this formula, we can
# find the answer in the following way.
 
# Notice that all of the multiples of 3 look like this:
#   3 + 6 + 9 + ... + 996 + 999 = 3 * (1 + 2 + ... + 333) = 3 * (333*334)/2
 
# Similarly, the sum of all multiples of 5 looks like this:
#   5 + 10 + 15 + ... + 995 = 5 * (1 + 2 + ... + 199) = 5 * (199*200)/2
 
# If we were to add these two integers together, we would be counting multiples
# of 15 twice (once as multiples of 3 and once as multiples of 5). So, we take
# the two numbers above and subtract an instance of all multiples of 15:
#   15 + 30 + ... + 990 = 15 * (1 + 2 + ... + 66) = 15 * (66*67)/2
 
start = time.time()
 
s = ((3*333*334)/2) + ((5*199*200)/2) - ((15*66*67)/2)
 
elapsed = time.time() - start
 
print "result %s found in %s seconds" % (s, elapsed)

We execute this and find the result about 35 times as fast as our fastest method yet.

result 233168 found in 9.53674316406e-07 seconds

Clojure Solution

The idea is to create a sequence of numbers from 1 to 1000, use a map with a function that filters out the numbers that aren’t divisible by 3 or 5, and use a reduce with a sum on the remaining sequence.

(ns project-euler-001.core
  (:gen-class))
 
(defn f
  "Takes an input x. If 3 or 5 divides x, returns x. Otherwise, returns 0."
  [x]
  (if (or (= (mod x 3) 0) (= (mod x 5) 0)) x 0))
 
(defn -main
  "Project Euler Problem 1 - Clojure Solution"
  [& args]
  (println (time (reduce + (map f (range 1 1000))))))