Categories
Coding Project Euler R

Project Euler Problem #1 (R)

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_1n\), 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]