## lundi 26 avril 2010

### 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 ;)