(*
The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?
*)

(* list of 1,2,3, and 4 digit primes *)
let primes =
  let rec primes x l =
    if x>9999 then l else
    if( List.exists (fun y->(x mod y=0)) l)
    then primes (x+1) l
    else primes (x+1) (x::l)
  in
    primes 2 []
;;

(* just four digit primes *)
let primes4d = List.filter (fun x->(x>999)) primes;;

(* decompose an integer into cifers *)
let rec cifers n =
  if n = 0 then [] else
  (n mod 10)::(cifers (n/10))
;;

(* check whether a b c are pairwise permutations *)
let check a b c =
  let ca=Sort.list (<) (cifers a) in
  let cb=Sort.list (<) (cifers b) in
  let cc=Sort.list (<) (cifers c) in
  if
    (List.for_all2 (=) ca cb) &&
    (List.for_all2 (=) cb cc)
  then Printf.printf "%d%d%d\n" c b a
  else ()
in
(* given a and b, we can search c among the list l of primes *)
(* we know that a>b, by the order (primes) generates *)
let rec search3 a b l =
  if List.mem (b-(a-b)) l
  then check a b (b-(a-b))
in
(* search b in l *)
let rec search2 a l =
  match l with
  [] -> ()
  | h::t -> (search3 a h t);(search2 a t)
in
(* search a in l *)
let rec search1 l =
  match l with
  [] -> ()
  | h::t -> (search2 h t);(search1 t) 
in
  search1 primes4d
;;