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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Высококототиентное число — это положительное целое число 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 выделены жирным) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Число решений уравнения x – φ(x) = k 1 1 1 2 1 1 2 3 2 0 2 3 2 1 2 3 3 1 3 1 3 1 4 4 3 0 4 1 4 3

Первые несколько высококототиентных чисел, являющихся простыми[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)

Примечания

[править | править код]

Литература

[править | править код]