/code/blog

Code, code and code

Least Common Multiple : What Is the Smallest Number That Is Evenly Divisible by All of the Numbers From 1 to 20

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 number that is evenly divisible by all of the numbers from 1 to 20? Notes This is essentially a requirement to compute the least common multiple for the values 1 through 20. We first need to find the prime factors for each number. For some of the numbers, some of the prime factors occur more than once. eg. for 12, the prime factors are 2 and 3, of which while 3 occurs once, 2 occurs twice. Thus for each number we create a hashmap of the prime factors and the number of occurrences. To do so we define a inc_count(dict_,key) which increments the occurence count of the key in the dictionary. This dictionary for each number is computed once and is referred to as new_factors. We need to ensure that we eventually create yet another dictionary which keeps track of the maximum count for each factor across all the numbers. We define yet another dictionary factors which is used to keep track of the maximum occurences of a given factor across all the new_factor instances. We finally fold the factors dictionary by compute a product of all the factors with each factor being used as many times as it occurs in the factors dictionary. That gives us the least common multiple, which is the solution to the problem. Solution 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

from itertools import chain

# function to take the first value of a generator and ignore the rest
def first(gen):
    try:
        return gen.next()
    except StopIteration :
        return None

# generator to return all the prime factors of a given number
def prime_factors(n):
    while n > 1 :
        ff = first(val for val in chain(
                    xrange(2,int(n**0.5+1.0)),[n]) if n % val == 0)
        yield ff
        n = n / ff

# increment the occurrences value of a key in a dictionary
def inc_count(dict_,key):
    dict_[key] = dict_[key] + 1
    return dict_

# keep track of the maximum occurrences of a key in a dictionary
def set_max_count(dict_,(key,val)):
    if dict_[key] < val :
        dict_[key] = val
    return dict_

# Actual solution
# Initialise a dictionary with all keys with occurrences set to zero
factors = dict((n,0)for n in range(2,21))

# For each number for whom we are computing the least common multiple
for num in range(2,21) :
    # Compute the prime factor occurences dictionary for the number
    new_factors = reduce(
                    inc_count,
                    prime_factors(num),
                    dict((n,0)for n in range(2,21)))
    # Update the tracking dictionary to keep track 
    # of the maximum occurrences of a key (factor)
    factors = reduce(set_max_count, new_factors.items(),factors)

# Generate a product by multiplying all the factors 
number = reduce(
            lambda num,(key,val) : num * (key ** val),
            factors.items(),
            1)
print number

Comments