Problem
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?
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?
Solution:
Let X be a set of integers.
|X| = N and xi is element of X where i is an element of the set {1,2, ... ,N} . Then,
LCM(x1,x2,.....,xN) = LCM(LCM(x1,x2,.....,xN-1),xN) and
LCM(x,y) = (x*y)/GCD(x,y) where x,y are any positive integer
LCM stands for Lowest Common Multiple. and GCD stands Greatest Common Divisor.Calculating GCD is a very efficient algorithm given by the great Euclid. It is called the grand daddy of all algorithm. The oldest algorithm that exists today and still play a great role in computer science.
Detail Work Out:
Let, X = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
(Read the black font from top to bottom, and blue font from bottom to top)
LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14,15,16,17,18,19),20)
LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14,15,16,17,18),19)
LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14,15,16,17),18)
LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14,15,16),17)
LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14,15),16)
LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14),15)
LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13),14)
LCM(1,2,3,4,5,6,7,8,9,10,11,12,13) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12),13)
LCM(1,2,3,4,5,6,7,8,9,10,11,12) = LCM(LCM(1,2,3,4,5,6,7,8,9,10,11),12)
LCM(1,2,3,4,5,6,7,8,9,10,11) = LCM(LCM(1,2,3,4,5,6,7,8,9,10),11)
LCM(1,2,3,4,5,6,7,8,9,10) = LCM(LCM(1,2,3,4,5,6,7,8,9),10)
LCM(1,2,3,4,5,6,7,8,9) = LCM(LCM(1,2,3,4,5,6,7,8),9)
LCM(1,2,3,4,5,6,7,8) = LCM(LCM(1,2,3,4,5,6,7),8)
LCM(1,2,3,4,5,6,7) = LCM(LCM(1,2,3,4,5,6),7)
LCM(1,2,3,4,5,6) = LCM(LCM(1,2,3,4,5),6)
LCM(1,2,3,4,5,6) = LCM(60,6) = (60*6)/GCD(60,6) = 60
LCM(1,2,3,4,5) = LCM(LCM(1,2,3,4),5)
LCM(1,2,3,4,5) = LCM(12,5) = (12*5)/GCD(12,5) = 60
LCM(1,2,3,4) = LCM(LCM(1,2,3),4)
LCM(1,2,3,4) = LCM(6,4) = (6*4)/GCD(6,4) = 12
LCM(1,2,3) = LCM(LCM(1,2),3)
LCM(1,2,3) = LCM(2,3) = (2*3)/GCD(2,3) = 6
Now we know,
LCM(1,2) = (1*2)/GCD(1,2) = 2/1 = 2
So, now we calculate the whole thing backwards. (As like it is done in recursion in programming). It takes N-1 steps.
