151109(2)

Ruby


Number of partitions of n into squares

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

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

def A001156(n)
  squares = (1..Math.sqrt(n).to_i).map{|i| i * i}
  ps = Array.new(n + 1){0}
  ps[0] = 1
  squares.each{|num|
    (num..n).each{|i|
      ps[i] += ps[i - num]
    }
  }
  ps
end
ary = A001156(67)

# OEIS A001156のデータ
ary0 =
[1,1,1,1,2,2,2,2,3,4,4,4,5,6,6,6,8,9,10,10,12,13,
 14,14,16,19,20,21,23,26,27,28,31,34,37,38,43,46,
 49,50,55,60,63,66,71,78,81,84,90,98,104,107,116,
 124,132,135,144,154,163,169,178,192,201,209,220,
 235,247,256]
# 一致の確認
p ary == ary0