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

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

x − φ(x) = k,

чем для любого другого числа между 1 и k. Здесь φ — функция Эйлера. Существует бесконечно много решений этого уравнения для k = 1, так что это значение из рассмотрения удаляется. Несколько первых высококототиентных чисел:[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, ... (последовательность A100827 в OEIS)

Существует много нечётных высококототиентных чисел. Фактически, после числа 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 является высококототиентным числом.

(последовательность A063740 в OEIS)

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

Простые

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

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, ... (последовательность A105440 в OEIS)

Примечания
  1. Sloane's A100827 : Highly cototient numbers Энциклопедия целочисленных последовательностей.
  2. Sloane's A105440: Highly cototient numbers that are prime Энциклопедия целочисленных последовательностей.

Литература
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.