Category: Project Euler

Here is a solution for Project Euler’s problem #1 in R. The problem is expressed as:

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.

As usual with Project Euler questions, there is an obvious way, and a less obvious, but much more efficient way. In this case, the obvious way is:

[code lang=”R”]
x < – seq(1,999)
sum(x[x %% 3 ==0 | x %% 5 == 0])
[/code]

Which very concisely returns the correct answer, 233168. However, if we use the following intuition:

$$S_N=S_3+S_5–(S_{3,5})$$

i.e. the sum of all numbers divisible by 3 or 5 is the sum of all numbers divisible by 3, plus the sum of all numbers divisible by 5, minus the sum of all numbers divisible by 3 and 5 (as we have double counted them), then we get the correct answer.

Since $$S_n=\frac{n(a_1+a_n)}{2}$$, where $n=\lfloor \frac{N}{n}\rfloor$, and $a_n=a_{1}n$, the last piece of the puzzle is what to use for $S_{3,5}$. This is straightforward, we just use the lowest common multiple of 3 and 5, which in this case is 15. Hence, the R representation of this is:

[code lang=”R”]sum(333*((3+333*3)/2),199*((5+199*5)/2)-66*((15+66*15)/2))[/code]