160425(3)

Ruby

Number of partitions of n into parts that are powers of 3

オンライン整数列大辞典の
A062051（http://oeis.org/A062051/list）
と比較し、答え合わせしてみる。

def A062051(n)
  ps = Array.new(n + 1){0}
  ps[0] = 1
  return ps if n == 0
  ary = (0..Math.log(n, 3).to_i).map{|i| 3 ** i}
  ary.each{|num|
    (num..n).each{|i|
      ps[i] += ps[i - num]
    }
  }
  ps
end
ary = A062051(69)

# OEIS A062051のデータ
ary0 =
[1,1,1,2,2,2,3,3,3,5,5,5,7,7,7,9,9,9,12,12,12,15,
 15,15,18,18,18,23,23,23,28,28,28,33,33,33,40,40,
 40,47,47,47,54,54,54,63,63,63,72,72,72,81,81,81,
 93,93,93,105,105,105,117,117,117,132,132,132,147,
 147,147,162]
# 一致の確認
p ary == ary0