# Find the sum of all the multiples of 3 or 5 below 1000

How to solve this problem, I can not figure it out:

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.

-
@J.M.:Much better title thank you! –  AD. Nov 7 '10 at 13:42
@AD: Sometimes straightforward is beautiful. ;) –  Ｊ. Ｍ. Nov 7 '10 at 13:44
This is actually Project Euler problem no 1 and can be solve efficiently by using mutual inclusion exclusion. –  Quixotic Nov 7 '10 at 13:45
This is the postage stamp lemma! Every number greater than 7 can be expressed as $3x+5y$ with $x,y>0$ crazyproject.wordpress.com/2010/10/22/… –  Nate Iverson Jun 28 '12 at 13:10

The previously posted answer isn't correct. The statement of the problem is to sum the multiples of 3 and 5 below 1000, not up to and equal 1000. The correct answer is \begin{eqnarray} \sum_{k_{1} = 1}^{333} 3k_{1} + \sum_{k_{2} = 1}^{199} 5 k_{2} - \sum_{k_{3} =1}^{66} 15 k_{3} = 166833 + 99500 - 33165 = 233168, \end{eqnarray} where we have the used the identity \begin{eqnarray} \sum_{k = 1}^{n} k = \tfrac{1}{2} n(n+1). \end{eqnarray}

-

The multiples of 3 are 3,6,9,12,15,18,21,24,27,30,....

The multiples of 5 are 5,10,15,20,25,30,35,40,45,....

The intersection of these two sequences is 15,30,45,...

The sum of the first numbers 1+2+3+4+...+n is n(n+1)/2.

The sum of the first few multiples of k, say k+2k+3k+4k+...+nk must be kn(n+1)/2.

Now you can just put these ingredients together to solve the problem.

To find n use 1000/3 = 333 + remainder, 1000/5 = 200 + remainder, 1000/15 = 66 + remainder and then sum multiples of 3: $3\cdot 333(333+1)/2 = 166833$. multiples of 5: $5\cdot 200(200+1)/2 = 100500$ and subtract multiples of 15 $15\cdot 66(66+1)/2 = 33165$ to get 234168.

-
The answer that you have provided is incorrect. Take a look at the accepted answer and see how you can improve your own post. –  gekkostate Jul 11 at 23:59