James Pine Has A Blog

I’ve started working through the problems at projecteuler, using Python. After playing around with Erlang for a while, I began to dislike the way the programming methodologies were baked into the language. It’s not that I disagreed with them, but sometimes it’s overkill to HAVE to do things via the idioms of assign once and message passing. Perhaps I’ll resolve these problems in Erlang one day, but for now, I decided to experiment with Python.

The first problem seemed trivial enough, sum all the multiples of 3 and 5 below 1000. My first solution looked like this:

def sumMultiplesOf3And5():
 total = 0
 for i in range(1000):
  if i % 3 == 0 or i % 5 == 0:
   total += i
 return total

After flipping through more documentation I came up with this 1 liner:

sum([i for i in range(1000) if i % 3 == 0 or i % 5 == 0])

Coming from Erlang, list comprehensions seem pretty natural, and I find Python’s syntax a bit more readable (actually, almost everything in Python seems more readable than Erlang).

There’s a built-in execution timer so I ran this on my 1.6Ghz Intel Atom powered Eee PC:

iterations = 1000
t = timeit.Timer("sumMultiplesOf3And5()","from __main__ import sumMultiplesOf3And5")
print "Answer: %d. %d iterations took %.3f seconds" % (sumMultiplesOf3And5(), iterations, t.repeat(1,iterations)[0])

t = timeit.Timer("sum([i for i in range(1000) if i % 3 == 0 or i % 5 == 0])")
print "Answer: %d. %d iterations took %.3f seconds" % (sum([i for i in range(1000) if i % 3 == 0 or i % 5 == 0]),iterations,t.repeat(1,iterations)[0])

Answer: 233168. 1000 iterations took 1.173 seconds
Answer: 233168. 1000 iterations took 1.208 seconds

So the list comprehension is a tad bit slower. I guess Python is creating an intermediary list which gets passed to the built-in sum function, no big deal. However, I took a second look at the range() function and saw I could get rid of the modulo operations and list comprehensions, at the expense of some extra subtraction, and this:

t = timeit.Timer("sum(range(3,1000,3)) + sum(range(5,1000,5)) - sum(range(15,1000,15))")
print "Answer: %d. %d iterations took %.3f seconds" % (sum(range(3,1000,3)) + sum(range(5,1000,5)) - sum(range(15,1000,15)),iterations,t.repeat(1,iterations)[0])

yields approximately a 13x increase in speed:

Answer: 233168. 1000 iterations took 0.093 seconds

The nice thing about projecteuler is, once you’ve submitted a correct answer, you have access to the forum for that problem. People post code samples in various languages and explanations of their algorithms. One code sample was a 1 line equation and when I saw the words “arithmetic sequence” it hit me how easy this could be. Granted, the solutions above are fine as computers are good at arithmetic and manipulating sequences of numbers, but this problem could quickly be solved with pen and paper as well. The sum of a sequence of numbers from 1->n is: n*(n+1)/2. After fiddling a bit, I realized the more general equation for the sum of a sequence of numbers from m->n where m, n and all numbers in-between are multiples of m is: n*((n/m)+1)/2.

Therefore, to answer this question, one only need to compute (999*((999/3)+1)+995*((995/5)+1)-990*((990/15)+1))/2. Just for kicks:

def f():
 return (999*((999/3)+1)+995*((995/5)+1)-990*((990/15)+1))/2


t = timeit.Timer("f()","from __main__ import f")
print "Answer: %d. %d iterations took %.3f seconds" % (f(),iterations,t.repeat(1,iterations)[0])

Answer: 233168. 1000 iterations took 0.004 seconds