amicable.ml

let total = 10000

let primes =
  let rec loop primes = function
    | n when n * n > total -> primes
    | n ->
       let rec loop2 = function
	 | [] -> true
	 | x::xs ->
	    if x * x > n
	    then true
	    else
	      if n mod x == 0
	      then false
	      else loop2 xs
       in
       let primes =
	 if loop2 primes
	 then primes @ [n]
	 else primes
       in
       loop primes (n + 2)
  in
  loop [2] 3

let divs n =
  let rec loop acc n = function
    | [] -> acc
    | (x::xs) as prims ->
       if x * x > n
       then n :: acc
       else
	 if n mod x == 0
	 then loop (x :: acc) (n / x) prims
	 else loop acc n xs
  in
  let rec loop2 acc = function
    | [] -> acc
    | x::xs ->
       let acc =
	 List.fold_left
	   (fun acc y ->
	     let t = x * y
	     in
	     if (t == n) || (List.mem t acc)
	     then acc
	     else t :: acc)
	   acc
	   acc
       in
       loop2 acc xs
  in
  loop2 [1] (loop [] n primes);;

let sums = Array.init (total + 1) (fun i -> List.fold_left (+) 0 (divs i))

let rec loop acc = function
  | n when n > total -> acc
  | n ->
     let t = sums.(n) in
     let acc =
       if (t == n) || (t > total)
       then acc
       else
	 if sums.(t) == n
	 then acc + n
	 else acc
     in
     loop acc (n + 1)

let () =
  Printf.printf "%d\n" (loop 0 1);;