代数系入門(松坂和夫) の 第1章 §8 問題1 の解答です。
Euler の関数 と Möbius の関数 を 1から100の数について計算して表にするというものです。
自分で手を動かしてやるときっと理解も深まると思いましたが、気の遠くなる作業が見込まれたため、プログラムを作って計算しました。
数 | Euler | Möbius |
---|---|---|
1 | 1 | 1 |
2 | 1 | -1 |
3 | 2 | -1 |
4 | 2 | 0 |
5 | 4 | -1 |
6 | 2 | 1 |
7 | 6 | -1 |
8 | 4 | 0 |
9 | 6 | 0 |
10 | 4 | 1 |
11 | 10 | -1 |
12 | 4 | 0 |
13 | 12 | -1 |
14 | 6 | 1 |
15 | 8 | 1 |
16 | 8 | 0 |
17 | 16 | -1 |
18 | 6 | 0 |
19 | 18 | -1 |
20 | 8 | 0 |
21 | 12 | 1 |
22 | 10 | 1 |
23 | 22 | -1 |
24 | 8 | 0 |
25 | 20 | 0 |
26 | 12 | 1 |
27 | 18 | 0 |
28 | 12 | 0 |
29 | 28 | -1 |
30 | 8 | -1 |
31 | 30 | -1 |
32 | 16 | 0 |
33 | 20 | 1 |
34 | 16 | 1 |
35 | 24 | 1 |
36 | 12 | 0 |
37 | 36 | -1 |
38 | 18 | 1 |
39 | 24 | 1 |
40 | 16 | 0 |
41 | 40 | -1 |
42 | 12 | -1 |
43 | 42 | -1 |
44 | 20 | 0 |
45 | 24 | 0 |
46 | 22 | 1 |
47 | 46 | -1 |
48 | 16 | 0 |
49 | 42 | 0 |
50 | 20 | 0 |
51 | 32 | 1 |
52 | 24 | 0 |
53 | 52 | -1 |
54 | 18 | 0 |
55 | 40 | 1 |
56 | 24 | 0 |
57 | 36 | 1 |
58 | 28 | 1 |
59 | 58 | -1 |
60 | 16 | 0 |
61 | 60 | -1 |
62 | 30 | 1 |
63 | 36 | 0 |
64 | 32 | 0 |
65 | 48 | 1 |
66 | 20 | -1 |
67 | 66 | -1 |
68 | 32 | 0 |
69 | 44 | 1 |
70 | 24 | -1 |
71 | 70 | -1 |
72 | 24 | 0 |
73 | 72 | -1 |
74 | 36 | 1 |
75 | 40 | 0 |
76 | 36 | 0 |
77 | 60 | 1 |
78 | 24 | -1 |
79 | 78 | -1 |
80 | 32 | 0 |
81 | 54 | 0 |
82 | 40 | 1 |
83 | 82 | -1 |
84 | 24 | 0 |
85 | 64 | 1 |
86 | 42 | 1 |
87 | 56 | 1 |
88 | 40 | 0 |
89 | 88 | -1 |
90 | 24 | 0 |
91 | 72 | 1 |
92 | 44 | 0 |
93 | 60 | 1 |
94 | 46 | 1 |
95 | 72 | 1 |
96 | 32 | 0 |
97 | 96 | -1 |
98 | 42 | 0 |
99 | 60 | 0 |
100 | 40 | 0 |
使用したプログラム
昔作ったプログラムに少し手を加えたものです。 下のコードを jsdo.it で公開しています。
実際に使ったプログラムと少し異なりますが、 Euler の関数 と Möbius の関数 を計算しているコア部分は同じです。
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
function getPrimeFactorArray(plusNumber) { var targetNumber = plusNumber; var count = 0; var elements = new Array(); for (var i = 0, divisor = 2; divisor <= targetNumber / divisor; i++, divisor = 2 * i + 1) { while (1) { if (targetNumber % divisor === 0) { targetNumber /= divisor; count++; } else { if (count != 0) { elements.push([divisor, count]); count = 0; } break; } } } if (targetNumber != 1) { elements.push([targetNumber, 1]); } return elements; } function getPrimeFactorDecomposition(elements) { var resultString = ''; for (var i = 0; i < elements.length; i++) { resultString += ('*' + elements[i][0].toString()); if (elements[i][1] != 1) { resultString += ('^' + elements[i][1].toString()); } } return resultString.substr(1); } function getDivisorsCount(elements) { var resultCount = 1; for (var i = 0; i < elements.length; i++) { resultCount *= (1 + elements[i][1]); } return resultCount; } function calcEuler(elements) { var result = 1; for (var i = 0; i < elements.length; ++i) { result *= Math.pow(elements[i][0], elements[i][1]) - Math.pow(elements[i][0], elements[i][1] - 1); } return result; } function calcMobius(elements) { for (var i = 0; i < elements.length; ++i) { if (elements[i][1] > 1) return 0; } return Math.pow(-1, elements.length); } function createTag(tagName, text) { var tag = document.createElement(tagName); tag.appendChild(document.createTextNode(text)); return tag; } function createTd(text) { return createTag('td', text); } function createTh(text) { return createTag('th', text); } var tableTag = document.createElement('table'); var trTag = document.createElement('tr'); trTag.appendChild(createTh('Number')); trTag.appendChild(createTh('Decomp')); trTag.appendChild(createTh('Euler')); trTag.appendChild(createTh('Mu00f6bius')); tableTag.appendChild(trTag); for (var i = 1; i <= 100; ++i) { var elements = getPrimeFactorArray(i); var e = calcEuler(elements); var m = calcMobius(elements); var trTag = document.createElement('tr'); trTag.appendChild(createTd(i.toString())); trTag.appendChild(createTd(getPrimeFactorDecomposition(elements))); trTag.appendChild(createTd(e)); trTag.appendChild(createTd(m)); tableTag.appendChild(trTag); } document.getElementById('result').appendChild(tableTag); |