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.

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

# re: F# Solution : Project Euler Problems 1-3 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 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 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