# Project Euler Problem 5

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

Leave a Comment