高互补欧拉商数

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

x - φ(x) = k

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

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

例子

$x$的互补欧拉商数（cototient）定义为$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	使得$k-\phi (k)=n$的k	使得$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, 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）

相关条目

• 高欧拉商数