# 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


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 bool whether $$n$$ is divisible by all $$divisors$$ or not
solutions.problem5.solve()