Blake O'Hare's School of Computer Science

Python 101: HW 1 Solution

Homework 1 was to solve the first problem on Project Euler. The first problem is as follows:

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.

After I stopped streaming, it occured to me that I never mentioned that you can use the words "and" and "or" in if statements. Had I mentioned this, your ideal solution would look something like this...

total = 0
counter = 0
while counter < 1000:
    if counter % 3 == 0 or counter % 5 == 0:
        total = total + counter
    counter = counter + 1
print total

But of course you wouldn't have known to use the "or" operator. And you can't simply just do this:

total = 0
counter = 0
while counter < 1000:
    if counter % 3 == 0:
        total = total + counter
    if counter % 5 == 0:
        total = total + counter
    counter = counter + 1
print total

...because numbers that are both divisible by 3 and 5 would get double counted. 300, for example. So here's an example of how a clever mathematician would approach the problem...

total = 0
counter = 0
while counter < 1000:
    valid = 0
    if counter % 3 == 0:
        total = total + counter
    if counter % 5 == 0:
        total = total + counter
    if counter % 15 == 0:
        total = total - counter
    counter = counter + 1
print total

Noting that all the double-counted numbers would be multiples of 15, you could add all multiples of 3 and 5 together, but subtract all multiples of 15 to balance the double counting.

For a mathematically unclever person like myself who thinks like a general programmer, the ideal solution would look something like this:

total = 0
counter = 0
while counter < 1000:
    valid = 0
    if counter % 3 == 0:
        valid = 1
    if counter % 5 == 0:
        valid = 1
    if valid == 1:
        total = total + counter
    counter = counter + 1
print total

Here, the variable "valid" is being set to 0 on each iteration. If the counter is a multiple of 3 or 5, it gets set to 1. If it's 1 by the end of the loop, you add it to total, but just once. No double-counting.