After doing about 50 Project Euler problems in my "native" language (C#) I decided to redo some of the problems I did many years ago in F#, as it's a language I always want to give a go. Judging from the code review meta it seems this is okay to post here: Project Euler Solutions
My question is not about how I'm solving the problem, but about how I'm using F# for my chosen solution. I'm a big fan of short, concise code, but readability should be taken into mind.
Multiples of 3 or 5
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.
let isMultipleOf y x =
x % y = 0
let isMultipleOf3Or5 n =
isMultipleOf 3 n || isMultipleOf 5 n
seq { 1..999 }
|> Seq.filter isMultipleOf3Or5
|> Seq.sum
Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
let fib n =
let rec loop zero one n =
match n with
| 0 -> zero
| 1 -> one
| _ -> loop one (zero + one) (n - 1)
loop 1 2 n
let isEven n =
n % 2 = 0
let isBelow x y =
x >= y
Seq.initInfinite fib
|> Seq.takeWhile (isBelow 4000000)
|> Seq.filter isEven
|> Seq.sum
Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
let isMultipleOf x y =
x % y = 0L
let getFirstFactor n =
{ 2L..n }
|> Seq.filter (isMultipleOf n)
|> Seq.head
let rec getFactors n =
seq {
let factor = getFirstFactor n
yield factor
if n <> factor then yield! getFactors (n / factor)
}
600851475143L |> primefactors |> Seq.max |> int