Project Euler - Problem 001

Project Euler - Problem 001

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.

Well, this is an easy one, but it's a great way to introduce the concept of modulo.

Remember having to do long division in elementary school? Lots of multiplication, subtracting, etc. to get a quotient and a remainder in the end. Most people focused on the quotient as the answer to the problem, while the remainder didn't get a second glance. Well, the modulo reverses that situation, only focusing on the remainder, and pretty much ignoring the quotient.

Most programming languages have a function for modulo, and Python is no different; it uses "%" as the modulo operator. Also, different from your pocket calculator, we want to get the integer portion of the division, chopping off the decimal component. Python's operator for integer division is "//". So let's play with some examples:

>>> 10 // 2
5
>>> 9 // 2
4
>>> 10 % 2
0
>>> 9 % 2
1

So, for any number a, where a // b = c and a % b = d, a = b * c + d. c is the quotient, and d is the modulo.

So how does this solve our problem? Well, if you think about it, if x is a multiple of y, then x % y = 0, meaning there's no remainder when you divide x by y.

Let's write some (pseudo)code:

total = 0
for each number X between 1 and 1000:
if X % 3 = 0 or X % 5 = 0:
total = total + X
end if
end for
print total

Now to convert that to Python, we need to know a few things about the language. I'll provide lines from my solution as we go along:


total = 0

• Python uses what's known as "duck typing", from the phrase "If it walks like a duck, and quacks like a duck, it's a duck". So, if it's a number, it won't worry if it's an integer, a float (decimal), a long (really large integers), etc.; in terms of operations, it'll use the best type for the result so that it won't lose information. Also, it's loosely typed, meaning that you don't have to declare a variable as a certain type before storing a value in it. Python automatically assumes you know what you want to do with your variables, so it lets you get away with almost anything; however, this also means that it's your responsibility to remember what kind of value you put into a variable.

for x in xrange(1000):

• The looping structure here is a for loop, and every time it enters the loop, it'll take the next number between 1 and 999. The xrange function generates all the required numbers as they are needed. (The range and xrange statements always stop one before the argument, so xrange(1000) will offer 999 as its last value.)

if x % 3 == 0 or x % 5 == 0:

• The math has been explained, and the == is not assigning a value to x % 3, but asking the question "Is the result of x % 3 equal to 0?". It'll either be true or false, and based on that, it will continue into the body of the if statement, or jump over it. The or in the middle just establishes that if either of the questions is true, then the body of the if statement should be executed.

total = total + x

• This just creates a running total. The new total is equal to the previous total plus the value of x.

print total

• This just outputs the value of the total after having run through all values of the range. Hey, we need to know what the result is to input it into Project Euler!

Another particularity of Python is that indentation is used to see what statements are included in the loop and if conditional. So the above looks like:

total = 0
for x in xrange(1000):
    if x % 3 == 0 or x % 5 == 0:
        total = total + x
print total

That may be weird for some people coming from other languages, and it takes some getting used to. I keep wanting to use braces a la Java and C++, but after a while it makes sense, sort of. It's also one of the more endearing qualities of Python; in other languages, the indentation isn't a requirement, so even though indentation helps understand what's going on, some programmers can mess it up without any adverse effects in the code. In Python, you *have* to indent to make your code work, so there's no getting around it.

Since this one is pretty much solved off the bat, no separate solution is provided.