views:

2650

answers:

8

I read an interesting DailyWTF post today, "Out of All The Possible Answers..." and it interested me enough to dig up the original forum post where it was submitted. This got me thinking how I would solve this interesting problem - the original question is posed on Project Euler as:

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?

To reform this as a programming question, how would you create a function that can find the Least Common Multiple for an arbitrary list of numbers?

I'm incredibly bad with pure math, despite my interest in programming, but I was able to solve this after a little Googling and some experimenting. I'm curious what other approaches SO users might take. If you're so inclined, post some code below, hopefully along with an explanation. Note that while I'm sure libraries exist to compute the GCD and LCM in various languages, I'm more interested in something that displays the logic more directly than calling a library function :-)

I'm most familiar with Python, C, C++, and Perl, but any language you prefer is welcome. Bonus points for explaining the logic for other mathematically-challenged folks out there like myself.

EDIT: After submitting I did find this similar question Least common multiple for 3 or more numbers but it was answered with the same basic code I already figured out and there's no real explanation, so I felt this was different enough to leave open.

A: 

Duplicate?

Alexander Kojevnikov
Yes, I posted that in the summary as a similar question, but the focus of my question was more on seeing different ways to approach the problem, and on explanations of the logic versus just posting a code snippet.
Jay
You can read the explanations here: http://mathworld.wolfram.com/LeastCommonMultiple.html
Alexander Kojevnikov
heh. you did catch the part where I said I'm mathematically challenged, right? That link is a bit above my head for a lot of it, but you should post that as an answer instead of a comment too, so others can see it.
Jay
Warren did that already along with a short explanation. Sorry for 'challenging' you, it wasn't my intent :)
Alexander Kojevnikov
A: 

In expanding on @Alexander's comment, I'd point out that if you can factor the numbers to their primes, remove duplicates, then multiply-out, you'll have your answer.

For example, 1-5 have the prime factors of 2,3,2,2,5. Remove the duplicated '2' from the factor list of the '4', and you have 2,2,3,5. Multiplying those together yields 60, which is your answer.

The Wolfram link provided in the previous comment, http://mathworld.wolfram.com/LeastCommonMultiple.html goes into a much more formal approach, but the short version is above.

Cheers.

warren
Unclear what "remove duplicates" mean. You're removing the '2' from the 2 because it's captured by the factorization of the 4. That's not just semantics. Justice puts it a little better. . .you want to take just the value of the MAX power of each prime. Then, you know lower powers are factors.
Baltimark
@Baltimark - I don't follow at all what you said, sorry .. but what do you mean?
warren
+1  A: 

The LCM of one or more numbers is the product of all of the distinct prime factors in all of the numbers, each prime to the power of the max of all the powers to which that prime appears in the numbers one is taking the LCM of.

Say 900 = 2^3 * 3^2 * 5^2, 26460 = 2^2 * 3^3 * 5^1 * 7^2. The max power of 2 is 3, the max power of 3 is 3, the max power of 5 is 1, the max power of 7 is 2, and the max power of any higher prime is 0. So the LCM is: 264600 = 2^3 * 3^3 * 5^2 * 7^2.

Justice
Thanks for the response, it looks like you and Warren provided the same basic answer. I was hoping people would post samples showing different approaches to solving this in code, it'd be great if you could post an algorithmic approach using this techqnique!
Jay
+3  A: 

This problem is interesting because it doesn't require you to find the LCM of an arbitrary set of numbers, you're given a consecutive range. You can use a variation of the Sieve of Eratosthenes to find the answer.

def RangeLCM(first, last):
    factors = range(first, last+1)
    for i in range(0, len(factors)):
        if factors[i] != 1:
            n = first + i
            for j in range(2*n, last+1, n):
                factors[j-first] = factors[j-first] / factors[i]
    return reduce(lambda a,b: a*b, factors, 1)
Mark Ransom
thanks Mark! this is exactly the kind of interesting reply I had in mind :-)
Jay
that is quite clever - I hadn't thought about it that way :)
warren
A: 

An algorithm in Haskell. This is the language I think in nowadays for algorithmic thinking. This might seem strange, complicated, and uninviting -- welcome to Haskell!

primes :: (Integral a) => [a]
--implementation of primes is to be left for another day.

primeFactors :: (Integral a) => a -> [a]
primeFactors n = go n primes where
    go n ps@(p : pt) =
        if q < 1 then [] else
        if r == 0 then p : go q ps else
        go n pt
        where (q, r) = quotRem n p

multiFactors :: (Integral a) => a -> [(a, Int)]
multiFactors n = [ (head xs, length xs) | xs <- group $ primeFactors $ n ]

multiProduct :: (Integral a) => [(a, Int)] -> a
multiProduct xs = product $ map (uncurry (^)) $ xs

mergeFactorsPairwise [] bs = bs
mergeFactorsPairwise as [] = as
mergeFactorsPairwise a@((an, am) : _) b@((bn, bm) : _) =
    case compare an bn of
        LT -> (head a) : mergeFactorsPairwise (tail a) b
        GT -> (head b) : mergeFactorsPairwise a (tail b)
        EQ -> (an, max am bm) : mergeFactorsPairwise (tail a) (tail b)

wideLCM :: (Integral a) => [a] -> a
wideLCM nums = multiProduct $ foldl mergeFactorsPairwise [] $ map multiFactors $ nums
Justice
I think you've over engineered it
Dan
I already had primeFactors, multiFactors, and multiProduct written for some other purposes (mathematical interest, mostly). The other two functions weren't too bad.
Justice
A: 

Here's my Python stab at it:

#!/usr/bin/env python

from operator import mul

def factor(n):
    factors = {}
    i = 2 
    while i <= n and n != 1:
        while n % i == 0:
            try:
                factors[i] += 1
            except KeyError:
                factors[i] = 1
            n = n / i
        i += 1
    return factors

base = {}
for i in range(2, 2000):
    for f, n in factor(i).items():
        try:
            base[f] = max(base[f], n)
        except KeyError:
            base[f] = n

print reduce(mul, [f**n for f, n in base.items()], 1)

Step one gets the prime factors of a number. Step two builds a hash table of the maximum number of times each factor was seen, then multiplies them all together.

Just Some Guy
+2  A: 

One-liner in Haskell.

wideLCM = foldl lcm 1

This is what I used for my own Project Euler Problem 5.

Justice
+8  A: 

The answer does not require any fancy footwork at all in terms of factoring or prime powers, and most certainly does not require the Sieve of Eratosthenes.

Instead, you should calculate the LCM of a single pair by computing the GCD using Euclid's algorithm (which does NOT require factorization, and in fact is significantly faster):


def lcm(a,b):
    gcd, tmp = a,b
    while tmp != 0:
        gcd,tmp = tmp, gcd % tmp
    return a*b/gcd

then you can find the total LCM my reducing the array using the above lcm() function:


reduce(lcm, range(1,21))
Indeed, that's the same algorithm I ended up with, and also what was provided as the solution to the similar question. Seems to be the general consensus on how to solve this.
Jay