Project Euler 1: Sum of the Multiples of 3 and 5

Project Euler is a cool site that I just stumbled upon. It contains problems which require both mathematics and programming to succeed. I decided to start writing a guide for Project Euler for those who need a little help. I will never write the complete answer, since you’ve got to do something by yourself. The first problem is straight-forward:

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.

You can solve this either through mathematics or through programming. If you want to go the mathematician’s way, you must first write an expression for it. The sum of the series is essentially the sum of two other series; the multiples of 3 below 1000 and the multiples of 5 below 1000. For the sum of these series, use the following formula:

n is the number of elements in the series. Therefore it equals 333 (999/3) for the first sum and 199 (999/5, rounded down) for the second one. a₁ is the first element, i.e. 3 and 5, respectively. a_n is the last element. That is 999 for the first (333*3) and 995 for the second (199*5). Now, we have:

Note, however, that there is a flaw here. The numbers which are multiples of both 3 and 5 are counted twice! In order to fix this, we need to find out which numbers are multiples both numbers. Of course, those numbers are the numbers divisible by the lowest common denominator of 3 and 5. That is 15. We will then subtract all numbers which are multiples of 15 in a similar way:

You’ve got to calculate it yourself.

It is much easier and faster (but less cool) to write a program which does the job for you. This perl script does the task well:

1
2
3
4
5
6
7

my $s = 0;
for ( my $n = 0; $n < 1000; $n++ ) {
	if ( ! ( $n % 3 && $n % 5 ) ) {
		$s += $n
	}
}
print $s;

• Line 1 sets $s (the sum) to 0, just to be sure.
• Line 2 starts the loop which will loop for $n (the current number) from 0 to 999.
• Line 3 checks whether $n is divisible by either 3 or 5.
• Line 4 adds $n to $s
• Line 7 prints the final sum.

Maybe Related?

• Project Euler 10: Sum of First Primes
• Project Euler 5: Find the Lowest Common Multiple
• Project Euler 8: Greatest Product of Consecutive Digits in String
• Project Euler 9: Pythagorean Triplets, Sum=1000
• Project Euler 6: Square of Sums Minus Sum of Squares