Общительные числа: что это и как найти цикл s(n)

Общительные числа (англ. sociable numbers) - это группа из трёх и более натуральных чисел, замкнутых в цикл функцией «сумма собственных делителей». Берём число, складываем все его делители, кроме самого числа, получаем второе число; для него считаем ту же сумму, получаем третье, и так далее. Если через несколько шагов мы возвращаемся ровно к исходному числу, вся цепочка чисел и называется общительной. Это прямое обобщение совершенных и дружественных чисел: у первых цикл состоит из одного числа, у вторых из двух, а у общительных длина цикла равна трём и больше. Ниже разберём, как устроена функция $s(n)$, чем три класса отличаются друг от друга, как найти цикл на практике и где в задачах чаще всего ошибаются. Чтобы сразу почувствовать, как итерация $s(n)$ гоняет число по компании, покрутите калькулятор: впишите своё число, и он покажет траекторию суммы делителей и найденный цикл.

Функция суммы собственных делителей s(n)

Всё держится на одной функции. Для натурального числа $n$ обозначим через $s(n)$ сумму всех его собственных делителей, то есть делителей, меньших самого $n$:

$s(n) = \sum_{\substack{d \mid n \\ d < n}} d.$

Например, делители числа $284$, меньшие его самого, это $1, 2, 4, 71, 142$, и их сумма равна $220$. А у числа $220$ собственные делители $1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110$ в сумме дают $284$. Получается, что $s(220) = 284$ и $s(284) = 220$: применив функцию дважды, мы вернулись к началу.

Иногда вместо $s(n)$ удобно работать с суммой всех делителей $\sigma(n)$, включая само число. Связь простая: $s(n) = \sigma(n) - n$. Через $\sigma$ сумму делителей легко считать по разложению на простые множители: если $n = p_1^{a_1} \cdots p_k^{a_k}$, то $\sigma(n)$ равна произведению геометрических сумм по каждому простому множителю. Поэтому в серьёзных вычислениях используют именно $\sigma$, а собственную сумму получают вычитанием. Знак разности $s(n) - n$ сразу подсказывает поведение: если делителей много и $s(n) > n$, число называют избыточным, если $s(n) < n$ - недостаточным, а равенство $s(n) = n$ выделяет совершенные числа.

Аликвотная последовательность и три судьбы

Если применять $s$ снова и снова, получится так называемая аликвотная последовательность: $n,\ s(n),\ s(s(n)),\ \dots$. У любого старта она ведёт себя одним из нескольких способов, и именно это разделяет числа на классы.

Рассчитать для своей задачи

Чаще всего сумма делителей раньше или позже приводит к простому числу, у которого собственный делитель только единица, и цепочка обрывается: после простого числа идёт $1$, а $s(1) = 0$. Такие числа никакого цикла не образуют. Но бывают и замкнутые сценарии. Удобно сразу разглядеть все три на одной картинке.

Рассчитать для своей задачи

Если цепочка замыкается, длина цикла и задаёт класс числа:

• Цикл длины 1 - это неподвижная точка $s(n) = n$, совершенное число. Классические примеры: $6$ (делители $1+2+3=6$) и $28$ (делители $1+2+4+7+14=28$).
• Цикл длины 2 - пара чисел, переходящих друг в друга: $s(a) = b$ и $s(b) = a$. Это дружественные числа, например $220$ и $284$.
• Цикл длины 3 и больше - и есть общительные числа.

Как выглядит общительный цикл

Самый известный общительный цикл имеет длину 5 и начинается с числа $12496$:

$12496 \to 14288 \to 15472 \to 14536 \to 14264 \to 12496.$

На каждой стрелке стоит одно и то же правило: следующее число равно сумме собственных делителей текущего. Проверить можно прямо в калькуляторе выше, выбрав чип «12496»: траектория поднимается и опускается, проходя через все пять чисел, а затем точно возвращается в исходную точку. Этот цикл нашёл в 1918 году бельгийский математик Поль Пуле, поэтому общительные числа иногда называют цепочками Пуле.

Циклы бывают и другой длины. Например, существует цикл порядка 4, начинающийся с $1264460$, и знаменитый цикл длины 28, начинающийся с $14316$, - один из самых длинных среди небольших чисел. А вот циклов длины 3 до сих пор не найдено ни одного, хотя их существование не запрещено: это до сих пор открытый вопрос теории чисел.

Длина цикла называется его порядком. Совершенные числа можно считать общительными порядка 1, дружественные - порядка 2, но обычно термин «общительные» закрепляют именно за порядком от 3 и выше, чтобы отличать их от уже названных классов.

