# Euler Problem 1: Multiples of 3 or 5

November 30, 2016
By

(This article was first published on The Devil is in the Data, and kindly contributed to R-bloggers)

## Euler Problem 1 Definition

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.

## Solution

There are four ways to solve this problem in R.

1. Brute force loop through all numbers from 1 to 999 and test whether they are divisible by 3 or by 5 using the modulus function.
2. Vector arithmetics.
3. Sequences of 3 and 5, excluding duplicates (numbers divisible by 15).
4. Using an arithmetic approach.

By the way, the problem definition on the Project Euler website is not consistent: the title mentions multiples of 3 AND 5, while the description asks for multiples of 3 OR 5.

# Solution 1
for (i in 1:999) {
if (i%%3 == 0 | i%%5 == 0)
}

# Solution 2
sum((1:999)[((1:999)%%3 == 0) | ((1:999)%%5 == 0)])

# Solution 3
sum(unique(c(seq(3, 999, 3), seq(5, 999, 5))))


The sum of an arithmetic progression , where n is the number of elements and a1 and an are the lowest and highest value, is:

$\mathrm{sum}= \frac{n(a_{1} + a_n)}{2}$

The numbers divisible by $n=3$ can be expressed as:

$\mathrm{sum}_3(999)=3+6+9+12+ \ldots +999 = 3*(1+2+3+4+ \ldots +333)$

We can now easily calculate the sum of all divisors by combining the above progression with the formula for arithmetic progressions as expressed in the above code, where m is the divisor and n<\i> the extent of the sequence.

p is the highest number less than n divisible by m. In the case of 5, this number is 995.

$p = n \lfloor (m/n) \rfloor$

Substitution gives:

$m$

# Solution 4
SumDivBy <- function(m, n) {
p <- floor(n/m)*m # Round to multiple of n
return (m*(p/m)*(1+(p/m))/2)
}

answer <- SumDivBy(3, 999) + SumDivBy(5, 999) - SumDivBy(15, 999)


The post Euler Problem 1: Multiples of 3 or 5 appeared first on The Devil is in the Data.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...