150429

Ruby


p(n | 和因子は相異なる)

２、３日前コードを書いてみた。
オンライン整数列大辞典の
A000009（http://oeis.org/A000009/list）
と比較し、答え合わせしてみる。

n = 55

ps = Array.new(n + 1){0}

ps[0] = 1

i = n + 1

while i > 1

  # ここまでiが最小の因子

  i -= 1

  j = [(n + i) * (n - i + 1) / 2, n - i].min

  ary = ps.clone

  (0..j).each{|k|

    ary[k + i] += ps[k]

  }

  ps = ary

end

# OEIS A000009のデータ

ary0 =

[1,1,1,2,2,3,4,5,6,8,10,12,15,18,22,27,32,38,46,

 54,64,76,89,104,122,142,165,192,222,256,296,340,

 390,448,512,585,668,760,864,982,1113,1260,1426,

 1610,1816,2048,2304,2590,2910,3264,3658,4097,4582,

 5120,5718,6378]

# 一致の確認

p ps == ary0