高歐拉商數

高歐拉商數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

相關條目

相關條目

参考资料