Меню
Главная
Случайная статья
Настройки
|
Высококототиентное число — это положительное целое число 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)
Примечания
- Sloane's A100827 : Highly cototient numbers Архивная копия от 18 октября 2017 на Wayback Machine Энциклопедия целочисленных последовательностей.
- Sloane's A105440: Highly cototient numbers that are prime Архивная копия от 19 апреля 2017 на Wayback Machine Энциклопедия целочисленных последовательностей.
Литература
|
|