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]:
The least common multiple of the numbers 1 to 10 is 2520. We are asked to find that of the numbers 1 to 20.
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.
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]:
In [7]:
lcm(*range(1, 10+1))
Out[7]:
In [ ]:
lcm(*range(1, 20))
This is way too slow! Let's try something else!
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]:
In [12]:
lcm(*range(1, 11))
Out[12]:
In [13]:
lcm(*range(1, 21))
Out[13]:
MUCH better.
In [14]:
# TODO