Monday, February 11, 2008 11:58 PM
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.