Некототиент

В теории чисел нонкототиент — это положительное целое число n , которое не может быть выражено как разность между положительным целым числом m и числом взаимно простых целых чисел, лежащих ниже него. То есть, m − φ ( m ) = n , где φ обозначает функцию тотиента Эйлера , не имеет решения для  m . Кототиент числа n определяется как n − φ ( n ) , поэтому нонкототиент — это число, которое никогда не является кототиентом.

Предполагается, что все некототиенты четные. Это следует из модифицированной формы немного более сильной версии гипотезы Гольдбаха : если четное число n можно представить в виде суммы двух различных простых чисел p и q , то

$${\displaystyle {\begin{aligned}pq-\varphi (pq)&=pq-(p-1)(q-1)\\&=p+q-1\\&=n-1.\end{aligned}}}$$

Ожидается, что каждое четное число больше 6 является суммой двух различных простых чисел, поэтому, вероятно, ни одно нечетное число больше 5 не является некототиентом. Оставшиеся нечетные числа покрываются наблюдениями 1 = 2 – φ (2) , 3 = 9 – φ (9) и 5 ​​= 25 – φ (25) .

Для четных чисел можно показать$${\displaystyle {\begin{aligned}2pq-\varphi (2pq)&=2pq-(p-1)(q-1)\\&=pq+p+q-1\\&=(p+1)(q+1)-2\end{aligned}}}$$

Таким образом, все четные числа n, такие что n + 2, можно записать в виде ( p + 1)( q + 1), где p, q — простые числа, являются кототиентами.

Первые несколько некототиентов — это

10 , 26 , 34 , 50 , 52 , 58 , 86 , 100 , 116 , 122 , 130 , 134 , 146 , 154 , 170 , 172 , 186, 202, 206, 218, 222 , 232, 244, 260, 266, 268, 274, 290, 292, 298, 310, 326, 340, 344, 346, 362, 366, 372, 386, 394, 404, 412, 436, 466, 470, 474, 482, 490, ... (последовательность A005278 в OEIS )

Коэффициент n равен

0, 1, 1, 2, 1, 4, 1, 4, 3, 6, 1, 8, 1, 8, 7, 8, 1, 12, 1, 12, 9, 12, 1, 16, 5, 14, 9, 16, 1, 22, 1, 16, 13, 18, 11, 24, 1, 20, 15, 24, 1, 30, 1, 24, 21, 24, 1, 32, 7, 30, 19, 28, 1, 36, 15, 32, 21, 30, 1, 44, 1, 32, 27, 32, 17, 46, 1, 36, 25, 46, 1, 48, ... (последовательность A051953 в OEIS )

Наименьшее k, такое что коэффициент k равен n (начнем с n = 0 , 0, если такого k не существует)

1, 2, 4, 9, 6, 25, 10, 15, 12, 21, 0, 35, 18, 33, 26, 39, 24, 65, 34, 51, 38, 45, 30, 95, 36, 69, 0, 63, 52, 161, 42, 87, 48, 93, 0, 75, 54, 217, 74, 99, 76, 185, 82, 123, 60, 117, 66, 215, 72, 141, 0, ... (последовательность A063507 в OEIS )

Наибольшее k, такое что коэффициент k равен n (начнем с n = 0 , 0, если такого k не существует)

1, ∞, 4, 9, 8, 25, 10, 49, 16, 27, 0, 121, 22, 169, 26, 55, 32, 289, 34, 361, 38, 85, 30, 529, 46, 133, 0, 187, 52, 841, 58, 961, 64, 253, 0, 323, 68, 1369, 74, 391, 76, 1681, 82, 1849, 86, 493, 70, 2209, 94, 589, 0, ... (последовательность A063748 в OEIS )

Число k таких, что k − φ ( k ) равно n (начнем с n = 0 )

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, 3, 4, 3, 0, 5, 2, 2, 1, 4, 1, 5, 1, 4, 2, 4, 2, 6, 5, 5, 0, 3, 0, 6, 2, 4, 2, 5, 0, 7, 4, 3, 1, 8, 4, 6, 1, 3, 1, 5, 2, 7, 3, ... (последовательность A063740 в OEIS )

Эрдёш (1913–1996) и Серпинский (1882–1969) задались вопросом, существует ли бесконечно много некототиентов. На этот вопрос окончательно ответили утвердительно Браукин и Шинцель (1995), которые показали, что каждый член бесконечного семейства является примером (см. число Ризеля ). С тех пор другие бесконечные семейства, примерно той же формы, были даны Фламменкампом и Лукой (2000).${\displaystyle 2^{k}\cdot 509203}$

• Browkin, J.; Schinzel, A. (1995). «О целых числах, не имеющих формы n-φ(n)». Colloq. Math . 68 (1): 55– 58. doi : 10.4064/cm-68-1-55-58 . Zbl  0820.11003.
• Фламменкамп, А.; Лука, Ф. (2000). «Бесконечные семейства некототиентов». Colloq. Math . 86 (1): 37– 41. doi : 10.4064/cm-86-1-37-41 . Zbl  0965.11003.
• Гай, Ричард К. (2004). Нерешенные проблемы теории чисел (3-е изд.). Springer-Verlag . С.  138–142 . ISBN 978-0-387-20860-2. Збл  1058.11001.

• Определение некототиента из MathWorld