151231

Ruby


p(n^2 | 和因子は平方数)

151109(2)分でp(n | 和因子は平方数) を求めたが、

そのn^2 番目について求めてみた。
オンライン整数列大辞典の
A037444（http://oeis.org/A037444/list）
と比較し、答え合わせしてみる。

def A037444(n)
  return [1] if n == 0
  ary = (1..n).map{|i| i * i}
  m = ary[-1]
  ps = Array.new(m + 1){0}
  ps[0] = 1
  a_ary = [1]
  ary.each{|num|
    (num..m).each{|i|
      ps[i] += ps[i - num]
    }
    a_ary << ps[num]
  }
  a_ary
end
ary = A037444(33)

# OEIS A037444のデータ
ary0 =
[1,1,2,4,8,19,43,98,220,504,1116,2468,5368,11592,
 24694,52170,108963,225644,462865,941528,1899244,
 3801227,7550473,14889455,29159061,56722410,
 109637563,210605770,402165159,763549779,
 1441686280,2707535748,5058654069,9404116777]
# 一致の確認
p ary == ary0