Чем общительные числа отличаются от дружественных

Разница только в длине цикла, но путаница встречается постоянно. Дружественные числа - это всегда ровно два числа, и условие у них симметричное: каждое равно сумме собственных делителей другого. Общительные числа - это цикл из трёх и более, где каждое переходит в следующее по кругу, а замыкается всё через несколько шагов, а не сразу.

Полезно держать в голове такую иерархию по порядку цикла $k$ функции $s$:

$k = 1:\ \text{совершенные}, \qquad k = 2:\ \text{дружественные}, \qquad k \ge 3:\ \text{общительные}.$

То есть все три класса - это один и тот же объект (цикл функции $s$), просто разной длины. Поэтому в задаче «докажите, что числа образуют общительный цикл» достаточно проверить, что сумма собственных делителей каждого числа даёт следующее, а последнее замыкается на первое.

Как найти цикл на практике

Алгоритм поиска прямолинеен и хорошо ложится в калькулятор выше. Чтобы проверить число $n$:

1. Посчитайте $s(n)$ - сумму его собственных делителей.
2. Возьмите полученное число и снова примените $s$.
3. Повторяйте, записывая все встреченные числа.
4. Как только очередное число совпало с одним из уже записанных, вы нашли цикл; если же дошли до единицы, цикла нет.

Главная вычислительная трудность - быстро считать сумму делителей. Перебор всех чисел до $n$ слишком долог для больших значений, поэтому делители ищут до $\sqrt{n}$: если $d$ делит $n$, то и $n/d$ делит $n$, и оба добавляются в сумму сразу. Именно так устроена функция в калькуляторе, поэтому он мгновенно обрабатывает даже шестизначные числа вроде $1264460$.

Есть и подводный камень: у некоторых стартовых чисел аликвотная последовательность сначала растёт, прежде чем замкнуться или оборвать, поэтому останавливать перебор нужно либо по совпадению с уже встреченным числом, либо по достижении единицы, либо по разумному ограничению на число шагов. Для самых упрямых стартов (например, числа $276$) до сих пор неизвестно, замкнётся ли их последовательность вообще - это знаменитая открытая гипотеза Каталана и Диксона о том, что любая аликвотная последовательность либо обрывается, либо попадает в цикл. Калькулятор выше как раз ограничивает число шагов: если за них цепочка не определилась, он честно сообщает, что результат не получен.

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

• Считают сам делитель. В сумму $s(n)$ входят только делители, меньшие $n$. Если по привычке включить само число, совершенное число «перестанет» быть совершенным, а цикл не замкнётся.
• Путают порядок цикла. Дружественные числа - это цикл длины 2, а не «два общительных числа». Общительными по умолчанию называют циклы порядка от 3.
• Останавливаются на первом совпадении знаков. Цикл найден только тогда, когда последовательность вернулась к ранее встреченному числу. Промежуточное равенство сумм ничего не значит.
• Ищут цикл длины 3. Таких циклов пока не нашли ни одного, поэтому в учебной задаче минимальный «настоящий» общительный цикл - это пятёрка чисел Пуле.
• Не переходят к $\sigma(n)$ для больших чисел. Сумму делителей удобнее считать через разложение на простые множители, а собственную получать как $\sigma(n) - n$.

FAQ

Существуют ли общительные числа из трёх чисел? На сегодня не найдено ни одного цикла длины 3, и вопрос остаётся открытым. Известны циклы длины 1, 2, 4, 5, 6, 8, 9 и больше, но именно тройку до сих пор никто не обнаружил и не доказал её невозможность.

Сколько вообще известно общительных циклов? Их найдено уже несколько миллионов, в основном порядков 4 и больше, причём подавляющее большинство имеют длину 4. Цикл длины 28, начинающийся с $14316$, остаётся одним из самых эффектных примеров среди небольших чисел.

Чем общительные числа полезны? Прямого практического применения у них нет: это классическая задача теории чисел, важная как пример того, как простая итерация порождает богатую структуру. Поиск таких циклов используют для проверки алгоритмов факторизации и подсчёта суммы делителей.

Коротко

Общительные числа - это цикл из трёх и более натуральных чисел, замкнутый функцией суммы собственных делителей $s(n)$: каждое число переходит в следующее, а последнее возвращается к первому. Совершенные числа отвечают циклу длины 1, дружественные - длины 2, общительные - длины 3 и больше. Самый известный пример - цикл порядка 5, начинающийся с $12496$. Чтобы проверить число, достаточно итерировать $s(n)$ и следить, вернётся ли цепочка к старту или оборвётся на единице.