http://projecteuler.net/index.php?section=problems&id=30
重複組合せを自作しました(15 + 25 + 25 = 25 + 15 + 25だから)。yieldを使うと簡単ですね。
let rec repeated_combination a n = seq { if n = 0 then yield [] else if a <> [] then for b in repeated_combination a (n - 1) do yield (List.head a) :: b for b in repeated_combination (List.tail a) n do yield b }
あとは範囲を絞るだけです。
let rec repeated_combination a n = seq { if n = 0 then yield [] else if a <> [] then for b in repeated_combination a (n - 1) do yield (List.head a) :: b for b in repeated_combination (List.tail a) n do yield b } let rec digits n m = if m = 0 then [] else (digits (n / 10) (m - 1)) @ [n % 10] let to_number a = List.fold (fun x y -> x * 10 + y) 0 a let rec pow n e = if e = 0 then 1 else n * (pow n (e - 1)) let rec max_num e n = if (pow 9 e) * n < (pow 10 n) - 1 then n else max_num e (n + 1) let E = 5 let N = max_num E 1 let s = seq { for a in repeated_combination [0..9] N -> (a, List.sum [ for d in a -> pow d E ]) } let is_valid x = fst x = List.sort (digits (snd x) N) let v = Seq.sum (Seq.map (fun x -> snd x) (Seq.filter is_valid s)) printfn "%d" (v - 1)