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

Два числа, каждое из которых «строит» другое из своих делителей, — математический символ дружбы.

Дружественные числа — пара чисел, в которой сумма собственных делителей каждого равна другому числу.

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

Пара 220 и 284

Обозначим через $s(n)$ сумму собственных делителей $n$. Пара $(a, b)$ дружественна, если

$$s(a) = b \quad \text{и} \quad s(b) = a.$$

Проверим на классике. Делители 220: $1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110$ — их сумма равна 284. Делители 284: $1, 2, 4, 71, 142$ — их сумма равна 220. Числа «ссылаются» друг на друга. Заметьте: совершенное число — частный случай, когда $a = b$.

Ищем дружественные пары

def divisor_sum(n):
    total = 1
    d = 2
    while d * d <= n:
        if n % d == 0:
            total += d
            if d != n // d:
                total += n // d
        d += 1
    return total

pairs = []
for a in range(2, 1500):
    b = divisor_sum(a)
    if b > a and divisor_sum(b) == a:
        pairs.append((a, b))
print("Дружественные пары до 1500:", pairs)

# Подробно про 220 и 284
print("s(220) =", divisor_sum(220))
print("s(284) =", divisor_sum(284))

Вывод:

Дружественные пары до 1500: [(220, 284), (1184, 1210)]
s(220) = 284
s(284) = 220

Как работает под капотом

В цикле мы для каждого $a$ считаем $b = s(a)$ и проверяем, вернёт ли $s(b)$ обратно $a$. Условие $b \gt a$ нужно, чтобы каждую пару не печатать дважды и заодно отсечь совершенные числа (там $b = a$). Пара $(1184, 1210)$ была найдена лишь в 1866 году шестнадцатилетним итальянцем Никколо Паганини (тёзкой скрипача) — её «проглядели» великие математики, потому что искали среди больших чисел. Существуют и более длинные циклы: «общительные» числа, где $s$ возвращает к началу через несколько шагов.

Частые ошибки

Не считайте пару $(n, n)$ дружественной — это уже совершенное число, для дружественных нужны различные числа. Не забывайте проверять обратное условие $s(b) = a$: одного равенства $s(a) = b$ мало. И не путайте: $s(n)$ — сумма собственных делителей, само $n$ не входит.

Итог

Дружественная пара: $s(a) = b$ и $s(b) = a$ при $a \neq b$.
Классическая пара — 220 и 284.
Совершенное число — вырожденный случай $a = b$.
Бывают и длинные «общительные» циклы.