Geeks With Blogs
Buhay Programmer Dont byte more than you can chew

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?

Solution:

Finding the LCM can be done via factorization.  Below is an excerpt from the wikipedia article.

The unique factorization theorem says that every positive integer number greater than 1 can be written in only one way as a product of prime numbers. The prime numbers can be considered as the atomic elements which, when combined together, make up a composite number.

For example: $90 = 2^1 \cdot 3^2 \cdot 5^1 = 2 \cdot 9 \cdot 5. \,\!$

Here we have the composite number 90 made up of one atom of the prime number 2, two atoms of the prime number 3 and one atom of the prime number 5.

This knowledge can be used to find the lcm of a set of numbers.

Example: Find the value of lcm(8,9,21).

First, factor out each number and express it as a product of prime number powers. $8\; \, \; \,= 2^3 \cdot 3^0 \cdot 5^0 \cdot 7^0 \,\!$ $9\; \, \; \,= 2^0 \cdot 3^2 \cdot 5^0 \cdot 7^0 \,\!$ $21\; \,= 2^0 \cdot 3^1 \cdot 5^0 \cdot 7^1. \,\!$

The lcm will be the product of multiplying the highest power in each prime factor category together. Out of the 4 prime factor categories 2, 3, 5, and 7, the highest powers from each are 23, 32, 50, and 71. Thus, $\operatorname{lcm}(8,9,21) = 2^3 \cdot 3^2 \cdot 5^0 \cdot 7^1 = 8 \cdot 9 \cdot 1 \cdot 7 = 504. \,\!$

Code:

module Prob5 = begin
open System
open Microsoft.FSharp.Math

let primeFactors (num:float) =
//let num = 50.0
let divSeq = num |> Seq.unfold (fun x ->
let rec get num2  =
let sq = Math.Sqrt (num2)
let div = ref 2.0
while( (not(num2 % !div = 0.0)) && (!div < sq) ) do
if (!div = 2.0) then
div  := !div + 1.0
else
div  := !div + 2.0
div
let sq = Math.Sqrt (x)
let divisor = get x
if (x = 1.0) then
None
else if (sq < !divisor) then
Some (x, 1.0)  // x is prime!
else
Some(!divisor, x/(!divisor))
)
divSeq
let pFactors = (2,20) |> Seq.unfold (fun (x,limit) ->
let y = float_of_int x
let s =  (primeFactors y) |> Seq.map (fun x -> Convert.ToInt32(x))
if x <=limit then
Some ( (x,s), (x+1, limit))
else
None
)

let factorSort x y =
let (num1, _) = x
let (num2,_) = y

if (num1 < num2)  then
-1
else if num1 > num2 then
1
else
0
let powSort x y =
let (_,num1) = x
let (_,num2) = y

if num1 < num2 then
1
else if num1 > num2 then       -1
else
0

let all =   pFactors |> Seq.map (fun (num,s) -> s |>  Seq.countBy (fun x -> x ) )  |> Seq.concat
let allList =  (Seq.to_list all) |> List.sort factorSort |> List.sort powSort

let a = ref 0
let b = ref 0
let filtered = allList |> List.filter (fun (x,y) ->
let (factor,pow) = allList |>  List.find (fun (r,s) -> r=x )

if (factor = x ) && (pow = y) && ( (!a <> x) || (!b <> y) ) then
a := factor
b := pow
true
else
false

)

let main() =
let lcm = filtered |> List.fold_left (fun a (x,y) -> a * Math.Pow(float_of_int x, float_of_int y ) ) 1.0
printfn "\n\nLCM = %f" lcm

end

My solution for this one follows the steps outlined in the wikipedia excerpt above. It is a bit long but essentially it can be broken down into the following stages...

1 - Factor out the number 1 to 20.

This is done on function pFactors.  pFactors outputs a sequenct of tuples wherein the first value is the number being factored while the second value is a sequence of its prime factors. For example, the output of this function when applied to the numbers 2 to 20

