Late Post! But this is really something worth adding into the blog. About 2 weeks ago, I met a developer who introduces me to Project Euler, a website that has some really difficult mathematical problems that’s bound to test not only your math skills but your programming skills as well. He challenges me to answer one of the problems. One of them is Problem no.1, which goes something like this:
==================================
Multiples of 3 and 5
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.
==================================
See, first problem and it already sent me sweating and breaking some neurons! So the challenge goes like this, we need to find the sum of all the multiples of 3 or 5 for the numbers below 1000. For example, multiples of 3 includes 3, 6, 9, 12, 15… while multiples of 5 are 5, 10, 15, 20, 25… below 1000 means it should be up to 999 for multiples of 3 (ie. …990, 993, 996, 999), while 995 for multiples of 5 (ie. …980, 985, 990, 995). Now we have to add the multiples of both 3 and 5, so it goes like this: 3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24, 25… and up until …990, 993, 995, 996, 999. That would be 3+5+6+9+10…
Now, we are ask to build a program in any language that does the equation. Earlier, this developer friend of mine by the name of Mike suggested that I use Python because it’s much easier, then I told him I am more comfortable with PHP, so I went to solve it in PHP.
I was able to build this code…
<?php
for($x=3, $max=1000; $x <= $max; $x++){
if (($x % 3) == 0) {
echo $x;
}
}
?>
and
<?php
for($y=5, $max=1000; $y <= $max; $y++){
if (($y % 5) == 0) {
echo $y;
}
}
?>
I thought of looping it using the for loop. The instruction is meant to seek for the multiples of 3 and 5. It states that for variable x (y), which is equivalent to 3 (5), set variable $max to 1000, $x ($y) should be less than or equal to $max which is 1000. Increment $x ($y). It’s followed by an if statement that if $x ($y) with a modal value of 3 (5) is equal to 0, then display the looped value of $x ($y). So the preprocessor will start counting from 0 and upwards, if it finds the multiples of 3 (5), it will display it… (result: 369121518… or 3, 6, 9, 12, 15… and 510152025 or 5, 10, 15, 20, 25…) now, I thought of merging the two loops and add their value. But I failed!
Another developer friend of mine who was good at math, came up with a code written in JAVA, which is where is he more adept at, and converted it into PHP. The outcome is:
<?php
$sum = 0;
for($x=3, $max=1000; $x <= $max; $x++) {
if((($x % 3) == 0) || (($x % 5) == 0)) {
echo $x . ' ';
}
}
It’s technically almost the same as my code, but better… he was able to merge both multiples of 3 and 5 and come out with 3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24, 25, 27, 30, 33, 35, 36… btw, the || in his code is the operator that means “or”. He used the same variable to produce the multiples of both 3 and 5.
Then he adds all of the values with this code:
<?php
$sum = 0;
for($x=3, $max=1000; $x <= $max; $x++) {
if((($x % 3) == 0) || (($x % 5) == 0)) {
echo $x . ' ';
$sum = $sum + $x;
}
}
echo ' = ' . $sum;
He cleverly created the variable $sum to add all of the contents of $x so the loop goes like when it comes up with 3, it adds that into $sum and $sum gets a new value of 3 (from previously 0). In the next loop runtime, it gets 5 then adds that into $sum which already has 3 so it becomes 3+5, and ends up with a new value of 8. The loop continues to do this until it reaches the limit <= 1000, in which from there it will start getting the “false” value and thereby terminate the loop as per its function.
The result is the answer 234168.
I showed it to Mike, but he was not quite impressed. He said, that while our method works, it will fail if we have a bigger $max value, let’s say less than 100,000,000,000,000,000,000. PHP will struggle to process everything and it would take more processing time, if not crash.
He wrote his own method:
<?php
$max = 1000;
function sumOfNaturalNumbers($n) {
return ($n * ($n + 1)) / 2;
}
$sum = sumOfNaturalNumbers($max / 3) * 3;
$sum += sumOfNaturalNumbers($max / 5) * 5;
$sum -= sumOfNaturalNumbers($max / 15) * 15;
echo $sum;
Brilliantly, he uses the summation notation formula to avoid the intensive resource-consuming process of the for loop. I ask him what += and -= means as these operators seem new to me. He said += will add the value of the variable from the right to the variable to the left. In short, it works like a shortcut for (sumOfNaturalNumbers($max / 5) * 5) + $sum. The same with -=, only this time, it’s subtraction.
He got the idea from StackExchange.com.
He arrived at the answer which is different from ours. His answer is 233833.33333333.
But unfortunately…
When I checked at Project Euler…
I also checked our answer and it seems nobody among us got it right. LOL
OK, it’s not that we are dumb programmers, nor are we poor at math. But it seems we didn’t understood the problem. So, I reanalyzed the problem to figure out why we got the wrong answer. Then I notice that it says “below 1000”. But… we set it to less than or equal to 1000. While multiples of 3 has no problem since the highest it can go is 999, which is below 1000, it’s problematic for multiples of 5 which can arrive at 1000. So I redid the formula.
Using the loop, the problem can be solve by changing the loop statement from $x <= $max to $x < $max so it turns out like this:
<?php
$sum = 0;
for($x=3, $max=1000; $x < $max; $x++) {
if((($x % 3) == 0) || (($x % 5) == 0)) {
echo $x . ' ';
$sum = $sum + $x;
}
}
echo ' = ' . $sum;
Unfortunately for Mike’s formula, it takes more than just tweaking the $max variable. I had to set 3 variables and set it all of them to less than 1000.
<?php
$max3 = 999;
$max5 = 995;
$max15 = 990;
function sumOfNaturalNumbers($n) {
return ($n * ($n + 1)) / 2;
}
$sum = sumOfNaturalNumbers($max3 / 3)*3;
$sum += sumOfNaturalNumbers($max5 / 5)*5;
$sum -= sumOfNaturalNumbers($max15 / 15) * 15;
echo $sum;
And after that, we got this:
How did we arrive at this equation? Using the Summation Notation formula Sum = N*(N+1)/2
Define:
S3 = 3+6+9+12+15+…+999 = 3*(1+2+3+…+333) = 3*333*334/2 = 166,833
S5 = 5+10+15+…995 = 5*(1+2+3+…+199) = 5*199*200/2 = 99,500
S15 = 15+30+45+…+990 = 15*(1+2+3+…+66) = 15*66*67/2 = 33,165
Now, S3+S5 includes all multiples of 3 and 5 but it includes all multiples 15 twice (double-count those).
S3+S5-S15 = 233,168
The correct answer is 233168. I’m the 764219th person in Project Euler to solve the problem. By the way, this problem is just 5% of the highest difficulty level in Project Euler and we already cracked our heads. Oh my god!
