Power-series coefficients of a rational generating function
Source:R/analytic_combinatorics_native.R
morie_rational_gf_coefficients.RdFor \(P(x)/Q(x)\) with \(Q(0) \ne 0\) the coefficients satisfy the linear recurrence read off \(Q\). With integer coefficients and \(q_0 = \pm 1\) the sequence is integral and is computed in arbitrary precision, exact at every index – Fibonacci leaves the double-exact range at \(n = 79\) and keeps going. Otherwise the expansion runs in doubles and says so.
Value
A list with coefficients (numeric), exact_coefficients
(decimal strings when exact), all_integral, is_exact.
Examples
morie_rational_gf_coefficients(c(0, 1), c(1, -1, -1), 300)
#> $coefficients
#> [1] 0.000000e+00 1.000000e+00 1.000000e+00 2.000000e+00 3.000000e+00
#> [6] 5.000000e+00 8.000000e+00 1.300000e+01 2.100000e+01 3.400000e+01
#> [11] 5.500000e+01 8.900000e+01 1.440000e+02 2.330000e+02 3.770000e+02
#> [16] 6.100000e+02 9.870000e+02 1.597000e+03 2.584000e+03 4.181000e+03
#> [21] 6.765000e+03 1.094600e+04 1.771100e+04 2.865700e+04 4.636800e+04
#> [26] 7.502500e+04 1.213930e+05 1.964180e+05 3.178110e+05 5.142290e+05
#> [31] 8.320400e+05 1.346269e+06 2.178309e+06 3.524578e+06 5.702887e+06
#> [36] 9.227465e+06 1.493035e+07 2.415782e+07 3.908817e+07 6.324599e+07
#> [41] 1.023342e+08 1.655801e+08 2.679143e+08 4.334944e+08 7.014087e+08
#> [46] 1.134903e+09 1.836312e+09 2.971215e+09 4.807527e+09 7.778742e+09
#> [51] 1.258627e+10 2.036501e+10 3.295128e+10 5.331629e+10 8.626757e+10
#> [56] 1.395839e+11 2.258514e+11 3.654353e+11 5.912867e+11 9.567220e+11
#> [61] 1.548009e+12 2.504731e+12 4.052740e+12 6.557470e+12 1.061021e+13
#> [66] 1.716768e+13 2.777789e+13 4.494557e+13 7.272346e+13 1.176690e+14
#> [71] 1.903925e+14 3.080615e+14 4.984540e+14 8.065155e+14 1.304970e+15
#> [76] 2.111485e+15 3.416455e+15 5.527940e+15 8.944394e+15 1.447233e+16
#> [81] 2.341673e+16 3.788906e+16 6.130579e+16 9.919485e+16 1.605006e+17
#> [86] 2.596955e+17 4.201961e+17 6.798916e+17 1.100088e+18 1.779979e+18
#> [91] 2.880067e+18 4.660047e+18 7.540114e+18 1.220016e+19 1.974027e+19
#> [96] 3.194043e+19 5.168071e+19 8.362114e+19 1.353019e+20 2.189230e+20
#> [101] 3.542248e+20 5.731478e+20 9.273727e+20 1.500521e+21 2.427893e+21
#> [106] 3.928414e+21 6.356307e+21 1.028472e+22 1.664103e+22 2.692575e+22
#> [111] 4.356678e+22 7.049252e+22 1.140593e+23 1.845518e+23 2.986111e+23
#> [116] 4.831630e+23 7.817741e+23 1.264937e+24 2.046711e+24 3.311648e+24
#> [121] 5.358359e+24 8.670007e+24 1.402837e+25 2.269837e+25 3.672674e+25
#> [126] 5.942511e+25 9.615186e+25 1.555770e+26 2.517288e+26 4.073058e+26
#> [131] 6.590346e+26 1.066340e+27 1.725375e+27 2.791715e+27 4.517090e+27
#> [136] 7.308806e+27 1.182590e+28 1.913470e+28 3.096060e+28 5.009530e+28
#> [141] 8.105590e+28 1.311512e+29 2.122071e+29 3.433583e+29 5.555654e+29
#> [146] 8.989237e+29 1.454489e+30 2.353413e+30 3.807902e+30 6.161315e+30
#> [151] 9.969217e+30 1.613053e+31 2.609975e+31 4.223028e+31 6.833003e+31
#> [156] 1.105603e+32 1.788903e+32 2.894506e+32 4.683410e+32 7.577916e+32
#> [161] 1.226133e+33 1.983924e+33 3.210057e+33 5.193981e+33 8.404038e+33
#> [166] 1.359802e+34 2.200206e+34 3.560008e+34 5.760213e+34 9.320221e+34
#> [171] 1.508043e+35 2.440065e+35 3.948109e+35 6.388174e+35 1.033628e+36
#> [176] 1.672446e+36 2.706074e+36 4.378520e+36 7.084594e+36 1.146311e+37
#> [181] 1.854771e+37 3.001082e+37 4.855853e+37 7.856935e+37 1.271279e+38
#> [186] 2.056972e+38 3.328251e+38 5.385223e+38 8.713475e+38 1.409870e+39
#> [191] 2.281217e+39 3.691087e+39 5.972304e+39 9.663391e+39 1.563570e+40
#> [196] 2.529909e+40 4.093478e+40 6.623387e+40 1.071687e+41 1.734025e+41
#> [201] 2.805712e+41 4.539737e+41 7.345449e+41 1.188519e+42 1.923063e+42
#> [206] 3.111582e+42 5.034645e+42 8.146227e+42 1.318087e+43 2.132710e+43
#> [211] 3.450797e+43 5.583507e+43 9.034305e+43 1.461781e+44 2.365212e+44
#> [216] 3.826993e+44 6.192205e+44 1.001920e+45 1.621140e+45 2.623060e+45
#> [221] 4.244200e+45 6.867260e+45 1.111146e+46 1.797872e+46 2.909018e+46
#> [226] 4.706890e+46 7.615908e+46 1.232280e+47 1.993871e+47 3.226150e+47
#> [231] 5.220021e+47 8.446172e+47 1.366619e+48 2.211236e+48 3.577856e+48
#> [236] 5.789092e+48 9.366948e+48 1.515604e+49 2.452299e+49 3.967903e+49
#> [241] 6.420201e+49 1.038810e+50 1.680831e+50 2.719641e+50 4.400472e+50
#> [246] 7.120113e+50 1.152058e+51 1.864070e+51 3.016128e+51 4.880198e+51
#> [251] 7.896326e+51 1.277652e+52 2.067285e+52 3.344937e+52 5.412222e+52
#> [256] 8.757160e+52 1.416938e+53 2.292654e+53 3.709592e+53 6.002246e+53
#> [261] 9.711839e+53 1.571409e+54 2.542592e+54 4.114001e+54 6.656593e+54
#> [266] 1.077059e+55 1.742719e+55 2.819778e+55 4.562497e+55 7.382275e+55
#> [271] 1.194477e+56 1.932705e+56 3.127182e+56 5.059887e+56 8.187069e+56
#> [276] 1.324696e+57 2.143402e+57 3.468098e+57 5.611500e+57 9.079598e+57
#> [281] 1.469110e+58 2.377070e+58 3.846179e+58 6.223249e+58 1.006943e+59
#> [286] 1.629268e+59 2.636211e+59 4.265478e+59 6.901689e+59 1.116717e+60
#> [291] 1.806886e+60 2.923602e+60 4.730488e+60 7.654090e+60 1.238458e+61
#> [296] 2.003867e+61 3.242325e+61 5.246192e+61 8.488516e+61 1.373471e+62
#>
#> $exact_coefficients
#> [1] "0"
#> [2] "1"
#> [3] "1"
#> [4] "2"
#> [5] "3"
#> [6] "5"
#> [7] "8"
#> [8] "13"
#> [9] "21"
#> [10] "34"
#> [11] "55"
#> [12] "89"
#> [13] "144"
#> [14] "233"
#> [15] "377"
#> [16] "610"
#> [17] "987"
#> [18] "1597"
#> [19] "2584"
#> [20] "4181"
#> [21] "6765"
#> [22] "10946"
#> [23] "17711"
#> [24] "28657"
#> [25] "46368"
#> [26] "75025"
#> [27] "121393"
#> [28] "196418"
#> [29] "317811"
#> [30] "514229"
#> [31] "832040"
#> [32] "1346269"
#> [33] "2178309"
#> [34] "3524578"
#> [35] "5702887"
#> [36] "9227465"
#> [37] "14930352"
#> [38] "24157817"
#> [39] "39088169"
#> [40] "63245986"
#> [41] "102334155"
#> [42] "165580141"
#> [43] "267914296"
#> [44] "433494437"
#> [45] "701408733"
#> [46] "1134903170"
#> [47] "1836311903"
#> [48] "2971215073"
#> [49] "4807526976"
#> [50] "7778742049"
#> [51] "12586269025"
#> [52] "20365011074"
#> [53] "32951280099"
#> [54] "53316291173"
#> [55] "86267571272"
#> [56] "139583862445"
#> [57] "225851433717"
#> [58] "365435296162"
#> [59] "591286729879"
#> [60] "956722026041"
#> [61] "1548008755920"
#> [62] "2504730781961"
#> [63] "4052739537881"
#> [64] "6557470319842"
#> [65] "10610209857723"
#> [66] "17167680177565"
#> [67] "27777890035288"
#> [68] "44945570212853"
#> [69] "72723460248141"
#> [70] "117669030460994"
#> [71] "190392490709135"
#> [72] "308061521170129"
#> [73] "498454011879264"
#> [74] "806515533049393"
#> [75] "1304969544928657"
#> [76] "2111485077978050"
#> [77] "3416454622906707"
#> [78] "5527939700884757"
#> [79] "8944394323791464"
#> [80] "14472334024676221"
#> [81] "23416728348467685"
#> [82] "37889062373143906"
#> [83] "61305790721611591"
#> [84] "99194853094755497"
#> [85] "160500643816367088"
#> [86] "259695496911122585"
#> [87] "420196140727489673"
#> [88] "679891637638612258"
#> [89] "1100087778366101931"
#> [90] "1779979416004714189"
#> [91] "2880067194370816120"
#> [92] "4660046610375530309"
#> [93] "7540113804746346429"
#> [94] "12200160415121876738"
#> [95] "19740274219868223167"
#> [96] "31940434634990099905"
#> [97] "51680708854858323072"
#> [98] "83621143489848422977"
#> [99] "135301852344706746049"
#> [100] "218922995834555169026"
#> [101] "354224848179261915075"
#> [102] "573147844013817084101"
#> [103] "927372692193078999176"
#> [104] "1500520536206896083277"
#> [105] "2427893228399975082453"
#> [106] "3928413764606871165730"
#> [107] "6356306993006846248183"
#> [108] "10284720757613717413913"
#> [109] "16641027750620563662096"
#> [110] "26925748508234281076009"
#> [111] "43566776258854844738105"
#> [112] "70492524767089125814114"
#> [113] "114059301025943970552219"
#> [114] "184551825793033096366333"
#> [115] "298611126818977066918552"
#> [116] "483162952612010163284885"
#> [117] "781774079430987230203437"
#> [118] "1264937032042997393488322"
#> [119] "2046711111473984623691759"
#> [120] "3311648143516982017180081"
#> [121] "5358359254990966640871840"
#> [122] "8670007398507948658051921"
#> [123] "14028366653498915298923761"
#> [124] "22698374052006863956975682"
#> [125] "36726740705505779255899443"
#> [126] "59425114757512643212875125"
#> [127] "96151855463018422468774568"
#> [128] "155576970220531065681649693"
#> [129] "251728825683549488150424261"
#> [130] "407305795904080553832073954"
#> [131] "659034621587630041982498215"
#> [132] "1066340417491710595814572169"
#> [133] "1725375039079340637797070384"
#> [134] "2791715456571051233611642553"
#> [135] "4517090495650391871408712937"
#> [136] "7308805952221443105020355490"
#> [137] "11825896447871834976429068427"
#> [138] "19134702400093278081449423917"
#> [139] "30960598847965113057878492344"
#> [140] "50095301248058391139327916261"
#> [141] "81055900096023504197206408605"
#> [142] "131151201344081895336534324866"
#> [143] "212207101440105399533740733471"
#> [144] "343358302784187294870275058337"
#> [145] "555565404224292694404015791808"
#> [146] "898923707008479989274290850145"
#> [147] "1454489111232772683678306641953"
#> [148] "2353412818241252672952597492098"
#> [149] "3807901929474025356630904134051"
#> [150] "6161314747715278029583501626149"
#> [151] "9969216677189303386214405760200"
#> [152] "16130531424904581415797907386349"
#> [153] "26099748102093884802012313146549"
#> [154] "42230279526998466217810220532898"
#> [155] "68330027629092351019822533679447"
#> [156] "110560307156090817237632754212345"
#> [157] "178890334785183168257455287891792"
#> [158] "289450641941273985495088042104137"
#> [159] "468340976726457153752543329995929"
#> [160] "757791618667731139247631372100066"
#> [161] "1226132595394188293000174702095995"
#> [162] "1983924214061919432247806074196061"
#> [163] "3210056809456107725247980776292056"
#> [164] "5193981023518027157495786850488117"
#> [165] "8404037832974134882743767626780173"
#> [166] "13598018856492162040239554477268290"
#> [167] "22002056689466296922983322104048463"
#> [168] "35600075545958458963222876581316753"
#> [169] "57602132235424755886206198685365216"
#> [170] "93202207781383214849429075266681969"
#> [171] "150804340016807970735635273952047185"
#> [172] "244006547798191185585064349218729154"
#> [173] "394810887814999156320699623170776339"
#> [174] "638817435613190341905763972389505493"
#> [175] "1033628323428189498226463595560281832"
#> [176] "1672445759041379840132227567949787325"
#> [177] "2706074082469569338358691163510069157"
#> [178] "4378519841510949178490918731459856482"
#> [179] "7084593923980518516849609894969925639"
#> [180] "11463113765491467695340528626429782121"
#> [181] "18547707689471986212190138521399707760"
#> [182] "30010821454963453907530667147829489881"
#> [183] "48558529144435440119720805669229197641"
#> [184] "78569350599398894027251472817058687522"
#> [185] "127127879743834334146972278486287885163"
#> [186] "205697230343233228174223751303346572685"
#> [187] "332825110087067562321196029789634457848"
#> [188] "538522340430300790495419781092981030533"
#> [189] "871347450517368352816615810882615488381"
#> [190] "1409869790947669143312035591975596518914"
#> [191] "2281217241465037496128651402858212007295"
#> [192] "3691087032412706639440686994833808526209"
#> [193] "5972304273877744135569338397692020533504"
#> [194] "9663391306290450775010025392525829059713"
#> [195] "15635695580168194910579363790217849593217"
#> [196] "25299086886458645685589389182743678652930"
#> [197] "40934782466626840596168752972961528246147"
#> [198] "66233869353085486281758142155705206899077"
#> [199] "107168651819712326877926895128666735145224"
#> [200] "173402521172797813159685037284371942044301"
#> [201] "280571172992510140037611932413038677189525"
#> [202] "453973694165307953197296969697410619233826"
#> [203] "734544867157818093234908902110449296423351"
#> [204] "1188518561323126046432205871807859915657177"
#> [205] "1923063428480944139667114773918309212080528"
#> [206] "3111581989804070186099320645726169127737705"
#> [207] "5034645418285014325766435419644478339818233"
#> [208] "8146227408089084511865756065370647467555938"
#> [209] "13180872826374098837632191485015125807374171"
#> [210] "21327100234463183349497947550385773274930109"
#> [211] "34507973060837282187130139035400899082304280"
#> [212] "55835073295300465536628086585786672357234389"
#> [213] "90343046356137747723758225621187571439538669"
#> [214] "146178119651438213260386312206974243796773058"
#> [215] "236521166007575960984144537828161815236311727"
#> [216] "382699285659014174244530850035136059033084785"
#> [217] "619220451666590135228675387863297874269396512"
#> [218] "1001919737325604309473206237898433933302481297"
#> [219] "1621140188992194444701881625761731807571877809"
#> [220] "2623059926317798754175087863660165740874359106"
#> [221] "4244200115309993198876969489421897548446236915"
#> [222] "6867260041627791953052057353082063289320596021"
#> [223] "11111460156937785151929026842503960837766832936"
#> [224] "17978720198565577104981084195586024127087428957"
#> [225] "29090180355503362256910111038089984964854261893"
#> [226] "47068900554068939361891195233676009091941690850"
#> [227] "76159080909572301618801306271765994056795952743"
#> [228] "123227981463641240980692501505442003148737643593"
#> [229] "199387062373213542599493807777207997205533596336"
#> [230] "322615043836854783580186309282650000354271239929"
#> [231] "522002106210068326179680117059857997559804836265"
#> [232] "844617150046923109759866426342507997914076076194"
#> [233] "1366619256256991435939546543402365995473880912459"
#> [234] "2211236406303914545699412969744873993387956988653"
#> [235] "3577855662560905981638959513147239988861837901112"
#> [236] "5789092068864820527338372482892113982249794889765"
#> [237] "9366947731425726508977331996039353971111632790877"
#> [238] "15156039800290547036315704478931467953361427680642"
#> [239] "24522987531716273545293036474970821924473060471519"
#> [240] "39679027332006820581608740953902289877834488152161"
#> [241] "64202014863723094126901777428873111802307548623680"
#> [242] "103881042195729914708510518382775401680142036775841"
#> [243] "168083057059453008835412295811648513482449585399521"
#> [244] "271964099255182923543922814194423915162591622175362"
#> [245] "440047156314635932379335110006072428645041207574883"
#> [246] "712011255569818855923257924200496343807632829750245"
#> [247] "1152058411884454788302593034206568772452674037325128"
#> [248] "1864069667454273644225850958407065116260306867075373"
#> [249] "3016128079338728432528443992613633888712980904400501"
#> [250] "4880197746793002076754294951020699004973287771475874"
#> [251] "7896325826131730509282738943634332893686268675876375"
#> [252] "12776523572924732586037033894655031898659556447352249"
#> [253] "20672849399056463095319772838289364792345825123228624"
#> [254] "33449372971981195681356806732944396691005381570580873"
#> [255] "54122222371037658776676579571233761483351206693809497"
#> [256] "87571595343018854458033386304178158174356588264390370"
#> [257] "141693817714056513234709965875411919657707794958199867"
#> [258] "229265413057075367692743352179590077832064383222590237"
#> [259] "370959230771131880927453318055001997489772178180790104"
#> [260] "600224643828207248620196670234592075321836561403380341"
#> [261] "971183874599339129547649988289594072811608739584170445"
#> [262] "1571408518427546378167846658524186148133445300987550786"
#> [263] "2542592393026885507715496646813780220945054040571721231"
#> [264] "4114000911454431885883343305337966369078499341559272017"
#> [265] "6656593304481317393598839952151746590023553382130993248"
#> [266] "10770594215935749279482183257489712959102052723690265265"
#> [267] "17427187520417066673081023209641459549125606105821258513"
#> [268] "28197781736352815952563206467131172508227658829511523778"
#> [269] "45624969256769882625644229676772632057353264935332782291"
#> [270] "73822750993122698578207436143903804565580923764844306069"
#> [271] "119447720249892581203851665820676436622934188700177088360"
#> [272] "193270471243015279782059101964580241188515112465021394429"
#> [273] "312718191492907860985910767785256677811449301165198482789"
#> [274] "505988662735923140767969869749836918999964413630219877218"
#> [275] "818706854228831001753880637535093596811413714795418360007"
#> [276] "1324695516964754142521850507284930515811378128425638237225"
#> [277] "2143402371193585144275731144820024112622791843221056597232"
#> [278] "3468097888158339286797581652104954628434169971646694834457"
#> [279] "5611500259351924431073312796924978741056961814867751431689"
#> [280] "9079598147510263717870894449029933369491131786514446266146"
#> [281] "14691098406862188148944207245954912110548093601382197697835"
#> [282] "23770696554372451866815101694984845480039225387896643963981"
#> [283] "38461794961234640015759308940939757590587318989278841661816"
#> [284] "62232491515607091882574410635924603070626544377175485625797"
#> [285] "100694286476841731898333719576864360661213863366454327287613"
#> [286] "162926777992448823780908130212788963731840407743629812913410"
#> [287] "263621064469290555679241849789653324393054271110084140201023"
#> [288] "426547842461739379460149980002442288124894678853713953114433"
#> [289] "690168906931029935139391829792095612517948949963798093315456"
#> [290] "1116716749392769314599541809794537900642843628817512046429889"
#> [291] "1806885656323799249738933639586633513160792578781310139745345"
#> [292] "2923602405716568564338475449381171413803636207598822186175234"
#> [293] "4730488062040367814077409088967804926964428786380132325920579"
#> [294] "7654090467756936378415884538348976340768064993978954512095813"
#> [295] "12384578529797304192493293627316781267732493780359086838016392"
#> [296] "20038668997554240570909178165665757608500558774338041350112205"
#> [297] "32423247527351544763402471792982538876233052554697128188128597"
#> [298] "52461916524905785334311649958648296484733611329035169538240802"
#> [299] "84885164052257330097714121751630835360966663883732297726369399"
#> [300] "137347080577163115432025771710279131845700275212767467264610201"
#>
#> $all_integral
#> [1] TRUE
#>
#> $is_exact
#> [1] TRUE
#>
#> $n
#> [1] 300
#>
#> $method
#> [1] "Analytic combinatorics (Flajolet and Sedgewick 2009)"
#>