0x0005 - Project Euler 005

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?

Solution:

1. Brute-Force Approach:

def is_divisible_20(n) :
    for i in range(2, 20) :
        if n%i != 0: return False
    return True

i = 20
while True:
    if is_divisible_20(i) :
        print i
        break
    i += 20

2. Efficient Approach:

def gcd(a, b) :
    if a == 0: return b
    if b == 0: return a
    if a < 0:  a = -a
    if b < 0:  b = -b

    while b != 0:
        a, b = b, a%b
    return a

result = 2
for i in range(2,21) :
    result = i / gcd(result,i) * result
print result

Analysis:

The brute-force approach to solve this problem would be to check a number’s divisibility from 2 to 20 (as all numbers are divisible by 1). We can start with the initial value of the number as 20 and then incrementing it by 20. In other words, we check for divisibility of numbers 20, 40, 60, 80, …. There is no point checking for numbers other than these as they would not be divisible by the largest number, 20.

For this, we create a function is_divisible_20() to which a number n is passed as argument. The result returned is a Boolean value (True or False). For determining this, we check if n is evenly divisible by all numbers from 2 to 20. As soon as it is found that the remainder (n % i) is not zero, a False is returned.

This function is called from within a while loop. Initially, we have a variable i with a value 20 and we check if is_divisible_20(i) returns True. If it does, the value of i is printed and we break out from the loop. If the result is false, i is incremented by 20 and the above process continues.

The second method is much more efficient that the brute force approach. In this method, a function for the Greatest Common Divisor, gcd(a, b) is created. If a has a value 0, b is returned as the GCD. If b has a value 0, a is returned as the GCD. Next, we convert a and b to their absolute values. However, instead of calling the built-in abs() function, we manually calculate the absolute values. This saves the time for the function call twice. After these steps, we find the GCD by the Euclidean Algorithm, which is in the form of a while loop. This method of calculating GCD is efficient in terms of both time and space complexity as there are neither any external function calls, nor any recursive function calls (thus saving Stack space).

Now, since all numbers are divisible by 1, we start with an initial value 2 for the variable result. The final value of result will give the required answer. The logic used here is a simple one. Suppose we need to find the smallest positive number evenly divisible by 1, 2 and 3. Clearly, the answer is the Least Common Multiple of 1, 2 and 3, i.e. the LCM of 2 and 3, which is 6. Similarly for numbers 1,2,3 and 4, the answer is the LCM of 2,3 and 4. This is equivalent to finding the LCM of 2 and 3, which is 6, and then the LCM of 4 and 6.

Therefore, LCM(1, 2, 3, 4) = LCM(2, 3, 4) = LCM ( LCM(2, 3), 4 ). = LCM (6, 4) = 12. This means that 12 is the smallest number which is evenly divisible by all numbers from 1 to 4.

Also, LCM(1, 2, 3, 4, 5) = LCM(2, 3, 4, 5) = LCM ( LCM(2, 3), 4, 5 ) = LCM ( LCM ( LCM(2, 3), 4 ) , 5) = LCM ( LCM (6, 4), 5) = LCM (12, 5) = 60. This means that 60 is the smallest number which is evenly divisible by all numbers from 1 to 5.

And so on. Also, we have a property that GCD(a, b) x LCM(a, b) = a x b. So the LCM can be calculated as LCM = a x b / GCD(a, b). As this can simply be substituted in the code instead of creating a separate function for it, thus eliminating the time for function calls.

If you notice the implementation of LCM in the code, you’ll see that the LCM is calculated as LCM = a / GCD(a, b) x b(division precedes multiplication). This reduces the size of one input for both the division and the multiplication, and reduces the required storage needed for intermediate results (overflow in the ax b computation). Because GCD(a, b) is a divisor of both a and b, and thus the division will be guaranteed to yield an integer, so the intermediate result can be stored in an integer.

Thus, in the program, we calculate the LCM of all number form 2 to 21. This is explained in the two examples shown above for 1…4 and 1…5. The same logic is implemented using a while loop. In the first pass, LCM(2, 2) = 2 is calculated. Then, in the next passes, LCM(2, 3) = 6, LCM(6, 4) = 12, LCM(12, 5) = 60, LCM(60, 6) = 60…. Finally, at the end of the loop, the smallest positive number evenly divisible by all numbers from 1 to 20 is stored in the variable result, and is printed.

Running times:

Using Python 2.7, under Ubuntu 10.10 terminal:

Brute-force approach: 12.688 seconds

Efficient approach: 44.107 microseconds, which is about 0.000347 percent of the time. In other words, this approach is more than 287664 times fast!