高欧拉商数
高欧拉商数(highly totient number)k是有以下性质,大于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 |
相关条目
- ^ Sloane, N.J.A. (编). Sequence A097942 (Highly totient numbers: each number k on this list has more solutions to the equation phi(x) = k than any preceding k (where phi is Euler's totient function, A000010)). The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
- L. Havelock, A Few Observations on Totient and Cototient Valence from PlanetMath
相关条目
参考资料
- L. Havelock, A Few Observations on Totient and Cototient Valence from PlanetMath