151228(2)

Ruby

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

A003107(10 ** i) を求めてみた。

# 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

N = 7
ary = A003107(10 ** N)
(0..N).each{|i| p ary[10 ** i]}

出力結果
1
22
97075
1013742289697
79170701411977377424244
83067459628701292838054798041549436000
1637462026740340833729644375485392457947071538846888312979
752766222145261316633107509392508342873807143453511899117237733049220345746591279