Euler Problem 1: Multiples of 3 or 5

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
answer <- 0
for (i in 1:999) {
    if (i %% 3 == 0 | i %% 5 == 0) 
        answer <- answer + i
}

# 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))))

These three brute-force solutions all take a bit of time to process, especially when using targets much higher than 999. An analytical solution will significantly reduce the processing time.

Analytical Solution

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 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 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:

\mathrm{sum}_m(n) =  p \frac{1+(p/m)}{2}

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

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

This code on GitHub.

3 thoughts on “Euler Problem 1: Multiples of 3 or 5

  1. Another simple solution is the following one (and when comparing with microbenchmark the fastest):

    sum(sapply(1:999, function(x){
        if(x%%5 == 0) return(x)
        if(x%%3 == 0) return(x)
        else return(0)
    }))
    
    • Thanks Johannes, this is a fast solution but still uses loops.

      The fourth solution in my post takes the same time no matter how long the vector is. Try to solve the problem for 999999 and you will see that it takes the same time no matter how high the number.

      In Big-O notation, solution 1-3 and yours are O(n) . The fourth solution is O(1) .

Feel free to share your thoughts about this article