Project Euler 38

http://projecteuler.net/index.php?section=problems&id=38

nで左辺第1項の範囲が決まるので、あとはpandigitalになっているかチェックするだけ。

let rec pow n e = if e = 0 then 1 else n * (pow n (e - 1))
let rec digits n = if n = 0 then [] else (digits (n / 10)) @ [n % 10]
let to_number a = List.fold (fun x y -> x * 10 + y) 0 a

let rec is_pandigital ds flag =
   if ds = [] then true
   else
      let d = List.head ds
      if d = 0 then false
      else
         let f = 1 <<< d
         if (flag &&& f) = 0 then
            is_pandigital (List.tail ds) (flag ||| f)
         else
            false

let ceil n m = (n + m - 1) / m

let seq_pali n = seq {
   let q = 9 / n
   let r = 9 % n
   let min_m = if r > 0 then ceil (pow 10 q) (n - r + 1)
               else pow 10 (q - 1)
   let max_m = if r > 0 then ((pow 10 (q + 1)) - 1) / (n - r)
               else ((pow 10 q) - 1) / n
   for m in min_m..max_m do
      let a = List.concat (seq { for k in 1..n -> digits (k * m) })
      if is_pandigital a 0 then
         yield (to_number a)
}

printfn "%d" (Seq.max (seq { for n in 2..9 do
                              for m in seq_pali n -> m }))