32
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ @J.M.:Much better title thank you! $\endgroup$ – AD. Nov 7 '10 at 13:42
  • 1
    $\begingroup$ @AD: Sometimes straightforward is beautiful. ;) $\endgroup$ – J. M. is a poor mathematician Nov 7 '10 at 13:44
  • 12
    $\begingroup$ This is actually Project Euler problem no 1 and can be solve efficiently by using mutual inclusion exclusion. $\endgroup$ – Quixotic Nov 7 '10 at 13:45
  • $\begingroup$ 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/… $\endgroup$ – N8tron Jun 28 '12 at 13:10
62
$\begingroup$

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}

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The one who posted the answer 233168, please explain that answer in detail . It would be really helpful for us if you will explain. $\endgroup$ – user126936 Feb 7 '14 at 9:16
  • $\begingroup$ The first two sums account for multiples of $3$ and $5$, the last sum accounts for over-counting multiples of $15$ (which can appear in either of the first two sums). $\endgroup$ – user02138 Feb 7 '14 at 13:12
  • $\begingroup$ For n=10; and k =3; ( 3 * (3+1) / 2) * 3 $\endgroup$ – shiva Jul 8 '14 at 10:02
  • 8
    $\begingroup$ how did you know to do that? $\endgroup$ – zurbergram Jun 30 '15 at 3:19
  • $\begingroup$ There is a general principal in counting things in several sets called "inclusion-exclusion". If the things can be in any of several sets, add the totals for each set, subtract the number of things that are in exactly two of the sets, add the number of things that are in exactly three of the sets, etc. $\endgroup$ – richard1941 Sep 12 '18 at 6:10
29
$\begingroup$

First of all, stop thinking on the number $1000$ and turn your attention to the number $990$ instead. If you solve the problem for $990$ you just have to add $993, 995, 996$ & $999$ to it for the final answer. This sum is $(a)=3983$

Count all the #s divisible by $3$: From $3$... to $990$ there are $330$ terms. The sum is $330(990+3)/2$, so $(b)=163845$

Count all the #s divisible by $5$: From $5$... to $990$ there are $198$ terms. The sum is $198(990+5)/2$, so $(c)=98505$

Now, the GCD (greatest common divisor) of $3$ & $5$ is $1$, so the LCM (least common multiple) should be $3\times 5 = 15$.

This means every number that divides by $15$ was counted twice, and it should be done only once. Because of this, you have an extra set of numbers started with $15$ all the way to $990$ that has to be removed from (b)&(c).

Then, from $15$... to $990$ there are $66$ terms and their sum is $66(990+15)/2$, so $(d)=33165$

The answer for the problem is: $(a)+(b)+(c)-(d) = 233168$

Simple but very fun problem.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ +1 but would be a bit better with an explanation as to why one should focus on 990 instead of 1000. $\endgroup$ – jmoreno Nov 13 '16 at 7:04
  • $\begingroup$ Think this answer is copied from Project Eulers' answer by Rudy: projecteuler.net/thread=1#209 $\endgroup$ – Eugene Kulabuhov Nov 25 '16 at 21:59
14
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 4
    $\begingroup$ The answer that you have provided is incorrect. Take a look at the accepted answer and see how you can improve your own post. $\endgroup$ – Jeel Shah Jul 11 '13 at 23:59
  • $\begingroup$ Why can't you duplicate the intersections? $\endgroup$ – JohnOsborne Jul 29 '18 at 22:32
8
$\begingroup$

Well the main equation is already given above. The only question which give me trouble is that why I have to subtract the sum of 15?! Well, the answer is, 15 can be evenly divide by both 3 & 5. So the products of 15 can also be divided by those number as well! So, when you adding the numbers with Sum Of Three & Sum Of Five there are some numbers(i.e. 15,30,45,60....) which are available at both SUMMATION. So, you have to subtract at least once from the total sum to get the answer!

Hope this helps someone like me:) !!

|cite|improve this answer
$\endgroup$

protected by Community♦ Mar 19 '14 at 16:05

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.