Euler Problem 5: Smallest Multiple

Euler Problem 5 relates to the divisibility of numbers.

Euler Problem 5

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 positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution

The solution will also be divisible by the number 1 to 10 so we can start at 2520 and increment by 2520. The loop checks whether the number is divisible by the numbers 1 to 20.

# Start as high as possible
i <- 2520
# Check consecutive numbers for divisibility by 1:20
while (sum(i %% (1:20)) != 0) {
    i <- i + 2520 # Increase by smallest number divisible by 1:10
}
answer <- i

This code on GitHub.

2 thoughts on “Euler Problem 5: Smallest Multiple

  1. Here’s an implementation using the Euclidean algorithm.

    gcd = function (x, y) ifelse(x == 0, y, gcd(y %% x, x))
    lcm = function (x, y) x*y/gcd(x,y)
    print(Reduce(lcm, 1:20))
    
    • Very nice work David. I did not think to use an analytical approach. I have never used the Reduce function before – thanks for the lesson.

Feel free to share your thoughts about this article