151228

Ruby


p(n | 和因子はフィボナッチ数)(1)

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

# n以下のフィボナッチ数
def f_ary(n)
  a, b = 0, 1
  ary = [a]
  while b <= n
    ary << b
    a, b = b, b + a
  end
  ary
end

def A003107(n)
  ary = f_ary(n)[2..-1]
  ps = Array.new(n + 1){0}
  ps[0] = 1
  ary.each{|num|
    (num..n).each{|i|
      ps[i] += ps[i - num]
    }
  }
  ps
end
ary = A003107(53)

# OEIS A003107のデータ
ary0 =
[1,1,2,3,4,6,8,10,14,17,22,27,33,41,49,59,71,83,
 99,115,134,157,180,208,239,272,312,353,400,453,
 509,573,642,717,803,892,993,1102,1219,1350,1489,
 1640,1808,1983,2178,2386,2609,2854,3113,3393,3697,
 4017,4367,4737]
# 一致の確認
p ary == ary0