Project Euler by F#

ProjectEuler.fs

// ----------------------------------------------------------------------------------------------------------
//      Problem 1 「3と5の倍数」
// -------------------------------
//
// 10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.
// 同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.
//
// ----------------------------------------------------------------------------------------------------------

// 通常の解答 / O(N)
let isMulOf5or3 x = x % 3 = 0 || x % 5 = 0
seq { for i in 1..(1000-1) do 
          if isMulOf5or3 i then yield i }
|> Seq.sum
|> printfn "Problem1 ans= %d"

// 包摂原則を利用した場合の回答例 / O(1)
// |> https://en.wikipedia.org/wiki/Project_Euler
let sum n k = k*((n/k)*((n/k)+1))/2
let sum' = sum (1000-1)
(sum' 3) + (sum' 5) - (sum' (3*5))
|> printfn "Problem1 ans'= %d"



// ----------------------------------------------------------------------------------------------------------
//      Problem 2 「偶数のフィボナッチ数」
// -----------------------------------------
//
// フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.
//              1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
//
// 数列の項の値が400万以下の, 偶数値の項の総和を求めよ.
//
// ----------------------------------------------------------------------------------------------------------

// フィボナッチ数
// |> https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0
let fib = 
    let rec gen a b = seq { yield a; yield! gen b (a + b); }
    gen 0I 1I

fib
|> Seq.takeWhile (fun i -> i <= 4_000_000I)
|> Seq.filter (fun i -> i % 2I = 0I)
|> Seq.sum
|> printfn "Problem2 ans= %A"



// ----------------------------------------------------------------------------------------------------------
//      Problem 3 「最大の素因数」
// -------------------------------------
//
// 13195 の素因数は 5, 7, 13, 29 である.
// 600851475143 の素因数のうち最大のものを求めよ.
//
// ----------------------------------------------------------------------------------------------------------

let sieveOfEratosthenes max =
    let sqrtMax = max |> (double >> sqrt >> int64)
    let rec sieve acc = function
        | [] -> acc
        | x::xs when sqrtMax < x -> acc@xs
        | x::xs -> sieve (acc@[x]) (List.filter (fun y -> y % x <> 0L) xs)
    sieve [] [2L]@[3L..2L..max]

sieveOfEratosthenes 600_851_475_143L
|> printfn "%A"