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 [1]:
from six.moves import range
In [2]:
all_divides = lambda m, *numbers: all(m % n == 0 for n in numbers)
In [3]:
all_divides(2520, *range(1, 10))
Out[3]:
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 [4]:
# 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 [5]:
def _lcm_recursive(nums, nums_new):
    if all_equals(nums_new): 
        # return any element 
        # why not the first one
        return nums_new[0]
    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[0]

# comment one out
lcm = lambda *nums: _lcm_recursive(list(nums), list(nums))
lcm = lambda *nums: _lcm_iterative(nums)
In [6]:
lcm(4, 7, 12,  21, 42)
Out[6]:
84
In [7]:
lcm(*range(1, 10+1))
Out[7]:
2520
In [ ]:
lcm(*range(1, 20))

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

Version 3 - Division by Primes

In [8]:
%load_ext autoreload
%autoreload 2
In [9]:
from common.utils import prime_range, reconstruct
In [10]:
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 [11]:
lcm(4, 7, 12,  21, 42)
Out[11]:
84
In [12]:
lcm(*range(1, 11))
Out[12]:
2520
In [13]:
lcm(*range(1, 21))
Out[13]:
232792560

MUCH better.

Version 4 - GCD and the Euclidean algorithm

$$\mathrm{lcd}(a, b) = \frac{a \cdot b}{\mathrm{gcd}(a, b)}$$
In [14]:
# TODO

Comments

Comments powered by Disqus