Высокототиентное число

Высокототиентное число — это целое число k, имеющее больше решений уравнения

x − φ(x) = k,

чем для любого другого числа, меньшего k. Здесь φ — функция Эйлера, значение функции называется тотиентом. Несколько первых высокототиентных чисел: 1, 2, 4, 8, 12, 24, 48, 72, 144, 240, 432, 480, 576, 720, 1152, 1440 (последовательность A097942 в OEIS), с 1, 3, 4, 5, 6, 10, 11, 17, 21, 31, 34, 37, 38, 49, 54 и 72 решениями соответственно. Последовательность высокототиентных чисел является подмножеством наименьших чисел k с точно n решениями уравнения φ(x) = k

Тотиентом числа x, с разложением $x=\underset{i}{\prod <!--\; \prod \; -->}{p}_i^{e_i}$$x=\prod _{i}p_{i}^{e_{i}}$, является произведение:

$\mathrm{\varphi <!--\; \varphi \; -->}(x)=\underset{i}{\prod <!--\; \prod \; -->}(p_i-<!--\; -\; -->1)p_i^{e_i-<!--\; -\; -->1}.$$\phi (x)=\prod _{i}(p_{i}-1)p_{i}^{e_{i}-1}.$

Таким образом, высокототиентное число — это число, которое имеет больше путей представления в виде произведения этого вида, чем любое меньшее число.

Концепция чем-то аналогична концепции высокосоставных чисел^[en]. Число 1 является единственным нечётным высокоставным числом, и точно так же 1 является единственным нечётным высокототиентным числом (на самом деле, все нечётные числа нетотиентны). И так же, как существует бесконечно много высокосоставных чисел, существует бесконечно много высокототиентных чисел, хотя найти высокототиентные числа труднее, чем найти высокосоставные, поскольку требует факторизации на простые множители, что становится крайне сложно по мере роста чисел.