# F# Solution : Project Euler Problems 1-3

__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.

- Share This Post:
- Short Url: http://wblo.gs/V4g

## Feedback

#### # re: F# Solution : Project Euler Problems 1-3

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. :) 2/18/2008 11:01 PM | Erik

#### # 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. 12/14/2009 12:29 PM | Darrell Plank

#### # 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/ 7/2/2010 9:02 AM | Stefano Ricciardi
__T__itle:

__N__ame:

__E__mail: *Not Displayed*

__C__omment:

## # 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]

2/14/2008 9:05 AM | Nate Hoellein