高互補歐拉商數

高互補歐拉商數highly cototient numberk是有以下性質,大於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的數[來源請求]

高互補歐拉商數的概念類似高合成數。高合成數有無限多個,而高互補歐拉商數也有無限多個。但數字越大,要進行整數分解也就越難,因此判斷高互補歐拉商數也越難。

例子

 的互補歐拉商數(cototient)定義為 ,也就是小於等於此數的正整數中,和此數至少有一個共同質因數(即不互質)的正整數。例如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 使得 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

相關條目

參考資料