跳转到内容

高欧拉商数

维基百科,自由的百科全书

高欧拉商数highly totient numberk是有以下性质,大于1的正整数:使以下方程式有多个解

φ(x) = k

其中φ是欧拉函数,而且若k用其他较小的整数代入时,解的个数都会比刚刚的个数要少。

例如方程式φ(x) = k,在k=1,2,3,4,5,6,7,8时,分别有2,3,0,4,0,4,0,5个解,φ(x) = 8有5个解,若代入小于8的数值,解都少于5个,因此8是高欧拉商数。

头几个高欧拉商数是:

1, 2, 4, 8, 12, 24, 48, 72, 144, 240, 432, 480, 576, 720, 1152, 1440 (OEIS数列A097942).

分别使上述方程有1, 3, 4, 5, 6, 10, 11, 17, 21, 31, 34, 37, 38, 49, 54及72个解。若将使φ(x) = k分别恰有0个解、1个解、2个解……的最小k值组成一个数列,则高欧拉商数会是此数列的一个子集[1]。例如8为高欧拉商数,φ(x) = 8有5个解,表示任何小于8的整数都无法使φ(x) = k有5个解,因此8是使φ(x) = k有5个解的最小k值。

若x的质因数分解为,其欧拉商数为以下的乘积:

因此,高欧拉商数和较小的整数相比,高欧拉商数可以表示为更多种以上式表示的乘积。

高欧拉商数的概念有点类似高合成数;1既是高合成数中唯一的奇数,也是高欧拉商数中唯一的奇数(其实1是欧拉函数值域中唯一的奇数)。而且高欧拉商数和高合成数都有无限多个,不过随著数字的增加,要找到高欧拉商数也就越来困难,因为欧拉商数和质因数分解有关,数字越大,就越难进行质因数分解。

举例

[编辑]

有五个整数(15, 16, 20, 24和30)的欧拉商数是8。比8小的整数中,没有哪一个是五个整数的欧拉商数。因此8是高欧拉商数。

[编辑]
n 使k值(OEIS数列A032447 使k的个数(OEIS数列A014197
0 0
1 1, 2 2
2 3, 4, 6 3
3 0
4 5, 8, 10, 12 4
5 0
6 7, 9, 14, 18 4
7 0
8 15, 16, 20, 24, 30 5
9 0
10 11, 22 2
11 0
12 13, 21, 26, 28, 36, 42 6
13 0
14 0
15 0
16 17, 32, 34, 40, 48, 60 6
17 0
18 19, 27, 38, 54 4
19 0
20 25, 33, 44, 50, 66 5
21 0
22 23, 46 2
23 0
24 35, 39, 45, 52, 56, 70, 72, 78, 84, 90 10
25 0
26 0
27 0
28 29, 58 2
29 0
30 31, 62 2
31 0
32 51, 64, 68, 80, 96, 102, 120 7
33 0
34 0
35 0
36 37, 57, 63, 74, 76, 108, 114, 126 8
37 0
38 0
39 0
40 41, 55, 75, 82, 88, 100, 110, 132, 150 9
41 0
42 43, 49, 86, 98 4
43 0
44 69, 92, 138 3
45 0
46 47, 94 2
47 0
48 65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210 11
49 0
50 0

相关条目

[编辑]

相关条目

[编辑]

参考资料

[编辑]