March Madness Entry 2

A bit squeezed on time between work and FUBAR Lab's social and administrative meeting, I decided to do something simple tonight - Project Euler! Some of those problems can get ridiculous, so I chose one I happened to know the answer that I've solved in the past, but didn't have the code laying around.

Note - if you want to solve project Euler yourself, don't cheat and peek at the rest of the post. Take this as a warning - the answer is at the end.


The 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 number that is evenly divisible by all of the numbers from 1 to 20?

 Immediately I realized that I would have to know the LCM of the number pairs between 1 and 20. LCM is a commonly implemented feature in software. The quickest method I knew of off the top of my head:

def lcm(a, b):
    return a*b / gcd(a, b)

Where I used the following for GCD

def gcd(a, b):



    if b == 0: return a
    return gcd(b, a % b)

The rest fell into place:

data = range(1, 20 + 1)

tmp = []

while len(data) > 1:

    print data

    print tmp

    for i in range(0, len(data), 2):

        if len(data)%1 == 0 and i is not 5:

            tmp.append(lcm(data[i], data[i-1]))

        else:

            tmp.append(lcm(data[i+1], data[i]))

    data = tmp

    tmp = []

print data

The returned answer? 5,342,931,457,063,200! Sheesh!