OCaml: совершенные числа

Согласно определению, совершенными называются числа, равные сумме своих делителей. Мы хотим создать небольшой набор функций, с помощью которого можно находить совершенные числа.

Первая функция в наборе называется divisors и её задача  - формировать список делителей числа.

let divisors n =
   let rec iter n j lst=
     if j>=n then lst
     else 
       if n mod j==0 then iter n (j+1) (j::lst)
       else
          iter n (j+1) lst in
   if n<=1 then []
   else
     iter n 1 [] ;;

Функция divisors содержит описание вложенной функции iter, которая и формирует список делителей.  Для этого она находит остаток от деления числа (n) на показание счётчика (j) и если остаток равен нулю, то число считается делителем и включается в список (j::lst).

Пример использования:

# divisors 28;;
- : int list = [14; 7; 4; 2; 1]

Вторая функция находит сумму элементов списка, используя механизм паттернов:

let rec sumlist lst =  
      match lst with
        | [] -> 0
        | hd::tl -> hd + sumlist tl;;

Третья функция является связующей и именно она ищет совершенные числа в заданном диапазоне (от 1 до n)

let rec perfect n lst = 
      if n=1 then lst
      else
        if sumlist (divisors n) = n then
          perfect (n-1) (n::lst)
        else
          perfect (n-1) lst;;

Определим результат для интервала от 1 до 10000. Время вычисления приблизительно оценивается в несколько секунд.

# perfect 10000 [];;
- : int list = [6; 28; 496; 8128]

Вывод: язык OCaml обладает достаточно выразительными средствами для решения классических задач из теории чисел в частности и функционального программирования в целом. Остаётся провести исследование производительности при использовании оптимизирующего компилятора в native-код.