Project Euler 37

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

2パターンは数字を右から追加するか左から追加するかなので、数字を追加する関数をそれぞれ作っておきます。

let add_right m d n = m * 10 + d
let add_left m d n = m + d * n

nはmが3桁なら1000です。
そして、truncatable primeから次の桁のそれを作るという作業をするのですが、このときに、

let next_list f a n = ...
let s_add f = ...
let s_right = s_add (next_list add_right)

最後のs_addの引数がカリー化された関数になっています。
さて、このようにして、両方のソートされたSequenceを作ったので、あとはいつものように比較していって一致する数を出すだけなのですが、よく考えるとSequenceはこのような操作ができないようです。しかたがないので、短いに決まっている右から追加する方をまずListにし、それの最大の数までで左からの方を打ち切ってListにします。左からのが大きな数の素数判定をしなければならないのを避けています。双方Listにすると、いつものアルゴリズムが使えます。

let is_prime n = n > 1 &&
                  Seq.forall (fun p -> n % p <> 0)
                     ((Seq.takeWhile (fun p -> p * p <= n)
                        (Seq.initInfinite (fun i -> i + 2))))

let rec pow n e = if e = 0 then 1 else n * (pow n (e - 1))

let add_right m d n = m * 10 + d
let add_left m d n = m + d * n

let next_list f a n =
   List.sort (List.filter is_prime
               [ for e in a do for d in 1..9 -> f e d n ])

let s_add f =
   let g t = if List.length (fst t) = 0 then None
             else Some(fst t, (f (fst t) (snd t), (snd t) * 10))
   seq { for a in Seq.unfold g ([0], 1) do for n in a -> n }

let s_right = s_add (next_list add_right)
let s_left = s_add (next_list add_left)

let l_right = Seq.toList s_right
let last = l_right.[l_right.Length-1]
let l_left = Seq.toList (Seq.takeWhile (fun n -> n <= last) s_left)

let rec coincident (a : int list) (b : int list) =
   if a = [] || b = [] then
      []
   else
      let m = a.Head
      let n = b.Head
      if m = n then m :: (coincident a.Tail b.Tail)
      else if m < n then (coincident a.Tail b)
      else               (coincident a b.Tail)

printfn "%d" (Seq.sum (coincident l_right l_left) - (2 + 3 + 5 + 7))