TREY STOUT

What You Need

• Python 3.x for your platform
• about 45 minutes
• your brain

Problem 1

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.

Let's break down what this problem is all about. It concerns factoring numbers and summing numbers. If you know how to do addition and division we're ready to rock. Since the problem gives us a nice example for a small number (10) we should write our code to solve that. If the code works for a small set, it should work for a larger set.

>>> 5 + 9

>>> 13 // 5
2
>>> 13 / 5
2.6
>>> 13 % 5
3

>>> a = 2
>>> b = 3
>>> a + b
5

1
2
3
4
5
6
7
8

"""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."""

limit = 10
print("Starting to find multiples up to", limit)

IF

An if statement is just that. It's a branching of logic where you can alter the flow of a program based on variables or expressions. Our brains handle thousands of these a day, and programming is basically identifying "ifs" and reacting accordingly. You have to pee, you walk to the bathroom. There are two doors. If you're a male, you go into the men's room, otherwise you go into the women's room. Let's start out by finding out if 10 has 3 or 5 as multiples. Your program should now look like this...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

"""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."""

limit = 10 print("Starting to find multiples up to", limit)

if limit % 5 == 0:
    print("5 is a multiple of", limit)
if limit % 3 == 0:
    print("3 is a multiple of", limit)

Save (CTRL+S) and run the program (F5) and you should see the following as output

Starting to find multiples up to 10 5 is a
multiple of 10

But what about the third print statement? Why did the output not show "3 is a multiple of 10"? Well because it's not. Our if statements were basically saying if you can modulus 5 into 10 and the result is 0, then 5 is a multiple of 10, so print that out. We then did the same thing for 3. But 3 goes into 10, 3 times with a remainder of 1. And 1 does not equal 0, so our print statement didn't execute. This is the power of if. If you notice in our if statements when were wanted to test if something equaled another something, we used == instead of =. This is very important as = is the "assignment operator". You use = when you want to set something as equal to another thing. When you want to test if two things are equal you use ==.

So this is great and all, but the problem states we should be finding all the numbers from 1 up to 1000. Not just 10. Man, it would suck to copy paste those tests 9 more times, let alone 999 more times. So how do we tell the machine to test those numbers for us without wearing out our keyboards? The second most powerful idea in programming:

LOOPS

Anytime you need a machine to do something over and over, you use a loop. There are many different kind of loops, including the famous infinite loop (which is why our keyboards ever had a BREAK key). For our purposes here we want to loop over the integers from 1 to 10 and test if each one has 3 or 5 as multiples.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

"""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."""

limit = 10 print("Starting to find multiples up to", limit)
for i in range(1, limit):
    print("Checking", i) if i % 5 == 0:
        print("5 is a multiple of", i)
    if i % 3 == 0:
        print("3 is a multiple of", i)

Hey check it out, we made a loop. The line for i in range(1, limit): tells the program to start a loop over the range of integers from 1, to limit (10). Now notice the code under the for line is indented. This is called the loop body. The for line states the boundaries of the loop, or how the loop should iterate. The indented code under it says what to do on each step. On each step of the loop, python will set the variable i for us, to whatever is next in the loop. So in plain english, this code says:

# Do the following 9 times starting with the number 1 # Set i to the current loop step (1) # Print out which number the loop is currently on (i) # Check if i modulus 5 is zero, if it is, then print out a message to that effect # Check if i modulus 3 is zero, if it is, then print out a message to that effect # Set i to the next value and go back to step 2, unless i was already set to the last value of the loop

When you run this program you should see the following...

Starting to find multiples up to 10
Checking 1
Checking 2
Checking 3
3 is a multiple of 3
Checking 4
Checking 5
5 is a multiple of 5
Checking 6
3 is a multiple of 6
Checking 7
Checking 8
Checking 9
3 is a multiple of 9

Hey it works! We just checked all the numbers from 1 to 10 without having to copy/paste a bunch of code. It's a little wordy. It was nice seeing that it checked all the numbers, but we don't need to see that every time, so let's comment that part out. You can turn any single line into a comment by putting a # at the start of the line. This will make our output little more concise. Also, the problem stated that we wanted the sum of these numbers, not just the numbers. So let's change it a bit to be more in line with the original problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

"""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."""

limit = 10 print("Starting to find multiples up to", limit)

total = 0
for i in range(1, limit):
    #print("Checking", i)
    if i % 5 == 0 or i % 3 == 0:
        total += i
        print(i, "has either 3 or 5 as a multiple. Total is now:", total)

print("total: ", total)

There's actually a lot that changed here.

Line 9

Before the loop, we set a new variable called total we will use this to track the total of numbers that we find. It starts out at 0 because before the loop starts we haven't found any numbers.

Line 11

On the first line inside the loop you can see we've commented out the line that prints "Checking..." to keep our output from being too wordy. You comment out code in this manner instead of deleting it in case you want to put it back at some point. All you'd have to do to get it back is remove the "#".

Line 12

We combined the two if statements into a single compound statement. The if statement now reads

"if the current loop value modulus 5 is zero OR the current loop value modulus 3 is zero..."

If a number i satisfies either one of these statements, then we execute the code below the if statement. If i matches, then we add it to the total with +=. This means add it to the value that total already has. If we had used just = it wouldn't accumulate a sum, total would just hold the last value of i that the loop ran. On each step we also print out the number that matched, and what the running total is on that step.

Line 16

We un-indent from the for loop, meaning Line 16 will run after the for loop is finished. As the last line of the program, it will print out the total that we've accumulated.

When you run this program it should now look like this...

Starting to find multiples up to 10
3 has either 3 or 5 as a multiple.
Total is now: 3
5 has either 3 or 5 as a multiple.
Total is now: 8
6 has either 3 or 5 as a multiple.
Total is now: 14
9 has either 3 or 5 as a multiple.
Total is now: 23
total: 23

Wicked! As per our comment at the top of the file, this is the answer we were looking for! Maybe we can solve the whole problem now! As you'll recall we're supposed to be doing this for numbers from 1 to 1000. And since we're such awesome programmers this doesn't require many changes. Since we used a variable for the limit, we can just add a couple of more zeros to change 10 to 1000! Let's make a couple of changes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

"""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."""

limit = 1000
print("Starting to find multiples up to", limit)

total = 0 for i in range(1, limit):
    #print("Checking", i)
    if i % 5 == 0 or i % 3 == 0:
        total += i
        #print(i, "has either 3 or 5 as a multiple. Total is now:", total)

print("total: ", total)

Line 6

We upped the limit to 1000. If you had just used 10 everywhere limit is written you'd have to change it in several places, meaning more work, and more opportunity to miss a spot and introduce a nasty bug into the program. Variables are your friends.

Line 14

We commented out this line so that we don't get so much spam in our output.

After running this program you should see this in the output window...

Starting to find multiples up to 1000 total:
233168

Which is the correct answer! It may comfort or frustrate you to know you can do this whole program in a single line of python. It's a bit more obfuscated, but it works nonetheless.

# complete program
print("total: ", sum([i for i in range(1, 1000) if i % 5 == 0 or i % 3 == 0]))

See if you can figure out what this one line is doing.

Bonus Points

How efficient is this algorithm? Did you notice a speed decrease in changing limit from 10 to 1000? What about 1000000 or 1000000000? How long does it take your machine to compute? Is there a better way to solve this?

Thanks for following along. I hope you learned something and had a good time.

In the next section I'll cover how brute force approaches like this aren't always the best idea. And how a little bit of math knowledge puts you leaps and bounds ahead of most other programmers out there.</a>