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

Высококототиентное число — это положительное целое число 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, ...