ProjectEuler 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 である.

それでは10000未満の友愛数の和を求めよ.
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2021

回答

第12問と同じく、エラストテネスの篩を少し修正して、約数の和を返す関数を作成した。
http://qiita.com/cof/items/222d51c09b043da974af

def factor_sum_seq(max):
  dl = [0] + [1]*(max-1)
  seq = range(max) 
  for i in seq[2:]:
    for j in seq[i*2::i]:
      dl[j] += i
  return dl

上記関数は、次のとおりに動く。(3/2 説明を修正)

dl[]: 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
i=2 : 1  1  1  3  1  3  1  3  1  3  1  3  1  3  1  3  1  3  1  3 
    #2の倍数(2自身を除く)に2が加えられる。
i=3 : 1  1  1  3  1  6  1  3  4  3  1  6  1  3  4  3  1  6  1  3
    #3の倍数(3自身を除く)に3が加えられる。
i=4 : 1  1  1  3  1  6  1  7  4  3  1 10  1  3  4  7  1  6  1  7
    #4の倍数(4自身を除く)に4が加えられる。

iを所定の数の平方根まで動かすことにより、各iの倍数、換言すれば各iを真の約数として持つ数に、当該約数各i加えられるので、真の約数の和が適切に算出される。

これを利用して次のように求めた。

def cof():
  MAX = 10**4
  seq = range(MAX)
  dl = factor_sum_seq(MAX)
  ans=0
  for i in seq:
    if dl[i]<MAX and i == dl[dl[i]] and i != dl[i]:
      ans += i

  print ans

cof()