Project Euler #35

let is_prime n =
  if n < 0 then
    false
  else
    let lim = int_of_float (sqrt (float_of_int n)) in
    let rec check_mod i l =
      if i > l then
        true
      else
        if n mod i = 0 then
          false
        else
          true && (check_mod (succ i) l)
    in
    check_mod 2 lim;;

let primes n =
  let rec inner_primes i =
    if i > n then
      []
    else
      if is_prime i then
        [i] @ inner_primes (succ i)
      else
        inner_primes (succ i)
  in
  inner_primes 2;;

let circulations n = 
  let rec circulate str =
    let str_len = String.length str in
    if str_len = 1 then
      [int_of_string n]
    else
      let variant = (String.sub str 1 (str_len - 1)) ^ (String.sub str 0 1) in
      if variant = n then
        [(int_of_string variant)]
      else
        [(int_of_string variant)] @ (circulate variant)
  in
  circulate n;;

(*
let is_circular n primes = 
  let number_string = string_of_int n in
  let variants = circulations number_string in
  List.fold_left 

    (&&) 

    true 

    (List.map 

      (fun x -> List.exists (fun y -> (x = y)) primes) 

      variants);;
*)

let is_circular n =
  let number_string = string_of_int n in
  let variants = circulations number_string in
  List.fold_left (&&) true (List.map (is_prime) variants);;

let primes_till_1e6 = primes 1000000;;
let test_primes = primes_till_1e6;;

Printf.printf "%d\n" 
    (List.fold_left 
       (+) 
       0 
       (List.map 
         (fun x -> if (is_circular x) then 1 else 0 ) 
         test_primes));;

Strange thing: List.exists is quite slow, so when I switched from using List.exists (commented out) to just plain is_prime in is_circular it became possible to get result in a minute. Or maybe I just can't use List.exists properly.