Euler Problem 1: Multiples of 3 or 5

[This article was first published on The Devil is in the Data, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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

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.

To leave a comment for the author, please follow the link and comment on their blog: The Devil is in the Data.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)