Высококототиентное число — это положительное целое число 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.
Концепция в чём-то аналогична концепции высокосоставных чисел[en]. Так же как существует бесконечно много высокосоставных чисел, существует бесконечно много высококототиентных чисел. Но вычисления более сложны, поскольку факторизация целых чисел усложняется по мере роста числа.
Пример
Кототиент числа 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]
Примечания
Литература
 | |
|---|---|
Классы простых чисел | |
|---|---|
| По формуле | Ферма (22n + 1) • Мерсенна (2p ? 1) • Двойные Мерсенна (22p?1 ? 1) • Вагстафа (2p + 1)/3 •
Прота (k•2n + 1) • Факториальное (n! ± 1) • Праймориальное (pn# ± 1) • Евклида (pn# + 1) • Пифагора (4n + 1) • Пьерпонта (2u•3v + 1) • Квартановое (x4 + y4) • Солинаса (2a ± 2b ± 1) • Каллена (n•2n + 1) • Вудала (n•2n ? 1) • Кубические (x3 ? y3)/(x ? y) • Кэрола (2n ? 1)2 ? 2 • Кении (2n + 1)2 ? 2 • Лейланда (xy + yx) • Сабита (3•2n ? 1) • Миллса (floor(A3n)) |
| Последовательности | |
| По свойствам | |
| Зависящие от системы счисления | Довольное • Диэдральное • Палиндромное • Еотсорп • Репьюниты (10n ? 1)/9 • Перестановочное • Кольцевое • Усекаемое • Стробограмматики • Минимальное • Слабо простые • Полно-повторное • Уникальное • Первобытное • Самопорождённые • Смарандаша — Веллена |
| Модели | Близнецы (p, p + 2) • Цепочка близнецов (n ? 1, n + 1, 2n ? 1, 2n + 1, …) • Тройка простых (p, p + 2 или p + 4, p + 6) • Четвёрка простых (p, p + 2, p + 6, p + 8) • k?Кортеж • Родственные (p, p + 4) • Отличающиеся на 6 (p, p + 6) • Чена • Софи Жермен (p, 2p + 1) • Цепи Куннингама (p, 2p ± 1, …) • Безопасные (p, (p ? 1)/2) • Прогрессии (p + a•n, n = 0, 1, …) • Сбалансированные (последовательные p ? n, p, p + n) |
| По размеру | Титаническое (1.000+ знаков) • Гигантское (10.000+) • Мегапростое (1.000.000+) • Наибольшее известное |
| Комплексные числа | |
| Составные числа | |
| Связанные разделы | |
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .