# Project Euler Problem 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?

In :
from six.moves import range

In :
all_divides = lambda m, *numbers: all(m % n == 0 for n in numbers)

In :
all_divides(2520, *range(1, 10))

Out:
True

The least common multiple of the numbers 1 to 10 is 2520. We are asked to find that of the numbers 1 to 20.

#### Version 1 - Integer Factorization¶

We already implemented lcm in problem 3, and the easiest way would be for us to simply use that. However, as we mentioned, it is not very efficient. Let's instead look at other ways of implementing it.

#### Version 2 - Simple algorithm¶

Given a list of $n$ integers $X = (x_1, x_2, \dotsc, x_n)$, we can find the least common multiple of the integers in $X$ by the following:

Let $X^{(0)} = (x_1^{(0)}, x_2^{(0)}, \dotsc, x_n^{(0)}) = (x_1, x_2, \dotsc, x_n) = X$ and $X^{(m+1)} = (x_1^{(m+1)}, x_2^{(m+1)}, \dotsc, x_n^{(m+1)})$ where

$$x_k^{(m+1)} = x_k^{(m)} + \begin{cases} x_k^{(0)} & \text{if } \min(X^{(m)}) = x_k^{(m)} \\ 0 & \text{otherwise} \end{cases}$$

Once all $X$ are equal, in every entry is the LCM.

In :
# First we need a predicate to test
# if all elements of a list are equal
# There are a number of ways to do this
pairs = lambda lst: zip(lst[1:], lst[:-1])
all_equals = lambda lst: all(x == y for x, y in pairs)
all_equals = lambda lst: lst[1:] == lst[:-1]
all_equals = lambda lst: len(set(lst)) < 2

# We'll also need argmin. Note that NumPy
# comes bundled with all of these, but
# they're trivial, why not implement them ourselves!
argmin = lambda lst: lst.index(min(lst))

In :
def _lcm_recursive(nums, nums_new):
if all_equals(nums_new):
# return any element
# why not the first one
return nums_new
k = argmin(nums_new)
nums_new[k] += nums[k]
return _lcm(nums, nums_new)

def _lcm_iterative(nums):
nums_new = list(nums) # remember to use list for deep copy
while not all_equals(nums_new):
k = argmin(nums_new)
nums_new[k] += nums[k]
return nums_new

# comment one out
lcm = lambda *nums: _lcm_recursive(list(nums), list(nums))
lcm = lambda *nums: _lcm_iterative(nums)

In :
lcm(4, 7, 12,  21, 42)

Out:
84
In :
lcm(*range(1, 10+1))

Out:
2520
In [ ]:
lcm(*range(1, 20))


This is way too slow! Let's try something else!

#### Version 3 - Division by Primes¶

In :
%load_ext autoreload

In :
from common.utils import prime_range, reconstruct

In :
from collections import defaultdict, Counter

def _lcm_prime_divisors(nums):
divides_count = Counter()
for p in prime_range(max(nums)+1):
for n in nums:
tmp = 0
while n % p == 0:
tmp += 1
n /= p
if tmp > divides_count[p]:
divides_count[p] = tmp
return reconstruct(divides_count)

lcm = lambda *nums: _lcm_prime_divisors(nums)

In :
lcm(4, 7, 12,  21, 42)

Out:
84
In :
lcm(*range(1, 11))

Out:
2520
In :
lcm(*range(1, 21))

Out:
232792560

MUCH better.

#### Version 4 - GCD and the Euclidean algorithm¶

$$\mathrm{lcd}(a, b) = \frac{a \cdot b}{\mathrm{gcd}(a, b)}$$

In :
# TODO