黄昏より暗きもの、血の流れより赤きもの

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

【Java】Project Euler 21 aの自分自身以外の約数の和がbに等しい(a,b)の組は幾つか?

Project Euler 問題21について

本日のProject Euler 21はある条件を満たす自然数(a,b)の組は幾つあるか?と言う問題。説明に自信は無いが、aの自分自身以外の約数の和がbに等しい(a,b)の組は幾つか?と言う問題である。


Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

問題意訳

d(n)はn以外の約数の和を表す。このとき二つの自然数a,bにおいて条件[aとbは異なりかつ、d(a)=b かつ d(b) = a を満たす(a,b)の組]をamicable numberと呼ぶ事とする。この時10,000より小さい整数における全てのamicable numberの和を求めよ。

背景知識:完全数(perfect number)

ここで本問題の背景知識を説明したい。まず本問題は完全数(perfect number)と関係深い。完全数とは自然数nにおいて、自分自身の約数の総和をd(n)がnに等しい。これを式で表すとd(n)=nを満たす整数nを完全数と言う。別の言う方をすれば自然数nの全ての約数の和が、元の自然数nの2倍となっているものと言う事もできる。

天下り的だが28を考えてみる。ここで28以外の約数の総和d(28) = 1+ 2 + 4 + 7 + 14 = 28より28は完全数となる。本問題ではd(a)=a が成立してしまうため、aとbは異なるという条件が追加されていると言う訳だ。そんな訳で本問題の解答を見てみよう。

Javaに依る解答

今回はJavaで解答を作成した。まずは別のクラス上で自然数nの約数の総和nを求めるメソッドPrimeNumberSum()を作成する。次にこれを1〜10000までの範囲で調べ、条件[aとbは異なりかつ、d(a)=b かつ d(b) = a を満たす(a,b)の組]を計算して行けば良い。具体的には以下のソースコードのように作業を続けていく。

実行結果

ソースコードの実行結果


x<-c(357,347,332,341,340)
> summary(x)
Min. 1st Qu. Median Mean 3rd Qu. Max.
332.0 340.0 341.0 343.4 347.0 357.0
> sqrt(var(x))
[1] 9.289779

上記結果を見ていると求める答えは31626macbook air(10.9)における5回実行時間を計測した時の標本平均は343.4[ms]、標本標準偏差は9.28[ms]と言う結果が得られた。約数の総和を求める上で整数を総当たりで計算しているため、
多分やらないけど、余裕があったらここの計算方法を見直したい。