Problem 5: smallest multiple

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?

Understanding the problem

The approach will be the following:

Create a list of all the factors of the numbers from 1 to 20
Obtain all the different factors. Get the equal factors with the greatest exponent
Multiply the factors: this is the solution

Functions for obtaining all the factors of a number



In [57]:

    
def factor(N):
    for i in range(2,N):
        if (N % i == 0):
            return i
    return 0

def decompose(N):
    f = factor(N)
    lf = []
    while f > 0:
        lf.append(f)
        N = N / f
        #print("Factor: {}, Rest: {}".format(f, N)) #-- Debuging
        f = factor(N)
    lf.append(N)
    
    #-- Create a dictionary with the factors and exponents
    d = {}
    for f in lf:
        try:
            d[f] += 1
        except:
            d[f] = 1
            
    return d

Checking the function



In [58]:

    
for i in range(2,21):
  print("{}: {}".format(i, decompose(i)))









    



2: {2: 1}
3: {3: 1}
4: {2: 2}
5: {5: 1}
6: {2: 1, 3: 1}
7: {7: 1}
8: {2: 3}
9: {3: 2}
10: {2: 1, 5: 1}
11: {11: 1}
12: {2: 2, 3: 1}
13: {13: 1}
14: {2: 1, 7: 1}
15: {3: 1, 5: 1}
16: {2: 4}
17: {17: 1}
18: {2: 1, 3: 2}
19: {19: 1}
20: {2: 2, 5: 1}

Now all the factors should be included in a new dictionary following the criteria of including the ones with the maximum exponent or factors that are not already there



In [76]:

    
df = {}
for i in range(2,21):
    d = decompose(i)
    for f in d.keys():
        try:
            df[f] = max(df[f], d[f])
        except:
            df[f] = 1

Finally, al the factors should be multiplied between them to obtaing the solution



In [77]:

    
n = 1
for f in df.keys():
    n = n * (f ** df[f])



In [78]:

    
print("The solution is: {}".format(n))









    



The solution is: 232792560



In [ ]: