151227(6)

Ruby


Stern's diatomic series(3)

a(2n) = a(n), a(2n + 1) = a(n) + a(n + 1)
という性質を用いて、行列計算で求めてみた。
オンライン整数列大辞典の
A002487（http://oeis.org/A002487/list）
と比較し、答え合わせしてみる。

require 'matrix'

def f(n)
  return 0 if n == 0
  m = Matrix[[1, 0]]
  m0 = Matrix[[1, 0], [1, 1]]
  m1 = Matrix[[1, 1], [0, 1]]
  n.to_s(2).reverse[0..-2].split('').each{|i| i == '0' ? m *= m0 : m *= m1}
  (m * Vector.elements([1, 1]))[0]
end

def A002487(n)
  (0..n).map{|i| f(i)}
end
ary = A002487(91)

# OEIS A002487のデータ
ary0 =
[0,1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,3,8,5,7,
 2,7,5,8,3,7,4,5,1,6,5,9,4,11,7,10,3,11,8,13,5,12,
 7,9,2,9,7,12,5,13,8,11,3,10,7,11,4,9,5,6,1,7,6,11,
 5,14,9,13,4,15,11,18,7,17,10,13,3,14,11,19,8,21,
 13,18,5,17,12,19]
# 一致の確認
p ary == ary0