151109(3)

Ruby


Number of partitions of n into cubes

オンライン整数列大辞典の

A003108（http://oeis.org/A003108/list）
と比較し、答え合わせしてみる。

def A003108(n)
  cubes = (1..(n ** (1.0 / 3)).to_i).map{|i| i * i * i}
  ps = Array.new(n + 1){0}
  ps[0] = 1
  cubes.each{|num|
    (num..n).each{|i|
      ps[i] += ps[i - num]
    }
  }
  ps
end
ary = A003108(86)

# OEIS A003108のデータ
ary0 =
[1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,
 4,4,4,5,5,5,5,5,6,6,6,7,7,7,7,7,8,8,8,9,9,9,9,9,
 10,10,10,11,11,11,12,12,13,13,13,14,14,14,15,15,
 17,17,17,18,18,18,19,19,21,21,21,22,22,22,23,23,
 25,26,26,27,27,27,28]
# 一致の確認
p ary == ary0