Совершенное тотиентное число

Совершенное тотиентное число — это целое число, которое равно сумме его итерированных тотиентов (значений функции Эйлера). То есть, мы применяем функцию Эйлера к числу n и последовательно ко всем получающимся тотиентам, пока не достигнем числа 1, последовательно складывая получающиеся числа. Если сумма равна n, то n является совершенным тотиентным числом. Алгебраически, если

$n=\sum _{i=1}^{c+1}\varphi ^{i}(n),$

где

$\varphi ^{i}(n)=\left\{{\begin{matrix}\varphi (n),i=1\\\varphi (\varphi ^{i-1}(n)),i\neq 1\end{matrix}}\right.$

рекурсивная итерированная функция Эйлера, а c — это целое число, такое, что

$\displaystyle \varphi ^{c}(n)=2,$

то n является совершенным тотиентным числом.

Совершенное тотиентное число по определению является нечётным.

Несколько первых совершенных тотиентных чисел

3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, … (последовательность A082897 в 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

Несколько чисел вида $a(n)=2^{2^{n}}-1$ (последовательность A051179 в OEIS), такие, как 255, 65 535, 4 294 967 295 и 18 446 744 073 709 551 615, являются совершенными тотиентными числами, и, кроме того, являются максимальными беззнаковыми целыми числами соответственно 8-, 16-, 32- и 64-битных переменных. Более ранние числа 3 и 15 из той же последовательности также являются совершенными тотиентными числами.

Степени тройки

Можно заметить, что многие совершенные тотиентные числа делятся на 3. Фактически, число 4375 является наименьшим совершенным тотиентным числом, не делящимся на 3. Все степени 3 являются совершенными тотиентными числами, что можно показать по индукции, используя факт

$\displaystyle \varphi (3^{k})=\varphi (2\times 3^{k})=2\times 3^{k-1}.$

Венкатараман (1975) нашёл другое семейство совершенных тотиентных чисел — если p = 4×3^k+1 простое, то 3p совершенное тотиентное число. Значения k, ведущие к совершенным тотиентным числам этим способом:

0, 1, 2, 3, 6, 14, 15, 39, 201, 249, 1005, 1254, 1635, … (последовательность A005537 в OEIS).

Более обще, если p является простым числом, большим 3, и 3p является совершенным тотиентным числом, то p ≡ 1 (mod 4). Не все p этого вида приводят к совершенным тотиентным числам. Так, 51 совершенным тотиентным числом не является. Иануччи, Денг и Коэн показали, что если 9p является совершенным тотиентным числом, то p является простым и имеет одну из трёх форм, перечисленных в статье. Неизвестно, имеются ли совершенные тотиентные числа вида 3^kp, где p является простым и k > 3.

Литература

Замечание: Оригинал статьи включает материал из статьи Perfect Totient Number с сайта PlanetMath c лицензией Creative Commons Attribution-ShareAlike 3.0 Unported