4
$\begingroup$

I just cant figure this question out:

Find the sum of the multiples of $3$ or $5$ under $709$ For example, 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$.

$\endgroup$
4
  • 3
    $\begingroup$ Hint: Add multiples of $3$ and multiples of $5$ and subtract multiples of $15$ since they got added twice. $\endgroup$
    – J. J.
    Aug 21, 2014 at 11:46
  • $\begingroup$ HINT: Find sum of all multiples of 3 below 709. Add to this sum of all multiples of 5 below 709. Finally subtract sum of all multiple of 15 below 709 (this will remove all double counted numbers like 15 which are both multiples of 3 and 5) $\endgroup$
    – Mufasa
    Aug 21, 2014 at 11:46
  • $\begingroup$ If you were just given an answer with no justification then how will you learn? $\endgroup$
    – Mufasa
    Aug 21, 2014 at 11:55
  • 2
    $\begingroup$ You don't need to add the numbers up manually - use the formula for the sum of an arithmetic sequence. $\endgroup$
    – Mufasa
    Aug 21, 2014 at 11:55

4 Answers 4

Reset to default
4
$\begingroup$

There are $\displaystyle\left\lfloor\frac{709}{3}\right\rfloor = 236$ multiples of $3$ below $709$, $\displaystyle\left\lfloor\frac{709}{5}\right\rfloor = 141$ multiples of $5$ below $709$ and $\displaystyle\left\lfloor\frac{709}{15}\right\rfloor = 47$ multiples of $15$ below $709$.

By the inclusion/exclusion principle:

$$\mathop{\sum_{(n|3\ \vee\ n|5)} n}_{ n \leq 709} = \mathop{\sum_{n|3} n}_{ n \leq 709} + \mathop{\sum_{n|5} n}_{ n \leq 709} - \mathop{\sum_{n|15} n}_{ n \leq 709} $$

Note that:

$$\mathop{\sum_{n|3} n}_{ n \leq 709} = 3 + 6 + \cdots + 3·236 = 3(1+2+\cdots + 236) = 3\frac{236·237}{2} = 83898$$

Similarly,

$$\mathop{\sum_{n|5} n}_{ n \leq 709} = 5 + 10 + \cdots + 5·141 = 5(1+2+\cdots + 141) = 5\frac{141·142}{2} = 50055$$

$$\mathop{\sum_{n|15} n}_{ n \leq 709} = 15 + 30 + \cdots + 15·47 = 15(1+2+\cdots + 47) = 15\frac{47·48}{2} = 16920$$

So the total sum is: $83898 + 50055 - 16920 = \boxed{117033}$

$\endgroup$
4
  • $\begingroup$ Three issues: $709$ has to be excluded as the given example $10$ shows, $104148$ is replaced by $10418$ and $709/3 = 236.333\dots$ $\endgroup$
    – gammatester
    Aug 21, 2014 at 12:56
  • $\begingroup$ @gammatester For the first issue, note that in the subscript of the sums it says $3|n$ and $n\leq 709$. That already excludes $709$. For the third issue, note that I'm using the floor function: $\lfloor 709/3\rfloor = 263$. The second one is a typo. I'll edit that. $\endgroup$
    – Darth Geek
    Aug 21, 2014 at 13:00
  • $\begingroup$ No, the value $\lfloor 709/3\rfloor$ is $236$ not $263$ $\endgroup$
    – gammatester
    Aug 21, 2014 at 13:02
  • $\begingroup$ @gammatester LOL, damn dyslexia... Thank you. Edited and corrected. $\endgroup$
    – Darth Geek
    Aug 21, 2014 at 13:09
2
$\begingroup$

Let $n_3 = \lfloor \frac{708}{3}\rfloor, \; n_5 = \lfloor \frac{708}{5}\rfloor, \; n_15 = \lfloor \frac{708}{15}\rfloor.\;$ Then using the hints in the comments your sum $S$ is $$S=3\sum_{k=1}^{n_3}k + 5\sum_{k=1}^{n_5}k-15\sum_{k=1}^{n_{15}}k =3\frac{n_3(n_3+1)}{2}+5\frac{n_5(n_5+1)}{2}-15\frac{n_{15}(n_{15}+1)}{2}$$ $$=3\frac{236\times 237}{2}+5\frac{141\times 142}{2}-15\frac{47\times 48}{2} = 117033 $$ Note added in proof: After Darth Geek's first differing answer, I verified my $S=117033$ with a small program.

$\endgroup$
2
$\begingroup$

If inc/exclusion is unknown then, note $\,3,5\mid n\!+\color{blue}{\!15k}\iff 3,5\mid n,\,$ so the multiples of $\,3,5\,$ have periodicity $15,\,$ so we can split the sum into chunks from each period as follows

$$\begin{eqnarray} \color{blue}{0}+\overbrace{\{0,3,5,6,9,10,12\}}^{\large \rm sum\, =\, \color{#c00}{45}}\\ \color{blue}{15}+\{0,3,5,6,9,10,12\}\\ \color{blue}{30}+\{0,3,5,6,9,10,12\}\\ \cdots\qquad\qquad\\ \color{blue}{15\cdot 46}+\{0,3,5,6,9,10,12\}\\ \underbrace{15\cdot 47}_{\large\color{#0a0}{705}} + \underbrace{15\cdot 47+3}_{\large\color{#0a0}{708}}\qquad\quad\ \ \, \\ \hline \end{eqnarray}\qquad\qquad$$

with total sum $\, =\, \color{blue}{7\cdot 15\, (47\cdot 46/2)} + 47\cdot \color{#c00}{45}\color{#0a0}{ + 705 + 708} = 117033$

$\endgroup$
2
$\begingroup$

Since,

$709(\mod3)= 1$

$709(\mod5)= 4$

$709(\mod15)= 4$

Now, look at these 3 A.P. series and their calculate their sum

$S_3=3+6+9+12\cdots708$. This has 236 terms.

And, $S_5=5+10+15\cdots705$. This has 141 terms.

Also, $S_{15}=15+30+45\cdots705$. This has 47 terms.

Your requested sum will be

$$S=S_3+S_5-S_{15}$$

Since,Multiples of 15 got added twice.(Follow Comments)

It comes out to be $117033$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .