151206

Ruby


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

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

require 'matrix'

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]
  ((a ** n) * v)[m - 1]
end

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

出力結果
[2, [1, 55, 354224848179261915075, 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875]]
[3, [0, 81, 53324762928098149064722658, 815507705949063215012634973737520390101047421640059634182536354954214345249517992411833219017896606412691713984091121798255747368520490502996057925004321483423983646944214344896256767238653269823324951340326550513652712428004750634815007544492510783789625725711384]]
[4, [0, 56, 2505471397838180985096739296, 80612965543569013375053017657224193322814498804143605698949253030259897351461707903235835255206857522960377247566119902833745107612558849667330639399422732632784532453583865206618002987209702170391793700471749898929136523409356835657014641447629317324840860079447184465668382508012160]]
[5, [0, 31, 8196759338261258264777004033, 13443520142394747905751303566960790514566367463663197111501191353709777126951474437866553367699441909504861540463704750840265037040870875839355638074955810739914342739218524786521352712187959472233969938248839473553665729166138340108183543336370069925904006912191465031558094147780942189200385]]
[6, [0, 16, 9446344817130007349662323904, 47926174280534914669640266755148680489952118066975763667882257581628650841761200610945408653182800916211576373936961298845651034956198409928069155819952368459415153711417382010472835852503043165772701691203304186831738194153591261201264679349298483657706552908018904841271338093240673228858160925]]
[7, [0, 8, 6952140676324494942045981696, 1568533933639196723025504816474892852801846600864935684677652330390629628312734658710324141182365413218878322926744076865229701569192566760399957949871518592634865083152698359621666274103976779813320200452549583186618098440409094525862076074444095357580578448762728970589935447300195920253480368658]]
[8, [0, 4, 4174747959172997404458625000, 5904990663319680096123713875387637834772027171150191509938030832603868343114917525591710433451943909189072757672390035289070630326679467682705473605908772863221587632898955331292176455715311981565666613292343161561310821563812781090847026437544565470534358494130640715780288951601230887635364049824]]
[9, [0, 2, 2279225977799461090403757880, 7933924390689031620818248254865930320588478067806264015020660356321568507968010461016354223553238235750493991343409309027268583945543255310735045919810484597016385159889096988465566253717414096007757163324472200386665933665338994209466205599325727554774532611195062752846504637865571732106893914592]]