(*
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.
*)

(*
Remarks:
- working on lists of cifers is more efficient
*)

(* get a nat number as a list of cifers *)
let rec cifers n =
  if n = 0 then [] else
  (n mod 10)::(cifers (n/10))
;;

(* check whether list is a palindrome; half the way is good enough here *)
let palindrome l = List.for_all2 (=) l (List.rev l);;

(* checks whether number factors in two three-cifer numbers *)
let fi3 n =
  let rec fi3 n x =
    if x<1 then false else
    if ((n mod x=0)&&(n/x<1000)) then true else
    fi3 n (x-1)
  in
    fi3 n 999
;;
  

(* largest palindrome below x which factors into numbers of three cifers *)
let rec lp x =
  (* largest prime factor <= y *)
  let rec lpf y =
    Printf.printf "lpf %d %d\n" x y;
    if (x mod y = 0) then y else (lpf (y-1))
  in
    if (
      ( palindrome ( cifers x ) ) &&
      ( fi3 x ) )
    then x
    else lp (x-1)
;;

Printf.printf "%d\n" (lp 999999);;