{ (2, {2}); (3, {3}; (4, {2;2}) ; (5, {5}) ...,<snip> .. (12, {2;2;3}) ...<snip> .. (20, {2;2;5})       }

type : seq< int * seq<int>>

2 - Count the number of occurrences of each prime factor and consolidate into just one sequence

This is done on line  let all = pFactors |> Seq.map (fun (num,s) -> s |> Seq.countBy (fun x -> x ) ) |> Seq.concat

Seq.countBy counts the number of occurences of an item in a sequence.  For example, if we apply to the sequence of prime factors of the number 20, the output will be

(20, {2;2;5} ) -> (2,2),(5,1) : where the 2nd value of the tuple is the number of occurences

So for the number 2 to 20 the output is

(2, 1)(3, 1)(2, 2)(5, 1)(2, 1)(3, 1)(7, 1)(2, 3)(3, 2)(2, 1)(5, 1)(11, 1)(2, 2)(3, 1)(13, 1)(2, 1)(7, 1)(3, 1)(5, 1)(2, 4)(17, 1)

(2, 1)(3, 2)(19, 1)(2, 2)(5, 1)

type : seq<int * int >

3 - Sort the output of stage 2.

The output of stage 2 obviously contains duplicates.  Referring back to the wikipedia excerpt above, what we need only are those factors with the highest power (or most number of occurences).  So in order for us to identify those factors, first we sort the sequence.  This is done on line

let allList = (Seq.to_list all) |> List.sort factorSort |> List.sort powSort

The output (though a bit confusing) guarantees that the for any number, the one with the highest number of occurences comes out on top.  For example (2,4) is on top of all the other tuple entries with first value of 2. And so is (3,2) for tuple values with first value of 3.

(2, 4)
(2, 3)
(2, 2)
(2, 2)
(2, 2)
(3, 2)
(3, 2)
(2, 1)
(2, 1)
(2, 1)
(2, 1)
(2, 1)
(3, 1)
(3, 1)
(3, 1)
(3, 1)
(5, 1)
(5, 1)
(5, 1)
(5, 1)
(7, 1)
(7, 1)
(11, 1)
(13, 1)
(17, 1)
(19, 1)

type : seq<int * int>

4.  Filter the resulting sequence of stage 3 and take only those with the highest 2nd element.  This is done on line

let filtered = allList |> List.filter (fun (x,y) -> ...  <snip>...

output is :  seq<int*int>

(2, 4)
(3, 2)
(5, 1)
(7, 1)
(11, 1)
(13, 1)
(17, 1)
(19, 1)

5. And finally we can compute the LCM.  This is done on the line

let lcm = filtered |> List.fold_left (fun a (x,y) -> a * Math.Pow(float_of_int x, float_of_int y ) ) 1.0

Total execution time on my machine is 0.17 seconds  which a great improvement from the 25 seconds using the brute force approach described here

Comments on this post: F# Solution (By Factorization) : Project Euler Problems 5

# re: F# Solution (By Factorization) : Project Euler Problems 5 Hi,
great post!

After the brute force approach you cited, I also tried another solution based on the relation between the least common multiple and the greatest common divisor, and it seems to be even faster than your code, taking only 0.015 seconds to execute!

It is presented here: http://www.fsharp.it/2008/02/08/project-euler-in-f-problem-5-alternative-solution/
Left by Claudio on Feb 21, 2008 6:08 PM

# re: F# Solution (By Factorization) : Project Euler Problems 5 Awesome! that's really fast. :)
Left by Erik on Feb 23, 2008 10:56 AM

# re: F# Solution (By Factorization) : Project Euler Problems 5 please send me complete Guide of TECHNICAL MATEMATICS 123 for 1st year Student Of DAE Classes.
Left by waseem iqbal on Apr 29, 2008 12:11 PM

# re: F# Solution (By Factorization) : Project Euler Problems 5 LCM(a,b) = a*b/GCD(a,b)
using euclidean gcd algorithm (repeated mods, very fast) removes need to compute primes.
simply fold lambda(x,y) = x*y/gcd(x,y) across {1,2,3,...20} should be simpler and faster.
Left by rho on Jul 26, 2008 4:54 AM