Greetings and salutations, my friends. Today is the start of a regular series showing the many Euler problems as I work through them, including my solution, the computationally optimal solution (if there is widely-agreed upon solution for this) and any mathematics behind it.
The Problem
Euler Problem 1 is a very simple one to begin with (they weren't going to make the first problem immensely hard or it would scare everyone away!)
It 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.
My Solution (C)
There's no hidden mathematical withcraft here, folks, this one is literally as simple as it sounds. To start with, let's look at my computational solution that I wrote about 10 minutes ago in C:
int main(){
int sum = 0;
for(int i = 0; i < 1000; ++i){
if(i % 3 == 0 || i % 5 == 0){
sum += i;
}
}
printf("%d\n", sum);
return 0;
}
For anyone unfamiliar to C, this code basically enumerates through numbers until it reaches 1000, and checks each number for being a multiple of 3 or 5 by using the modulus operation - which returns the resulting remainder of a division. If the remainder of the number to be tested divided by 3 or 5 is equal to 0 then we can safely say that the number is a multiple of 3 or 5.
If the number is indeed a multiple of 3 or 5 then it sets the sum variable equal to itself plus the new number - effectively adding summing all multiples of 3 and 5 below 1000 - just as the problem says.
The answer that this code outputs is:
233168
I input this into the Euler problem website and it was indeed correct.
While looking other people's answers , I learned that this problem could be done entirely mathematically, without use of a computer with surprising ease.
The problem can easily be solved like this:
(sum of all multiples of 3 below 1000) + (sum of all multiples of 5 below 1000) - (sum of all multiples of 3 * 5 = 15 below 1000)
The reason we minus the sum of all multiples of both 3 and 5 is because we would be double counting them otherwise, and would get the wrong answer.
That is all for today, folks, I shall be posting the next problem and it's solution in the next day or two. I hope you have enjoyed and for now, adios :)