Find the sum of the multiples of $3$ and $5$ below $709$?

Question

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$.

Answer 1

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.

Answer 2

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}$

Answer 3

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$

Answer 4

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$