オイラーの関数とメビウスの関数を計算

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 の関数を計算しているコア部分は同じです。

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);

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);

The Life

オイラーの関数とメビウスの関数を計算

使用したプログラム

関連記事

この記事を見た人は次の記事も見ています

A Life Summary of an Gypsy