PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 21 / 友愛数

d(n) を n の真の約数の和と定義する。真の約数とは n 自身以外の約数のことである。

d(a) = b かつ d(b) = a(a ≠ b)が成立するとき,「a と b は友愛数である」という。

たとえば 220の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である。
284の約数は 1, 2, 4, 71, 142 なので d(284) = 220 であり,220と284は友愛数である。

10000未満の友愛数の和を求めよ。

Problem 21 - Project Euler

真の約数の和は DivisorSigma[1,n]-n。これを F[n] とおくと,n が友愛数のペアの一員となる条件は次のようになります。

 F(F(n))=n  かつ  F(n) \ne n

この条件をみたす数を抽出して,和をとればOKなはず。

ただし,問題文がちょっと曖昧です。友愛数とは普通,2数の組のことです。和を求めるにあたって,友愛数の片割れが10^4を超える場合はカウントしないのでしょうか? そんな数はなかったのですが,一応,含めないことにして計算しました。