Project Euler Problem 5: Smallest Multiple

The source code for this problem can be found here.

Problem Statement

\(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 Discussion

\(2520\) is the smallest multiple of all numbers \(1\) through \(10\), which means that any multiple of \(2520\) is also divisible by \(1\) through \(10\). Any non-multiple will not be divisible by ALL numbers \(1\) through \(10\), so can be ignored.

Divisibility by the numbers \(11\) through \(20\) should be tested from highest (\(20\)) to lowest (\(11\)) since higher divisors will rule more candidates out by in-divisibility. More explicitly, \(19\) out of every \(20\) integers are not divisible by \(20\) whereas only \(18\) out of every \(19\) integers are not divisible by \(19\). This is akin to lazy boolean logic evaluation and avoids redundant computation.

Using these insights, a simple search strategy will find the answer very quickly. More specifically, search through increasing multiples of \(2520\) testing for divisibility by \(20,19,\dots,11\) - in that order. Identify the first, and thus smallest such number.

Solution Implementation

from typing import List


def is_multiple(n: int, divisors: List[int]) -> bool:
    """ Check whether :math:`n` is divisible by all of the given :math:`divisors`

    :param n: the integer to check for divisibility
    :param divisors: the divisors to test :math:`n` with
    :return: whether :math:`n` is divisible by all :math:`divisors` or not
    """

    for m in divisors:
        if n % m != 0:
            return False
    return True


def solve():
    """ Compute the answer to Project Euler's problem #5 """
    divisors = [20, 19, 18, 17, 16, 15, 14, 13, 12, 11]  # reverse order
    n = 2520  # start our search at 2520
    while not is_multiple(n, divisors):
        n += 2520  # increment our search by 2520 at a time
    return n


expected_answer = 232792560
solutions.problem5.is_multiple(n, divisors)

Check whether \(n\) is divisible by all of the given \(divisors\)

Parameters:
  • n (int) – the integer to check for divisibility
  • divisors (List[int]) – the divisors to test \(n\) with
Return type:

bool
Returns:

whether \(n\) is divisible by all \(divisors\) or not
solutions.problem5.solve()

Compute the answer to Project Euler’s problem #5