You are on the Home/Other Tutorials/Project Euler/Problem 1 page
Google
Web This Site

Project Euler - Problem 1

More about Project Euler.

Problem description

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.

Solution

We are asked to add two series of numbers.  The first is 3,6,9,...,996,999.  This can be represented as 3 *(1+2+3+...+332+333), or more generically, 3*(1+2+3+...+(n-1)+n), where n=(Limit-1)\3) with \ representing an integer division operator.  We use -1 since the requirement is "below 1000" and not "less than or equal to 1000."

The sum of all the numbers from 1 to n is given by n*(n+1)/2.  So, the required sum collapses to 3*n*(n+1)/2 where n=(1000-1)\3=333.

One can similarly compute the 2nd series of numbers 5*(1+2+...+(n-1)+n) where n=(Limit - 1) \ 5.

There is one more issue to address.  The 2 series have some number of overlapping elements.  These are numbers that are multiples of both 3 and 5, i.e., 15, 30, 45, etc.  These numbers have effectively been double-counted.  So, one set of these numbers should be subtracted.  Of course, these numbers themselves constitute the series 15*(1+2+...+n) where n= (Limit-1) \ 15.

Put the three series together to solve Problem 1 without any computer code!