151109(4)

Ruby


Number of partitions of n into fourth powers

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

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

def A046042(n)
  fourth_powers = (1..(n ** (1.0 / 4)).to_i).map{|i| i * i * i * i}
  ps = Array.new(n + 1){0}
  ps[0] = 1
  fourth_powers.each{|num|
    (num..n).each{|i|
      ps[i] += ps[i - num]
    }
  }
  ps[1..-1]
end
ary = A046042(102)

# OEIS A046042のデータ
ary0 =
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,
 2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,
 4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,
 5,5,5,5,5,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,9,9,9,
 9,9,9]
# 一致の確認
p ary == ary0