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

Problem 1 : 

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Solution :

let mySeqP1 = [ 1 .. 999 ] |> Seq.filter (fun x -> ( (x % 5 = 0) || (x % 3 = 0)) ) |> Seq.fold(+) 0
printfn "sum = %i" mySeqP1

Problem 2:

 Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed one million.

Solution :

let sumofEven =   (1,1) |> Seq.unfold (fun (x,y) ->
     match y with
     | y when y < 0 -> None
     | _ -> Some(y, (y, x+y)))
     |> Seq.filter ( fun x ->      x > 0 && x < 1000000 && (x % 2 = 0))
     |> Seq.fold (+) 0

   printfn "Sum of even = %i" sumofEven

 

For this solution I had to put the guard statement "when y <  0" so that negative numbers won't be included in the generated sequence.  If that guard istatement s not there, negative numbers will be included when it goes over the maximum value of Int32.

 Problem 3:

 Find the largest prime factor of 317584931803.

Solution:

let primefactorsOf (num:float)=
    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 (Int32.of_float(x) = 1) then
         None
      else if (Int32.of_float( sq ) < Int32.of_float( !divisor )) then
        Some ( Int32.of_float( x ) , 1.0)  // x is prime!
      else
        Some(Int32.of_float !divisor, x/(!divisor))
      )
      
    divSeq
    
  let primefactors =  (primefactorsOf 317584931803.0)   
  
  let mainp3() = 
    primefactors |> Seq.iter (fun x -> printfn "%i " x)

 

The function "primefactorsOf" takes a number and returns a sequence containing the prime factors of that number.  The prime factors are determined using Trial Division.  This of course is not very fast for ver large numbers but is sufficient enough for 317584931803.0 If it's not clear why the square root of the number being factored out was used instead of directly using the number itself, the wikipedia article explaining Trial Division is here

If you want to output only the largest primefactor you can just pass the value primefactors to Seq.fold like so

let largestFactor = primefactors |> Seq.fold (fun a x -> if x > a then x else a ) 0

Next time I'll post my solution to problems 4-6.

Posted on Monday, February 11, 2008 11:58 PM | Back to top


Comments on this post: F# Solution : Project Euler Problems 1-3

# re: F# Solution : Project Euler Problems 1-3
Requesting Gravatar...
Hi Erik - I too am working my way through the Euler problems in F#, I like your solutions! I'm curious as to why you chose sequences over a list for the first problem? I solved the first problem with a list like so:

let answer = List.fold1_left (+) [ for x in 1 .. 999 when x % 3 = 0 || x % 5 = 0 -> x]

Left by Nate Hoellein on Feb 14, 2008 9:05 AM

# re: F# Solution : Project Euler Problems 1-3
Requesting Gravatar...
Hi Nate,

Thanks!

Coming from C#, I'm trying to get the hang of "Lazy evaluatiion" which is why I almost always use Seq. Unfortunately I had a typo in my solution problem. It would have been much clearer that I'm using seqences if [ 1 .. 99 ] is { 1 .. 99 }.

Than you for posting your solution. I like it. It's a lot shorter. :)
Left by Erik on Feb 18, 2008 11:01 PM

# re: F# Solution : Project Euler Problems 1-3
Requesting Gravatar...
It's a little weird to me that your solution to #2 works. I tested it and it does, but the part that puzzles me is the filter. In general, a filter doesn't "stop" the evaluation of a sequence - it just keeps taking and filtering to the end of the sequence. Oh, I think I see now - it's not actually an infinite sequence - it stops when it overflows and Y<0. Otherwise, I think you'd have an infinite loop. Allowing yourself to loop until you overflow and then relying on your check to keep stuff under 1M seems a bit wasteful. Might I suggest:

let sumofEven =
Seq.unfold (fun (x,y) ->
match y with
| y when y > 1000000 -> None
| _ -> Some(y, (y, x+y))) (1,1)
|> Seq.filter ( fun x -> (x % 2 = 0))
|> Seq.sum

which gives the same answer and stops when Y reaches 1M.
Left by Darrell Plank on Dec 14, 2009 12:29 PM

# re: F# Solution : Project Euler Problems 1-3
Requesting Gravatar...
I have also played with this problem recently. Here' my solution: http://stefanoricciardi.com/2010/07/01/project-euler-problem-3-in-f/
Left by Stefano Ricciardi on Jul 02, 2010 9:02 AM

Your comment:
 (will show your gravatar)


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