Project Euler 35

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

重複して素数判定したくないのでうまく代表元を選んでそれを回転して素数判定したいところです。それには、回転して最小の数を代表元に選べばよいです。例えば、791なら791→917→179だから、179を代表元にします。しかし、代表元を列挙するのは難しいので、頭の数字を決めたら、それより小さな数字は使えないことにして列挙します。回転してみて最小だったらそれを使います。2桁以上の場合、当然数字は1,3,7,9しか使えません。最後に回転して同じ数が出てくる場合があるので、それを考慮に入れてカウントします。

let sieve max_n =
   let a = Array.create (max_n + 1) true
   a.[0] <- false
   a.[1] <- false
   for p in Seq.takeWhile (fun k -> k * k <= max_n)
            (Seq.filter (fun k -> a.[k])
            (Seq.initInfinite (fun k -> k))) do
      for k in p*2..p..max_n do
         a.[k] <- false
   
   List.filter (fun i -> a.[i]) [ 2..max_n ]

let rec pow n e = if e = 0 then 1 else n * (pow n (e - 1))
let rec num_digits n = if n < 10 then 1 else 1 + (num_digits (n / 10))

let rotate n =
   let e = num_digits n
   let m = pow 10 (e - 1)
   Seq.take e (Seq.unfold (fun n' -> Some(n', n' / 10 + n' % 10 * m)) n)

let N = 6
let primes = sieve (int (sqrt (double (pow 10 N))))

let is_prime n = Seq.forall (fun p -> n % p <> 0)
                        (Seq.takeWhile (fun p -> p * p <= n)
                              (List.toSeq primes))
let is_circular_prime n = Seq.forall is_prime (rotate n)

let is_rot_min n = Seq.forall (fun m -> m >= n) (rotate n)

let rot_min n =
   if n = 1 then
      seq { 2..9 }
   else
      let ds = [ 1; 3; 7; 9 ]
      let rec rot_min_core n d0 =
         if n = 0 then
            seq [ 0 ]
         else
            seq { for m in rot_min_core (n - 1) d0 do
                     for d in Seq.filter (fun d -> d >= d0) ds ->
                        m * 10 + d
            }
      
      let p = pow 10 (n - 1)
      seq {
         for d0 in ds do
            for m in rot_min_core (n - 1) d0
               -> d0 * p + m
      }

let uniq n = Set.count (Set.ofSeq (rotate n))

printfn "%d" (Seq.sum (Seq.map uniq
                  (Seq.filter
                        (fun n -> is_rot_min n && is_circular_prime n)
                     (seq { for n in 1..N do
                              for m in rot_min n -> m }))))