Problem 5 on the Project Euler list is the following:
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
This is asking us to compute the lowest common multiple (lcm) from 1 to 20. The lcm of two integers a and b is defined as
\[ \frac{ab}{\mbox{gcd}(a,b)} \]
In order to compute the gcd, we can use a simple algorithm, like a Euclidian reduction:
# Iterative Euclidean algorithm
gcd <- function(a,b) {
t <- 0
while (b != 0) {
t <- b
b <- a %% b
a <- t
}
a
}
Defining the lcm then becomes:
lcm <- function(a,b) {
abs(a * (b/(gcd(a,b))))
}
Now we have defined pretty much everything we need to solve the problem. We can write an iterative lcm routine that calculates the least common denominator from 1 to x:
lcm_ <- function(xs) {
l <- 1
for (i in 1:(length(xs))) {
l <- lcm(l,xs[i])
}
l
}
And we can calculate the answer:
> lcm_(c(1:20))
[1] 232792560
However, I also experimented with writing a reduce() function (similar to Haskell’s foldr operation). We can write reduce() as follows:
reduce <- function(op,x,xs) {
y <- x
for (i in 1:(length(xs)-1)) {
y <- do.call(op, list(y, xs[i]))
}
y
}
And then invoke:
>reduce(lcm, 1, c(1:20))
[1] 232792560
Note that R actually has inbuilt Map/Reduce operations. Using the native Reduce, this is:
> Reduce(f=lcm, x=c(1:20), right=1)
[1] 232792560