<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 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?
Step1:  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
Step2:  This is way too slow! Let's try something else!
Version 3 - Division by Primes
Step3:  MUCH better.
Version 4 - GCD and the Euclidean algorithm
$$\mathrm{lcd}(a, b) = \frac{a \cdot b}{\mathrm{gcd}(a, b)}$$
<ASSISTANT_TASK:>
Python Code:
from six.moves import range
all_divides = lambda m, *numbers: all(m % n == 0 for n in numbers)
all_divides(2520, *range(1, 10))
Explanation: 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?
End of explanation
# 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))
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)
lcm(4, 7, 12,  21, 42)
lcm(*range(1, 10+1))
lcm(*range(1, 20))
Explanation: 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.
<!-- TEASER_END -->
End of explanation
%load_ext autoreload
%autoreload 2
from common.utils import prime_range, reconstruct
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)
lcm(4, 7, 12,  21, 42)
lcm(*range(1, 11))
lcm(*range(1, 21))
Explanation: This is way too slow! Let's try something else!
Version 3 - Division by Primes
End of explanation
# TODO
Explanation: MUCH better.
Version 4 - GCD and the Euclidean algorithm
$$\mathrm{lcd}(a, b) = \frac{a \cdot b}{\mathrm{gcd}(a, b)}$$
End of explanation
<END_TASK>