Problem 5 - Smallest Multiple

Ella, Sri Lanka - 9 Arches Bridge - April 30th, 2025

\(2,520\) 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?

https://projecteuler.net/problem=5

Development

To start out, we write a simple program to test numbers from 1 to 11, 1 to 12, and so forth to test runtime feasibility.

e.g.

n <- 2520
x1 <- 1
x2 <- 11
while (TRUE) {
  if (all(n %% x1:x2 == 0)) {
    return(n)
  }
  n <- n + 1
}

The runtime begins to become non-trivial at x2 = 19.

We notice that all answers from x2 = {11, 12, .., 18} are multiples of 2520.

Thus, we can increase n incrementally by 2520 instead of incrementally by 1.

R

Answer 1

#' @param n Starting number
#' @param inc increment to increase by
#' @param x1 Lowest factor
#' @param x2 Highest factor
n_x1_to_x2 <- function(n, inc = 1, x1 = 1, x2 = 10) {
  while (TRUE) {
    if (all(n %% x1:x2 == 0)) {
      return(n)
    }
    n <- n + inc
  }
}

tic()
n_x1_to_x2(2520, 2520, 1, 20)
toc()

[1] 232792560
0.052 sec elapsed

Answer 2 - No(Low) Code

We don’t need much code here.

We need to compute the LCM (Least Common Multiple) of 2520 & a number that is the product of 1-20 using prime factorization.

The LCM is the product of the highest power of each prime. Prime factorization of 1-10 do not have higher powers.

Multiple	Prime Factorization
11	11
12	2^2 * 3
13	13
14	2 * 7
15	3 * 5
16	2^4
17	17
18	2 * 3^2
19	19
20	2^2 * 5

\(LCM = 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19\)

2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19

[1] 232792560

Answer 3

LCM & Prime Factorization, just code:

l_pf <- primes::prime_factors(1:20)
l_pf_c <- l_pf |> lapply(table)
p <- unique(unlist(l_pf))
d_lcm <- data.frame(p = p)
l_lcm <- c()
for (p_i in p) {
  i_p <- lapply(l_pf, function(i) i == p_i) |> lapply(sum) |> unlist() |> which.max()
  l_lcm[[as.character(p_i)]] <- l_pf_c[[i_p]][[1]]
}
d_lcm$y <- l_lcm
prod(d_lcm$p ^ unlist(d_lcm$y))

[1] 232792560

Python

Answer 1

import time

def n_x1_to_x2(n: int, inc: int, x1=1, x2=10) -> int:
  x = list(range(x1, x2+1))
  while True:
    if all([n % i == 0 for i in x]):
      return n
    n=n+inc

n = 2520

t0 = time.perf_counter()
print(n_x1_to_x2(n, inc=n, x1=1, x2=20))
t1 = time.perf_counter()
t = t1 - t0
print(f'{t:.3f} sec elapsed')

232792560
0.073 sec elapsed

Answer 2

LCM & Prime Factorization, just code:

def is_prime(n):
  """
  Checks if a number n is prime using trial division up to sqrt(n).
  """
  if n != int(n): return False
  if n <= 1: return False
  if n <= 3: return True
  if n % 2 == 0: return False
  limit = int(n**0.5) + 1
  for i in range(3, limit, 2):
    if n % i == 0: return False
  return True

def prime_factors(n: list) -> dict:
  """
  Returns prime factorization of list of integers
  """
  d = {}
  for i in n:
    if is_prime(i):
      d[i] = [i]
      continue
    j = []
    k = i
    p = [2] + [h for h in range(3, int(i**0.5)+1+1, 2) if is_prime(h)]
    for h in p:
      while k % h == 0:
        j.append(h)
        k /= h
      if k == 1: break
    d[i] = j
  return d

from math import prod
from collections import Counter

p = prime_factors(list(range(1,21)))
counts = {i:Counter(j) for i, j in p.items()}
p_unique = list(set([j for i in list(p.values()) for j in i]))
p_unique.sort()
d = {}
for i in p_unique:
  c = []
  c = [j[i] for k, j in counts.items()]
  d[i] = max(c)
prod([i**j for i, j in d.items()])

232792560