Project Euler | Problem 1 - Multiples of 3 and 5
A tutorial about how to solve problem 1 from Project Euler.
I have decided to start with Project Euler. Project Euler is a website that collects mathematical problems for people who like to work on mathematics. I guess I am one of such people and I want to see how far I can get. If you do not know Project Euler, check out their website. They describe themselves as follows:
What is Project Euler?
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.
Along the way, I want to describe how I approach to solve these problems. Actually, the team from Project Euler asks to not share any solutions publicly outside of Project Euler (besides their website, they also have a forum). However, this rule does not apply to the problems 1 to 100 as long as you do not only post the solution but also the way how you got to solution (i.e., your code or calculations). You can find that rule on their about page (you need to be logged in).
I learned so much solving problem XXX, so is it okay to publish my solution elsewhere?
It appears that you have answered your own question. There is nothing quite like that "Aha!" moment when you finally beat a problem which you have been working on for some time. It is often through the best of intentions in wishing to share our insights so that others can enjoy that moment too. Sadly, that will rarely be the case for your readers. Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.
However, the rule about sharing solutions outside of Project Euler does not apply to the first one-hundred problems, as long as any discussion clearly aims to instruct methods, not just provide answers, and does not directly threaten to undermine the enjoyment of solving later problems. Problems 1 to 100 provide a wealth of helpful introductory teaching material and if you are able to respect our requirements, then we give permission for those problems and their solutions to be discussed elsewhere.
Since I want to respect their rules, I plan to post the solutions and how I got them only for problem 1 to 100 here. I hope this might also help others to get started with Project Euler.
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.
A naive approach to solve this problem is to use brute-force. We simply loop through all numbers between 3 and 999 and check which numbers are divisible by 3 or 5. The lower bound is 3 here, because we already know that 1 and 2 are not divisible by either 3 or 5. The upper bound is 999, because the problem description says that we should consider numbers below 1000.
To check if a number is divisible by 3 or 5, we can use the modulo operator (in Python it's the % sign). The modulo operator gives you the rest of a division operation. For instance, if we want to calculate 5 / 2, we get 2.5. However, if we want to receive the result in whole numbers, we get 2 with a rest of 1 (2 * 2 = 4 and 4 + rest 1 is 5). The modulo operator gives you the rest (here 1). We can use this to test if a number is divisible by another number, since in this case the rest must be 0. So, to check if a number is divisible by 3, we can use the expression number % 3 == 0 (similarly we can check if a number is divisible by 5 using the expression number % 5 == 0).
The whole code looks as follows (in Python):
def multiples():
n = 999
sum = 0
for i in range(n,2,-1):
if (i % 3 == 0) or (i % 5 == 0):
sum += i
return sum
%time multiples()
The solution is 233168. The calculation took 163 microseconds.
Actually, after a while it came to my mind, that you don't need to write any code to solve the problem. You can solve it only by using mathematics.
The numbers that are divisible by 3 are
$3, \quad 6, \quad 9, \quad 12, \quad ...$
The numbers that are divisible by 5 are
$5, \quad 10, \quad 15, \quad 20, \quad ...$
If a number is divisible by 3, it must also be a multiple of 3. So, we can also write the list of numbers as follows
$3\cdot1 (=3), \quad 3\cdot2 (=6), \quad 3\cdot3 (=9), \quad 3\cdot4 (=12), \quad ...$
Similarly for the numbers divisible by 5
$5\cdot1 (=5), \quad 5\cdot2 (=10), \quad 5\cdot3 (=15), \quad 5\cdot4 (=20), \quad ...$
However, what we actually need is the sum of the numbers divisible by 3
$3\cdot1 \quad + \quad 3\cdot2 \quad + \quad 3\cdot3 \quad + \quad 3\cdot4 \quad + \quad ...$
and the numbers divisible by 5
$5\cdot1 \quad + \quad 5\cdot2 \quad + \quad 5\cdot3 \quad + \quad 5\cdot4 \quad + \quad ...$
We can pull out the 3
$3 \cdot (1 \quad + \quad 2 \quad + \quad 3 \quad + \quad 4 \quad + \quad ...)$
and the 5
$5 \cdot (1 \quad + \quad 2 \quad + \quad 3 \quad + \quad 4 \quad + \quad ...)$
Now, we can make use of the following formula for summations
$$1 \quad + \quad 2 \quad + \quad 3 \quad + \quad ... \quad + \quad n \quad = \quad \sum^n_{i=1} i \quad = \quad \frac{n \cdot (n + 1)}{2}$$
and use them for our sum of numbers divisible by 3
$$3 \cdot (1 \quad + \quad 2 \quad + \quad 3 \quad + \quad ... \quad + \quad n) \quad = \quad \frac{3 \cdot n \cdot (n + 1)}{2}$$
and for our sum of the numbers divisible by 5
$$5 \cdot (1 \quad + \quad 2 \quad + \quad 3 \quad + \quad ... \quad + \quad n) \quad = \quad \frac{5 \cdot n \cdot (n + 1)}{2}$$
But what is n (the last/highest number) in both cases? Well, the upper bound is 1000. Thus, the highest number divisible by 3 must satisfy the following requirement
$$3 \cdot n \quad < \quad 1000$$
Now, we can calculate the n
$$n \quad < \quad \frac{1000}{3}$$
$$n \quad < \quad 333.\overline{33}$$
This means that n is 333, because 333 is the highest whole number smaller than 333.33. Similarly, the highest number divisible by 5 must satisfy the following requirement
$$5 \cdot n \quad < \quad 1000$$
Now, we can calculate the n
$$n \quad < \quad \frac{1000}{5}$$
$$n \quad < \quad 200$$
This means that n is 199, because 199 is the highest whole number smaller than 200. Now, we can set the n in both formulas and add both formulas together
$$\frac{3 \cdot 333 \cdot (333 + 1)}{2} \quad + \quad \frac{5 \cdot 199 \cdot (199 + 1)}{2} \quad = \quad 266333$$
However, this is not the final solution yet. Why? Because we counted a few numbers twice. Which? Well, the numbers divisible by 15, because the numbers divisible by 15 are divisible by 3 and by 5. The numbers divisible by 15 are multiples of 15
$15\cdot1 (=15), \quad 15\cdot2 (=30), \quad 15\cdot3 (=45), \quad 15\cdot4 (=60), \quad ...$
But they are also multiples of 3 and 5, which becomes clear when we write the multiples of 15 as follows
$3\cdot5\cdot1 (=15), \quad 3\cdot5\cdot2 (=30), \quad 3\cdot5\cdot3 (=45), \quad 3\cdot5\cdot4 (=60), \quad ...$
since 3 times 5 is 15. So, this means we added these numbers twice when we calculated our sum, because they were included in the sum of the numbers divisible by 3 and in the sum of the numbers divisible by 5. Hence, we need to substract each of the numbers divisible by 15 once from our sum of numbers divisible by 3 and 5. For this we need to calculate the sum of the numbers divisible by 15 and substract that sum from our sum of the numbers divisible by 3 and 5. Let's calculate the sum of the numbers divisible by 15 first
$$\frac{15 \cdot n \cdot (n + 1)}{2}$$
The highest number divisible by 15 must satisfy the following requirement
$$15 \cdot n \quad < \quad 1000$$
Now, we can calculate the n
$$n \quad < \quad \frac{1000}{15}$$
$$n \quad < \quad 66.\overline{66}$$
This means n is 66, because 66 is the highest whole number smaller than 66.66. Now, let's calculate the sum of the numbers divisible by 15
$$\frac{15 \cdot 66 \cdot (n + 1)}{2} \quad = \quad \frac{15\cdot66\cdot67}{2} \quad = \quad 33165$$
Finally, let's substract the sum of the numbers divisible by 15 from our sum of the numbers divisible by 3 and 5
$$266333 \quad - \quad 33165 \quad = \quad 233168$$
The solution is 233168. This is the same solution that we also received with our naive approach above.