Project Euler 46

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

これも前問と同じアルゴリズムを、奇数ごとに適用します。この問題は有限リストなので素直に書けます。

let mutable primes = [ 2 ]
let is_prime n = Seq.forall (fun p -> n % p <> 0)
                  (Seq.takeWhile (fun p -> p * p <= n) primes)
let extend_primes ps max_n =
   let last = List.nth ps ((List.length ps) - 1)
   ps @ (List.filter is_prime [last+1..max_n])

let rec coincident ps qs : bool =
   let p = if ps = [] then 0 else List.head ps
   let q = if qs = [] then 0 else List.head qs
   if p = 0 || q = 0 then false
   else if p = q then true
   else if p < q then coincident (List.tail ps) qs
   else               coincident ps             (List.tail qs)

let s = seq {
   for n in Seq.initInfinite (fun n -> n * 2 + 9) do
      primes <- extend_primes primes n
      let sq = Seq.toList ((Seq.takeWhile ((<=) 0)
                           (Seq.initInfinite
                                    (fun k -> n - 2 * k * k))))
      if not (coincident primes (List.rev sq)) then
         yield n
}

printfn "%d" (Seq.head s)