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:
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.
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,
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
Print | posted on Tuesday, February 19, 2008 1:15 AM