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

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

x − φ(x) = k,
 чем для любого другого числа между 1 и k. Здесь φ — функцияЭйлера. Существует бесконечно много решений этого уравнения для k= 1, так что это значение из рассмотрения удаляется. Несколько первыхвысококототиентных чисел:

 2, 4, 8, 23, 35, 47, 59, 63, 83, 89, 113, 119, 167, 209, 269, 299, 329,389, 419, 509, 629, 659, 779, 839, 1049, 1169, 1259, 1469, 1649, 1679,1889, ...
 Существует много нечётных высококототиентных чисел. Фактически, послечисла 8, все перечисленные выше числа нечётны, а после 167 всеперечисленные выше числа сравнимы с 29 по модулю 30.
 Концепция в чём-то аналогична концепции . Так же как существуетбесконечно много высокосоставных чисел, существует бесконечно многовысококототиентных чисел. Но вычисления более сложны, посколькуфакторизация целых чисел усложняется по мере роста числа.

Пример


Кототиент числа x определяется как x –φ(x) (значение функции Эйлера φ(x) называется тотиентом),т.е. число положительных чисел, меньших либо равных x и имеющихпо меньшей мере один общий делитель с x. Например, кототиентчисла 6 равен 4, поскольку следующие 4 положительных числа имеют общиепростые множители с 6, это 2, 3, 4 и 6. Кототиент числа 8 также равен 4,на этот раз с числами 2, 4, 6 и 8. Это в точности два числа, имеющиекототиент 4. Имеется меньше чисел, имеющих кототиент 2 и 3 (по одномучислу), так что 4 является высококототиентным числом.

k (высокототиентные k выделены жирным)0123456789101112131415161718192021222324252627282930
Число решений уравнения x – φ(\emphx) = k111211232023212331313144304143

Простые


 Первые несколько высококототиентных чисел, являющихся простыми

 2, 23, 47, 59, 83, 89, 113, 167, 269, 389, 419, 509, 659, 839, 1049,1259, 1889, 2099, 2309, 2729, 3359, 3989, 4289, 4409, 5879, 6089, 6719,9029, 9239, ...