151226

Ruby

フィボナッチ数列、トリボナッチ数列、テトラナッチ数列、…(2)

行列計算で第10 ** i 項の下20桁を求めてみた。

require 'matrix'

def power(a, n, mod)
  return Matrix.I(a.row_size) if n == 0
  m = power(a, n >> 1, mod)
  m = (m * m).map{|i| i % mod}
  return m if n & 1 == 0
  (m * a).map{|i| i % mod}
end

def f(m, n)
  ary0 = Array.new(m, 0)
  ary0[0] = 1
  v = Vector.elements(ary0)
  ary1 = [Array.new(m, 1)]
  (0..m - 2).each{|i|
    ary2 = Array.new(m, 0)
    ary2[i] = 1
    ary1 << ary2
  }
  # 配列を引数に展開
  a = Matrix[*ary1]
  mod = 10 ** 20
  # power(a, n, mod) * vの成分はmod未満
  (power(a, n, mod) * v)[m - 1]
end

(2..9).each{|m|
  p [m, (0..10).map{|i| f(m, 10 ** i)}]
}

出力結果
[2, [1, 55, 54224848179261915075, 76137795166849228875, 66073310059947366875, 49895374653428746875, 68996526838242546875, 86998673686380546875, 6082642167760546875, 3172326981560546875, 99069175119560546875]]
[3, [0, 81, 62928098149064722658, 10783789625725711384, 84855239178776081984, 45590351831757462976, 87395036595190865536, 36466221250542429440, 95160048182486712832, 88871128684941792256, 56893269687011067904]]
[4, [0, 56, 97838180985096739296, 84465668382508012160, 72950854709025441792, 96451003184390892544, 8740034747828348928, 32803712350556868608, 84027725612141256704, 74152605583824732160, 50331276893492641792]]
[5, [0, 31, 38261258264777004033, 94147780942189200385, 22299037799913441025, 71762521041589169921, 38967967351782360833, 9226043430064117505, 68633832057834469121, 1772155374304605953, 82711718805648324353]]
[6, [0, 16, 17130007349662323904, 93240673228858160925, 88056360493937573376, 48812610302662993151, 4915217296395642996, 56390686729323541264, 27169437970338339728, 89068418041425978989, 15824280756705573376]]
[7, [0, 8, 76324494942045981696, 195920253480368658, 23778413061199575800, 44144174396274980576, 39905909105358155136, 73690200277951099392, 31576895769957220352, 80865343089788137472, 59806603832376205312]]
[8, [0, 4, 59172997404458625000, 1230887635364049824, 60556540444184606992, 10346590246637690992, 81836027114883468848, 29447872758524258224, 13483357678177838768, 93482707094876314800, 42525944029057284272]]
[9, [0, 2, 77799461090403757880, 65571732106893914592, 62937430511874341760, 54835914168209817088, 88530826807377868800, 11174062203432853504, 29289147652664426496, 7404157041260232704, 56925392030348607488]]