高互补欧拉商数

高互补欧拉商数（highly cototient number）k是有以下性质，大于1的正整数：使以下方程式有多个解

x - φ(x) = k

其中φ是欧拉函数，而且若k用其他较小的整数代入时，解的个数都会比刚刚的个数要少。若k=1时，上式会有无穷多组解，因此在定义上，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, ... （OEIS数列A100827）

许多高互补欧拉商数是奇数，大于8的高互补欧拉商数都是奇数，大于167的高互补欧拉商数都是29 mod 30的数^{[来源请求]}。

高互补欧拉商数的概念类似高合成数。高合成数有无限多个，而高互补欧拉商数也有无限多个。但数字越大，要进行整数分解也就越难，因此判断高互补欧拉商数也越难。

例子

${\displaystyle x}$的互补欧拉商数（cototient）定义为${\displaystyle x-\phi (x)}$，也就是小于等于此数的正整数中，和此数至少有一个共同质因数（即不互质）的正整数。例如6的互补欧拉商数是4，因为有4个小于等于6的正整数和6有共同的质因数：2, 3, 4, 6，因此6的互补欧拉商数是4。只有二个整数（6和8）的互补欧拉商数是4。而互补欧拉商数是2和3的整数都不到2个，因此4是高互补欧拉商数。

（OEIS数列A063740）

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

n	使得${\displaystyle k-\phi (k)=n}$的k	使得${\displaystyle k-\phi (k)=n}$的k的个数 （OEIS数列A063740）
0	1	1
1	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ... （所有的质数）	∞
2	4	1
3	9	1
4	6, 8	2
5	25	1
6	10	1
7	15, 49	2
8	12, 14, 16	3
9	21, 27	2
10		0
11	35, 121	2
12	18, 20, 22	3
13	33, 169	2
14	26	1
15	39, 55	2
16	24, 28, 32	3
17	65, 77, 289	3
18	34	1
19	51, 91, 361	3
20	38	1
21	45, 57, 85	3
22	30	1
23	95, 119, 143, 529	4
24	36, 40, 44, 46	4
25	69, 125, 133	3
26		0
27	63, 81, 115, 187	4
28	52	1
29	161, 209, 221, 841	4
30	42, 50, 58	3
31	87, 247, 961	3
32	48, 56, 62, 64	4
33	93, 145, 253	3
34		0
35	75, 155, 203, 299, 323	5
36	54, 68	2
37	217, 1369	2
38	74	1
39	99, 111, 319, 391	4
40	76	1
41	185, 341, 377, 437, 1681	5
42	82	1
43	123, 259, 403, 1849	4
44	60, 86	2
45	117, 129, 205, 493	4
46	66, 70	2
47	215, 287, 407, 527, 551, 2209	6
48	72, 80, 88, 92, 94	5
49	141, 301, 343, 481, 589	5
50		0

质数

高互补欧拉商数中，头几个是质数的是^[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, ... （OEIS数列A105440）

相关条目

• 高欧拉商数

参考资料

1. Sloane, N.J.A. (编). Sequence A100827 (Highly cototient numbers). The On-Line Encyclopedia of Integer Sequences. OEIS Foundation..
2. Sloane, N.J.A. (编). Sequence A105440 (Highly cototient numbers that are prime). The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.