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

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

  3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, ... .
  Например, начиная с 327 вычисляем φ(327) = 216, φ(216) = 72, φ(72) = 24, φ(24) = 8, φ(8) = 4, φ(4) = 2, φ(2) = 1, получаем 216 + 72 + 24 + 8 + 4 + 2 + 1 = 327.
 4294967295 является совершенным тотиентным числом, которое является также максимальным беззнаковым целым числом во многих современных компьютерах.

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


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

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

  0, 1, 2, 3, 6, 14, 15, 39, 201, 249, 1005, 1254, 1635, ... .
  Более обще, если p является простым числом, большим 3, и 3p является совершенным тотиентным числом, то p ≡ 1 (mod 4). Не все p этого вида приводят к совершенным тотиентным числам. Так, 51 совершенным тотиентным числом не является. Иануччи, Денг и Коэн показали, что если 9p является совершенным тотиентным числом, то p является простым и имеет одну из трёх форм, перечисленных в статье. Неизвестно, имеются ли совершенные тотиентные числа вида 3kp, где p является простым и k \textgreater 3.