PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 153 / ガウス整数の調べ上げ

ガウス整数とは a と b がともに整数の複素数 a + bi のことである。普通の整数もガウス整数である (b = 0 のケース)。
b ≠ 0 のガウス整数と区別するために,普通の整数を「有理整数」と呼ぶことにする。

有理整数 n をあるガウス整数で割った結果がガウス整数である場合,そのガウス整数は約数と呼ばれる。例として 5/(1+2i) は以下のように簡略化できる。

f:id:variee:20170602203321g:plain

1+2i は5の約数である。1+i は5の約数でないことに注意。

f:id:variee:20170602203437g:plain

ガウス整数 a+bi が有理整数 n の約数ならば,その共役複素数 a-bi もまた n の約数となる。

5は実部が正となる約数を
{1, 1+2i, 1-2i, 2+i, 2-i, 5}
の6個持つ。以下に最初の5個の正の有理整数の約数の表を示す。

n実部が正のガウス整数の約数約数の和 s(n)
111
21, 1+i, 1-i, 25
31, 34
41, 1+i, 1-i, 2, 2+2i, 2-2i,413
51, 1+2i, 1-2i, 2+i, 2-i, 512

正の実部を持つ約数について
f:id:variee:20170602203623g:plain

1 ≤ n ≤ 10^5 について,∑s(n) = 17924657155 となる。

1 ≤ n ≤ 10^8 について,∑s(n) を求めよ。

Problem 153 - Project Euler


Mathematica はガウス整数の範囲で約数を求められますが,虚部が正のものしか返してくれません。

和を2倍した後,ダブリである有理整数の和を引くことで対処しました。30分以上かかりました。

a+bI とおいて数える解法も考えてみたのですが,微妙に数があわず*1,解答にはいたっていません。いつか再挑戦します。

*1:0.4%ずれる