Русская Википедия:Совершенное тотиентное число
Совершенное тотиентное число — это целое число, которое равно сумме его итерированных тотиентов (значений функции Эйлера). То есть, мы применяем функцию Эйлера к числу n и последовательно ко всем получающимся тотиентам, пока не достигнем числа 1, последовательно складывая получающиеся числа. Если сумма равна n, то n является совершенным тотиентным числом. Алгебраически, если
- <math>n = \sum_{i = 1}^{c + 1} \varphi^i(n),</math>
где
- <math>\varphi^i(n)=\left\{\begin{matrix}\varphi(n), i = 1\\ \varphi(\varphi^{i-1}(n)), i \ne 1\end{matrix}\right.</math>
рекурсивная итерированная функция Эйлера, а c — это целое число, такое, что
- <math>\displaystyle\varphi^c(n)=2,</math>
то n является совершенным тотиентным числом.
Совершенное тотиентное число по определению является нечётным.
Несколько первых совершенных тотиентных чисел
- 3, 9, 15, 27, 39, 81, Шаблон:Нп4, 183, Шаблон:Нп4, Шаблон:Нп4, Шаблон:Нп4, Шаблон:Нп4, 471, 729, 2187, 2199, 3063, 4359, 4375, … (Шаблон:OEIS).
Например, начиная с 327 вычисляем φ(327) = 216, φ(216) = 72, φ(72) = 24, φ(24) = 8, φ(8) = 4, φ(4) = 2, φ(2) = 1, получаем 216 + 72 + 24 + 8 + 4 + 2 + 1 = 327.
Числа вида a(n)=2^(2^n)-1
Несколько чисел вида <math>a(n)=2^{2^n}-1</math> (Шаблон:OEIS), такие, как Шаблон:Нп4, Шаблон:Нп4, Шаблон:Нп4 и Шаблон:Число, являются совершенными тотиентными числами, и, кроме того, являются максимальными беззнаковыми целыми числами соответственно 8-, 16-, 32- и 64-битных переменных. Более ранние числа 3 и 15 из той же последовательности также являются совершенными тотиентными числами.
Степени тройки
Можно заметить, что многие совершенные тотиентные числа делятся на 3. Фактически, число 4375 является наименьшим совершенным тотиентным числом, не делящимся на 3. Все степени 3 являются совершенными тотиентными числами, что можно показать по индукции, используя факт
- <math>\displaystyle\varphi(3^k) = \varphi(2\times 3^k) = 2\times 3^{k-1}.</math>
Венкатараман (1975) нашёл другое семейство совершенных тотиентных чисел — если p = 4×3k+1 простое, то 3p совершенное тотиентное число. Значения k, ведущие к совершенным тотиентным числам этим способом:
- 0, 1, 2, 3, 6, 14, 15, 39, 201, 249, 1005, 1254, 1635, … (Шаблон:OEIS).
Более обще, если p является простым числом, большим 3, и 3p является совершенным тотиентным числом, то p ≡ 1 (mod 4)Шаблон:Sfn. Не все p этого вида приводят к совершенным тотиентным числам. Так, 51 совершенным тотиентным числом не является. Иануччи, Денг и КоэнШаблон:Sfn показали, что если 9p является совершенным тотиентным числом, то p является простым и имеет одну из трёх форм, перечисленных в статье. Неизвестно, имеются ли совершенные тотиентные числа вида 3kp, где p является простым и k > 3.
Примечания
Литература
Замечание: Оригинал статьи включает материал из статьи Perfect Totient Number с сайта PlanetMath c лицензией Creative Commons Attribution-ShareAlike 3.0 Unported
Шаблон:Классы натуральных чисел Шаблон:Rq
