Дружественные числа

Пусть d(n) определяется как сумма делителей n (числа меньше n, делящие n нацело). Если d(a) = b и d(b) = a, где a ≠ b, то a и b называются дружественной парой, а каждое из чисел a и b - дружественным числом.

Например, делителями числа 220 являются 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 и 110, поэтому d(220) = 284. Делители 284 - 1, 2, 4, 71, 142, поэтому d(284) = 220.

Подсчитайте сумму всех дружественных чисел меньше 10000.

Решение (F#)

1. Для начала объявим функцию нахождения квадратного корня из целого числа isq, она нам потребуется для нахождения множителей, как верхняя граница перебора
2. создадим функцию генерации всех делителей числа divs
   • добавим в последовательность единицу,
   • для всех чисел от 2 до sqrt(n) проверим делится ли нацело
   • если делится, то запишем делитель
   • если кратное не равно делителю, то запишем и его, т.к. если a/b = c, то a/c = b, b и c являются делителями для числа a
3. последовательность solv содержит все дружественные числа
   • для каждого числа из диапазона 1..9999 найдем сумму делителей d1
   • найдем сумму делителей для числа d1
   • если сумма равна исходному, то запишем число
4. посчитаем сумму дружественных чисел и выведем ответ

let isq = float >> sqrt >> int

let divs n =
    seq {
        yield 1
        for i in 2 .. isq n do
            if n % i = 0 then
                yield i
                let d = n / i
                if i <> d then
                    yield d
    }

let solv =
    seq {
        for i in 1..9999 do
            let d1 = divs i |> Seq.sum
            let d2 = divs d1 |> Seq.sum
            if d2 = i then
                yield i
    }

let answer = solv |> Seq.sum

printfn $"the answer is {answer}" //the answer is 40285

• кому интересно, спиок дружественных чисел

  [1; 6; 28; 220; 284; 496; 1184; 1210; 2620; 2924; 5020; 5564; 6232; 6368; 8128]