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 |
Unless there was a strong requirement that this code needed to be the most efficient possible, I would go for readability and conciseness of the code as follows :
2
3
4
5
6
7
8
9
return a if b==0 else gcd(b, a%b)
def lcm(a,b):
return a*b/gcd(a,b)
print reduce(lcm, range(2,21))
# Note: this code can go upto 10000 without requiring
# more than a fraction of a second to compute
Ahh Euclid’s GCD algorithm, i remember seeing this code snippet in my first year engg and being completely mesmerized by its beauty and elegance. At that time, I didnt know that Euclid was behind this algo, I thought that the guy who passed on his notes had written it and I was demoralized because I was sure I would never come up with something like this in my whole life, leave alone the 15 to 20 minutes that I could spend on it in the exam. End result: I gave up on the course and secured an impressive 14/100 in my exams
Going back to the code, sorry for nitpicking, but in the lcm code,
return a/gcd(a,b) * b is more efficient. For the current example, it wont make much of a difference, but when a and b are really large and have to be encapsulated as BigIntegers, my personal experience has shown that it definitely makes a difference.
Abhay,
In this case the impact of a/gcd(a,b)*b was perceptible but not substantial (about 2%). Thats probably because the lcm() function gets used far less often than gcd()
Navin,
I completely agree with you on the readability argument especially if performance is not particularly critical.
However as a complete side note to your comment, there is an interesting angle on the performance front here. The algorithm you document degrades very rapidly as the numbers become bigger (most likely due to the fact that the number of invocations of gcd increase much more). Thus range(2,10K) takes about 0.2 seconds vs. range(90K,100K) (both have the same count of values to compute lcm for) takes about 0.9 seconds and range(2,100K) takes about 56 seconds. On the other hand the rather verbose logic takes about 2.65 seconds for range(2,1M) and avoids degradation both for larger ranges of numbers and larger values of the numbers themselves.
I think there will be another “twist” in the story for the verbose logic as the numbers get really large starting from over 10 billion. The prime factor code will get quite slow.
Am taking a different line of thought about the verbose logic code for really LARGE numbers, am not claiming correctness of the algorithm. You are finding prime factors for “every” number in the sequence and storing the max prime power. Only one number could be factorized. Consider the following:
1) Find the max number in the sequence. Lets call is max_seq
2) Find prime factors till sqrt (max_seq). This list can be generated before hand.
3) Find max power of each prime in the number. This is equivalent to
prime^max_power <= max_seq
You can use log functions to compute max_power, take the floor of the computed decimal and store it
4) For the sequence, check if the numbers are divisible by the prime powers. You dont have to divide each number, but you can take the product of the prime numbers in chunks of say 20 numbers and check if the GCD (number, chunk) != 1. That will speed things using Euclid's algo.
5) For every sequence number for which the modulus is 0, you can multiply the prime raised to max_prime_power and thus compute the LCM
6) A potential pitfall here is that the sequence itself could contain a prime which wont be covered under sqrt(max_sequence). We could run the AKS primality test over the sequence, find the prime numbers and multiply them to initialize the LCM variable.
I’ve always wondered why people code the theorem like Navin did above.
Doesn’t this require one less iteration?
2
3
4
5
if (a%b==0)
return a
else
return gcd(b,a%b)
The LCM from 1-20 is 232,792,560
Yes. Indeed, thats the same answer you will get if you run the code I wrote.
Look: 232,792,560 divided by 19 = 12,252,240
12,252,240 divided by 17 = 720,720
720,720 divided by 13 = 55,440
55,440 divided by 11 = 5,040
5,040 divided by 7 = 720
720 divided by 6 = 120
120 divided by 4 = 30
30 divided by 3 = 10
10 divided by 10 = 1
So: Essantialy 3x4x6x7x10x11x13x17x19 = The LCM of numbers 1-20
Here: Take a closer look:
232,792,560 divided by 1 = 232,792,560
232,792,560 divided by 2 = 116,396,280
232,792,560 divided by 3 = 77,567,520
232,792,560 divided by 4 = 58,198,140
232,792,560 divided by 5 = 46,558,512
232,792,560 divided by 6 = 38,798,760
232,792,560 divided by 7 = 33,256,080
232,792,560 divided by 8 = 29,099,070
232,792,560 divided by 9 = 25,865,840
232,792,560 divided by 10 = 23,279,256
232,792,560 divided by 11 = 21,162,960
232,792,560 divided by 12 = 19,399,380
232,792,560 divided by 13 = 17,907,120
232,792,560 divided by 14 = 16,628,040
232,792,560 divided by 15 = 15,519,504
232,792,560 divided by 16 = 14,549,535
232,792,560 divided by 17 = 13,693,680
232,792,560 divided by 18 = 12,932,920
232,792,560 divided by 19 = 12,252,240
232,792,560 divided by 20 = 11,639,628
Haha! I’m right!!!
I’m sorry if it looks like I’m copying Julian, but at first I had written Julian as a fake name and then decided; What the heck, I’ll just put my real name and erase Julian’s comments! I can’t do that.
Sorry, again!
3×4×6×7×10×11×13×15×17×19x23x29 = 2,329,089,562,800
——————————-OR——————————-
232,972,560 x 3 x 5 x 23 x 29 = 2,329,089,562,800
(LCM of 1-20)__________________(LCM of 1-30)
Mathew,
I have already indicated in a comment earlier that your answer is correct.
Dhananjay