Project Euler 5: Smallest Multiple

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?

The solution will also be divisible by the numbers 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.

ProjectEuler

  ## Project Euler 5: Smallest Multiple

  answer <- 2520
  while (sum(answer %% (1:20)) != 0) {
      answer <- answer + 2520 # Increase by smallest number divisible by 1:10
  }
  print(answer)

David Radcliffe provided a more generalised way to derive the answer. To solve this problem, we need the Least Common Denominator, which is the smallest number that two or more numbers will divide into evenly. To find the LCD, we first need to know the Greatest Common Divisor \(gcd(x, y)\). The Lowest Common Denominator is the product two numbers, divided by the \(gcd\).

The first function calculates the Greatest Common Divisor of tho numbers, \(gcd(x, y)\), using the Euclidean Algorithm in a recursive function. The second function derives the \(lcm\).

The Reduce() function takes a function, and a list of data items and recursively applies the function to the elements of the list. Reduce performs the function in the first parameter over the first two elements, then over that result and the third element, and so on. A nice way to see what Reduce() does is to use accumulate = TRUE. This option returns its state after processing the elements of the list.

This solution thus finds the Lowest Common Denominator for the numbers 1 to 20.

  ## Generalised method 

  gcd = function (x, y) ifelse(x == 0, y, gcd(y %% x, x))
  lcm = function (x, y) x * y / gcd(x, y)
  Reduce(lcm, 1:20)
  Reduce(lcm, 1:20, accumulate = TRUE)

As seen on R Bloggers