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

Posted on Tuesday, February 19, 2008 1:15 AM | Back to top


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

# re: F# Solution (By Factorization) : Project Euler Problems 5
Requesting Gravatar...
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
Requesting Gravatar...
Awesome! that's really fast. :)
Left by Erik on Feb 23, 2008 10:56 AM

# re: F# Solution (By Factorization) : Project Euler Problems 5
Requesting Gravatar...
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
Requesting Gravatar...
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

Your comment:
 (will show your gravatar)
 


Copyright © Erik Araojo | Powered by: GeeksWithBlogs.net | Join free