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
fromitertoolsimportchain# function to take the first value of a generator and ignore the restdeffirst(gen):try:returngen.next()exceptStopIteration:returnNone# generator to return all the prime factors of a given numberdefprime_factors(n):whilen>1:ff=first(valforvalinchain(xrange(2,int(n**0.5+1.0)),[n])ifn%val==0)yieldffn=n/ff# increment the occurrences value of a key in a dictionarydefinc_count(dict_,key):dict_[key]=dict_[key]+1returndict_# keep track of the maximum occurrences of a key in a dictionarydefset_max_count(dict_,(key,val)):ifdict_[key]<val:dict_[key]=valreturndict_# Actual solution# Initialise a dictionary with all keys with occurrences set to zerofactors=dict((n,0)forninrange(2,21))# For each number for whom we are computing the least common multiplefornuminrange(2,21):# Compute the prime factor occurences dictionary for the numbernew_factors=reduce(inc_count,prime_factors(num),dict((n,0)forninrange(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(lambdanum,(key,val):num*(key**val),factors.items(),1)printnumber