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



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.

Search R-bloggers


Sponsors

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)