Skip to content

Project Euler Problem 5

October 8, 2011

Project Euler Problem 5 extends the notion of a least common multiple, or lcm of two numbers to a least common multiple of a sequence:

lcm of three numbers would be lcm(a,b,c) = lcm(lcm(a,b), c)
– …
– if lcm of sequence of n items is lcm(s(n)), then lcm(s(n+1)) = lcm(lcm(s(n)), n+1)

Now, lcm of two numbers and gcd (greatest common divisor) of the same numbers are fulfill the following:

lcm (n,m) = (n * m) / gcd(n,m)

Finally gcd(n,m) can be easily found using Euclidean algorithm.

// gcd - greatest common divisor; Euclidean algorithm:
let rec gcd n m =
    match m with
    | 0L -> n
    | _ -> gcd m (n % m)

// lcm - least common multiple
let lcm n m = n * m / gcd n m

let problem005 () =
    seq [1L .. 20L] |> Seq.reduce lcm
Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: