Project Euler #23

(* generates array with values [1..n] *)
let rec range_array n =
  if n == 1 then
    [| n |]
  else
    Array.append (range_array (n - 1)) [| n |];;

(* calculates sum of proper divisors of given number *)
let sum_of_proper_divisors n =
  let limit = n / 2 in
  let rec sum_divisors k l =
    if k > l then
      0
    else
      if n mod k = 0 then
        k + sum_divisors (k + 1) l
      else
        sum_divisors (k + 1) l
  in
  if n = 1 then
    1
  else
    sum_divisors 1 limit;;

(* checks whether given number is abundant*)
let is_abundant n =
  n < sum_of_proper_divisors n;;

(* generates array of abundant number less than given number *)
let find_abundant_numbers n =
  let rec gen_numbers k =
    if k = n then
      [||]
    else
      if is_abundant k then
        Array.append [| k |] (gen_numbers (k + 1))
      else
        gen_numbers (k + 1)
  in
  gen_numbers 12;;

let binary_search (data:'a array) elem =
  let rec iter a b =
    if a = b then -1
    else
      let median = a + (b - a)/2 in
      match data.(median) with
      | value when value = elem -> median
      | value when value < elem -> iter (median + 1) b
      | _                       -> iter a median
  in
  iter 0 (Array.length data);;

let make_possible_sums a =
  let len = (Array.length a) - 1 in
  let res = Array.make_matrix (len + 1) (len + 1) 0 in
  for i = 0 to len do
    for j = i to len do
      res.(i).(j) <- a.(i) + a.(j)
    done
  done;
  res;;

(* sets all elements of a found in s to 0 *)
let refine_array a s =
  let to_delete = Array.make (Array.length a) false in
  let l1 = Array.length s in
  let l2 = Array.length s.(0) in
  for i = 0 to l1 - 1 do
    for j = 0 to l2 - 1 do
      let idx = binary_search a s.(i).(j) in
      if idx != -1 then
        to_delete.(idx) <- true
    done
  done;
  for i = 0 to (Array.length to_delete) - 1 do
    if to_delete.(i) then
      a.(i) <- 0
  done;;

let all_numbers = range_array 28123;;
let abundant_numbers_sums = make_possible_sums (find_abundant_numbers 28123);;
refine_array all_numbers abundant_numbers_sums;;

Printf.printf "%d\n" (Array.fold_left (+) 0 all_numbers);;

Straightforward and very slow but correct solution ;)