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

Число, равное сумме своих делителей, древние считали воплощением гармонии.

Совершенное число — натуральное число, равное сумме всех своих собственных делителей (делителей, меньших самого числа).

Возьмём число 6. Его собственные делители — 1, 2, 3, и их сумма $1 + 2 + 3 = 6$. Число «воссоздаёт себя» из своих частей. Такие числа называли совершенными ещё пифагорейцы, видя в них символ завершённости (недаром мир, по преданию, был сотворён за 6 дней).

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

Следующее после 6 — число 28: его делители $1 + 2 + 4 + 7 + 14 = 28$. Дальше идут 496 и 8128. Все известные совершенные числа чётны, и каждое связано с простым числом Мерсенна формулой Евклида — Эйлера:

$$P = 2^{p-1} \cdot (2^p - 1), \quad \text{если } 2^p - 1 \text{ простое}.$$

Например, при $p = 2$: $2^1 \cdot (2^2 - 1) = 2 \cdot 3 = 6$. При $p = 3$: $2^2 \cdot 7 = 28$. Простые числа вида $2^p - 1$ называют простыми Мерсенна, и каждое из них рождает совершенное число. Существуют ли нечётные совершенные числа — не известно до сих пор.

Ищем совершенные числа

def divisor_sum(n):
    total = 1  # единица — делитель любого n > 1
    d = 2
    while d * d <= n:
        if n % d == 0:
            total += d
            if d != n // d:
                total += n // d
        d += 1
    return total

perfect = [n for n in range(2, 10000) if divisor_sum(n) == n]
print("Совершенные числа до 10000:", perfect)

# Проверим формулу Евклида - Эйлера
for p in [2, 3, 5, 7]:
    mersenne = 2**p - 1
    num = 2**(p - 1) * mersenne
    print(f"p={p}: 2^p-1={mersenne}, число={num}")

Вывод:

Совершенные числа до 10000: [6, 28, 496, 8128]
p=2: 2^p-1=3, число=6
p=3: 2^p-1=7, число=28
p=5: 2^p-1=31, число=496
p=7: 2^p-1=127, число=8128

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

Функция divisor_sum ищет делители парами: если $d$ делит $n$, то и $n/d$ делит. Поэтому перебор до $\sqrt n$ находит сразу оба делителя, что ускоряет код. Совершенные числа невероятно редки: до миллиарда их всего семь. Формула Евклида — Эйлера объясняет почему: каждое чётное совершенное число однозначно соответствует простому Мерсенна, а тех известно лишь несколько десятков. Числа, у которых сумма делителей меньше самого числа, называют недостаточными, а больше — избыточными; совершенные — редкая граница между ними.

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

Не включайте само число в сумму делителей — речь о собственных делителях. Не забывайте про парный делитель $n/d$ при переборе до корня. И будьте внимательны с квадратами: если $d = n/d$ (например, $d=2$ для $n=4$), делитель надо считать один раз, иначе сумма раздуется.

Итог

• Совершенное число равно сумме своих собственных делителей.
• Первые: 6, 28, 496, 8128.
• Формула Евклида — Эйлера: $2^{p-1}(2^p-1)$ при простом $2^p-1$.
• Нечётных совершенных чисел не нашли — открытый вопрос.