Аликвотная последовательность

В математике аликвотная последовательность — это рекурсивная последовательность, в которой каждый член является суммой собственных делителей предыдущего члена. Аликвотная последовательность, начинающаяся с некоторого положительного целого числа k, может быть определена формально в терминах суммирующей функции делителей σ₁ следующим образом[1]:

s₀ = k

s_n = σ₁(s_n−1) − s_n−1.

Например, аликвотная последовательность для числа 10 — 10, 8, 7, 1, 0, поскольку:

σ₁(10) − 10 = 5 + 2 + 1 = 8

σ₁(8) − 8 = 4 + 2 + 1 = 7

σ₁(7) − 7 = 1

σ₁(1) − 1 = 0

Многие аликвотные последовательности завершаются нулём (последовательность A080907 в OEIS), и все такие последовательности завершаются простым числом с последующими единицей (поскольку единственным собственным делителем простого числа является единица) и нулём (поскольку у единицы нет собственных делителей). Имеется также несколько случаев, когда аликвотная последовательность бесконечна:

• Совершенное число имеет повторяющуюся аликвотную последовательность с периодом 1. Аликвотной последовательностью шести, например, является 6, 6, 6, 6, ...
• Дружественные числа имеют повторяющуюся аликвотную последовательность с периодом 2. Например, аликвотной последовательностью числа 220 является 220, 284, 220, 284, ...
• Компанейские числа имеют повторяющуюся аликвотную последовательность с любым периодом. Например, аликвотной последовательностью числа 1 264 460 является 1 264 460, 1 547 860, 1 727 636, 1 305 184, 1 264 460, ...
• Некоторые числа дают аликвотную последовательность, с некоторого места переходящую в последовательность с некоторым периодом, не будучи при этом ни совершенными, ни дружественными, ни компанейскими. Например, аликвотной последовательностью числа 95 является 95, 25, 6, 6, 6, 6, ... . Числа наподобие 95, не являющиеся совершенными, но дающие последовательность, переходящую с некоторого места в последовательность с периодом 1, называются сходящимися (A063769).

Длины аликвотных последовательностей, начинающихся с n:

1, 2, 2, 3, 2, 1, 2, 3, 4, 4, 2, 7, 2, 5, 5, 6, 2, 4, 2, 7, 3, 6, 2, 5, 1, 7, 3, 1, 2, 15, 2, 3, 6, 8, 3, 4, 2, 7, 3, 4, 2, 14, 2, 5, 7, 8, 2, 6, 4, 3, ... (последовательность A044050 в OEIS).

Последний элемент аликвотных последовательностей (не включая 1), начинающихся с n:

1, 2, 3, 3, 5, 6, 7, 7, 3, 7, 11, 3, 13, 7, 3, 3, 17, 11, 19, 7, 11, 7, 23, 17, 6, 3, 13, 28, 29, 3, 31, 31, 3, 7, 13, 17, 37, 7, 17, 43, 41, 3, 43, 43, 3, 3, 47, 41, 7, 43, ... (последовательность A115350 в OEIS).

Числа, аликвотные последовательности которых завершаются 1:

1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, ... (последовательность A080907 в OEIS).

Числа, аликвотные последовательности которых завершаются совершенным числом:

25, 95, 119, 143, 417, 445, 565, 608, 650, 652, 675, 685, 783, 790, 909, 913, ... (последовательность A063769 в OEIS).

Числа, аликвотные последовательности которых завершаются циклом длины 2:

220, 284, 562, 1064, 1184, 1188, 1210, 1308, 1336, 1380, 1420, 1490, 1604, 1690, 1692, 1772, 1816, 1898, 2008, 2122, 2152, 2172, 2362, ... (последовательность A121507 в OEIS).

Числа, для которых не известно, являются ли их аликвотные последовательности конечными или периодическими:

276, 306, 396, 552, 564, 660, 696, 780, 828, 888, 966, 996, 1074, 1086, 1098, 1104, 1134, 1218, 1302, 1314, 1320, 1338, 1350, 1356, 1392, 1398, 1410, 1464, 1476, 1488, ... (последовательность A131884 в OEIS).

Важной гипотезой относительно аликвотных последовательностей, принадлежащей Каталану, является предположение, что любая аликвотная последовательность завершается одним из перечисленных путей — простым числом, совершенным числом, набором дружественных чисел или набором компанейских чисел[2]. В противном случае должны существовать числа, аликвотная последовательность которых бесконечна и апериодична. Любое из упомянутых выше чисел, для которых аликвотная последовательность не определена полностью, может оказаться таким числом. Первые пять кандидатов называются пятёрка Лемера (по имени американского математика Дика Лемера): 276, 552, 564, 660 и 966[3].

К декабрю 2013 года известно 898 положительных целых чисел, меньших 100 000, для которых аликвотная последовательность не установлена, и 9205 таких чисел, меньших 1 000 000[4].