Project Euler, Problem #1

The first problem within Project Euler isn’t meant to twist the brain in knots and is a gentle introduction to what is coming further down the road. The problem states:

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.

As I mentioned in my initial post about exploring Project Euler, I noted that I often write in a lowest common denominator with whatever language I’m using at the time. The net effect of that decision is often a working but poorly optimised solution or a solution that doesn’t fit well with the spirit of the programming language.

The solution to problem #1 took three distinct evolutions, the first of which is below and looks like a solution you’d likely see in any programming language:

i = 1
sum = 0

while i < 1000:
  if i % 3 == 0 or i % 5 == 0:
    sum += i
  i += 1

print sum

I wasn’t a fan of needing to declare the variables to start with for such a simple problem, so removed the need for the i but using the Python range function to generate a series of numbers. The range function allows you to generate any length series of numbers, starting and ending where you want with any stepping. By default, it starts at 0 and a stepping of 1 – which means range(1000) is going to generate a list of numbers from 0 – 999.

sum = 0

for x in range(1000):
  if x % 3 == 0 or x % 5 == 0:
    sum += x

print sum

Python provides functionality for its lists called list comprehensions. The idea behind a list comprehension is that you can perform the same action, whatever that may be, against each item in the set. In the final solution below, I have applied a filter (the if statements), which now only returns those items from the for x in range that match and I’m not applying an expression to the resulting matches (the solitary x before the for). Once collected the new list is passed to the sum function to yield our result.

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

2 thoughts on “Project Euler, Problem #1

  1. Could you have summed with the range stepping set to 3 & 5 rather than a brute force ‘try all numbers’ approach with singular stepping ?

    ie you already know the steps must be in 3s and 5s.

    For example:

    sum[range(0,1000,3) + range(0,1000,5)]

    This gives 266333.

  2. Andrew,

    There are plenty of different ways to solve the problems and there aren’t extra points for elegant versus brute force solutions.

    In your example, a solution like that would work so long as you could remove the duplicate items from the two lists. As an example, the first range statement will include the value 30, which will also be present in the second list. As such, it’ll be summed twice and you’d get an inflated result.

    Al

Comments are closed.