Problem 153
の編集
https://odz.sakura.ne.jp/projecteuler/?Problem+153
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
(no template pages)
*[[Problem 153:http://projecteuler.net/problem=153]] 「ガウス整数の調べ上げ」 [#u6c62b84] 方程式 &tex{x^{2} = -1}; が実数 x について解が存在しないことは誰もが知っている. ~ しかし, 虚数 i を導入することで方程式は2つの解 x = i , x = -i を持つ. ~ さらに, 方程式 &tex{(x - 3)^{2} = -4}; は二つの複素数の解 x = 3+2i , x = 3-2i を持つ. ~ x = 3+2i と x = 3-2i は他方の共役複素数と呼ばれる. ~ a + bi という形の数は複素数と呼ばれる. ~ 一般に, a + bi と a - bi は他方の共役複素数である. ガウス整数とはaとbがともに整数である複素数 a + bi のことである. ~ 普通の整数はまた, ガウス整数である. (b = 0 のケース)~ b ≠ 0 のガウス整数と区別するために, 普通の整数を"有理整数"と呼ぶことにする. ~ 有理整数 n をあるガウス整数で割った結果がガウス整数である場合, そのガウス整数は約数と呼ばれる. ~ 例として, 5 を 1+2i で割ると, 5 / (1 + 2&tex{i};) は以下のように簡略化できる. ~ 分子と分母に1+2iの共役複素数(1-2i)を掛ける. ~ 結果は, 5 / (1 + 2i) = 5 / (1 + 2i) * (1 - 2i) / (1 - 2i) = (5(1 - 2i)) / (1 - (2i)^2) = (5(1 - 2i)) / (1 - (-4)) = (5(1 - 2i)) / 5 = 1 - 2i となる. ~ よって, 1+2i は 5 の約数である. ~ 1+i は 5/(1 + i) = 5/2 - 5/2i なので 5 の約数でないことに注意. ~ さらに, ガウス整数(a+bi)が有理整数 n の約数ならば, その共役複素数(a-bi)もまた n の約数となることにも注意. 実際, 5 は実部が正となる約数を, {1, 1 + 2i, 1 - 2i, 2 + i, 2 - i, 5}の6個持つ. ~ 以下に最初の5個の正の有理整数の約数の表を示す. |n|実部が正のガウス整数の約数|約数の和 s(n)| |1|1|1| |2|1, 1+i, 1-i, 2|5| |3|1, 3|4| |4|1, 1+i, 1-i, 2, 2+2i, 2-2i,4|13| |5|1, 1+2i, 1-2i, 2+i, 2-i, 5|12| 正の実部を持つ約数について, Σ &tex{{}_{n = 1}^{5}}; s(n) = 35 を得る. 1 ≤ n ≤ &tex{10^{5}}; について, ∑s(n) = 17924657155 となる. 1 ≤ n ≤ &tex{10^{8}}; について, ∑s(n) を求めよ.
タイムスタンプを変更しない
*[[Problem 153:http://projecteuler.net/problem=153]] 「ガウス整数の調べ上げ」 [#u6c62b84] 方程式 &tex{x^{2} = -1}; が実数 x について解が存在しないことは誰もが知っている. ~ しかし, 虚数 i を導入することで方程式は2つの解 x = i , x = -i を持つ. ~ さらに, 方程式 &tex{(x - 3)^{2} = -4}; は二つの複素数の解 x = 3+2i , x = 3-2i を持つ. ~ x = 3+2i と x = 3-2i は他方の共役複素数と呼ばれる. ~ a + bi という形の数は複素数と呼ばれる. ~ 一般に, a + bi と a - bi は他方の共役複素数である. ガウス整数とはaとbがともに整数である複素数 a + bi のことである. ~ 普通の整数はまた, ガウス整数である. (b = 0 のケース)~ b ≠ 0 のガウス整数と区別するために, 普通の整数を"有理整数"と呼ぶことにする. ~ 有理整数 n をあるガウス整数で割った結果がガウス整数である場合, そのガウス整数は約数と呼ばれる. ~ 例として, 5 を 1+2i で割ると, 5 / (1 + 2&tex{i};) は以下のように簡略化できる. ~ 分子と分母に1+2iの共役複素数(1-2i)を掛ける. ~ 結果は, 5 / (1 + 2i) = 5 / (1 + 2i) * (1 - 2i) / (1 - 2i) = (5(1 - 2i)) / (1 - (2i)^2) = (5(1 - 2i)) / (1 - (-4)) = (5(1 - 2i)) / 5 = 1 - 2i となる. ~ よって, 1+2i は 5 の約数である. ~ 1+i は 5/(1 + i) = 5/2 - 5/2i なので 5 の約数でないことに注意. ~ さらに, ガウス整数(a+bi)が有理整数 n の約数ならば, その共役複素数(a-bi)もまた n の約数となることにも注意. 実際, 5 は実部が正となる約数を, {1, 1 + 2i, 1 - 2i, 2 + i, 2 - i, 5}の6個持つ. ~ 以下に最初の5個の正の有理整数の約数の表を示す. |n|実部が正のガウス整数の約数|約数の和 s(n)| |1|1|1| |2|1, 1+i, 1-i, 2|5| |3|1, 3|4| |4|1, 1+i, 1-i, 2, 2+2i, 2-2i,4|13| |5|1, 1+2i, 1-2i, 2+i, 2-i, 5|12| 正の実部を持つ約数について, Σ &tex{{}_{n = 1}^{5}}; s(n) = 35 を得る. 1 ≤ n ≤ &tex{10^{5}}; について, ∑s(n) = 17924657155 となる. 1 ≤ n ≤ &tex{10^{8}}; について, ∑s(n) を求めよ.
テキスト整形のルールを表示する
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
