vendredi 23 avril 2010

Project Euler #21

let proper_divisors_sum n =
  let limit = n / 2 in
  let rec proper_divisors_list n k =
    if k > limit then
      []
    else
      if n mod k = 0 then
        [k] @ (proper_divisors_list n (k + 1))
      else
        proper_divisors_list n (k + 1)
  in
  List.fold_left (+) 0 (proper_divisors_list n 1);;

let amicable_numbers_sum n =
  let rec amicable_numbers k =
    if k > n then
      []
    else
      let b = proper_divisors_sum k in
      let a = proper_divisors_sum b in
      if (a != b) && (a = k) then
        [k] @ (amicable_numbers (k + 1))
      else
        amicable_numbers (k + 1)
  in
  List.fold_left (+) 0 (amicable_numbers 2);;

Printf.printf "%d\n" (amicable_numbers_sum 10000);;
Quite straightforward and surely using lists ;) Actually we can sum without intermediate lists.

Aucun commentaire:

Publier un commentaire