160425(2)

Ruby

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

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

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

# OEIS A018819のデータ
ary0 =
[1,1,2,2,4,4,6,6,10,10,14,14,20,20,26,26,36,36,46,
 46,60,60,74,74,94,94,114,114,140,140,166,166,202,
 202,238,238,284,284,330,330,390,390,450,450,524,
 524,598,598,692,692,786,786,900,900,1014,1014,
 1154,1154,1294,1294]
# 一致の確認
p ary == ary0