2016年8月8日月曜日

160808

Ruby


A generalization of Dana Scott's sequence(1)

以下の一般化を思いついた。

a(0) = … = a(2k - 1) = 1,
a(n) = (l a(n - k) + m a(n - 1) a(n - 2k + 1)) / a(n - 2k)

実験してみると、m = 1 のとき、a(n) が整数となる。

require 'prime'

def A(k, l, m, n)
  a = Array.new(k * 2, 1)
  ary = [1]
  while ary.size < n + 1
    break if (l * a[k] + m * a[1] * a[-1]) % a[0] > 0
    a = *a[1..-1], (l * a[k] + m * a[1] * a[-1]) / a[0]
    ary << a[0]
  end
  ary
end

# 特性方程式の係数の絶対値が1より大きいもの
def c(k, l)
  k * (k - 1) / 2 * l * l + (4 * k - 2) * l + 3
end

def berlekamp_massey(s, q)
  b, c = [1], [1] + [0] * (s.size - 1)
  l, m, a = 0, -1, 1
  s.size.times do |n|
    d = (0..l).inject(0) {|sum, i| (sum + c[i] * s[n - i]) % q}
    next if d == 0
    t = c[0..l]
    (0...[s.size - n + m, b.size].min).each do |j|
      c[n - m + j] = (c[n - m + j] - d * a * b[j]) % q
    end
    b, l, m, a = t, n + 1 - l, n, mod_inv(d, q) if 2 * l <= n
  end
  c[0..l]
end

def euclid(a, b)
  return [0, 1] if a == 0
  q, r = b.divmod(a)
  x, y = euclid(r, a)
  [y - q * x, x]
end

# x^(-1) (mod n)
def mod_inv(x, n)
  euclid(x, n)[0]
end

# x % n1 = r1, x % n2 = r2, |x| <= n1 * n2 / 2 となる x
def chinese(n1, r1, n2, r2)
  x = (n1 * (r2 - r1) * mod_inv(n1, n2) + r1) % (n = n1 * n2)
  2 * x > n ? x - n : x
end

# f を多項式として f=0 が数列 s を生成する漸化式の特性方程式となっているか
def test(f, s)
  (0..s.size - f.size).all? do |i|
    f.each_with_index.inject(0) {|sum, (fj, j)|
      sum + fj * s[f.size + i - j - 1]
    } == 0
  end
end

# 数列 s を生成する漸化式の特性方程式を返す
def polynomial(s)
  f, n = [], 1
  Prime.each do |q|
    c = berlekamp_massey(s, q)
    if c.size != f.size then
      f, n = c, q if c.size > f.size
      next
    end
    f = (0...f.size).map {|i| chinese(n, f[i], q, c[i])}
    return f if test(f, s)
    n *= q
  end
end

i = 7
n = 150
(1..i).each{|k|
  (1..i).each{|l|
    (1..i).each{|m|
      ary = A(k, l, m, n)
      if ary.size == n + 1
        p [[k, l, m], c(k, l), polynomial(ary)]
        p ary[0..50]
      end
    }
  }
}

出力結果
[[1, 1, 1], 5, [1, -5, 5, -1]]
[1, 1, 2, 6, 21, 77, 286, 1066, 3977, 14841, 55386, 206702, 771421, 2878981, 10744502, 40099026, 149651601, 558507377, 2084377906, 7779004246, 29031639077, 108347552061, 404358569166, 1509086724602, 5631988329241, 21018866592361, 78443478040202, 292755045568446, 1092576704233581, 4077551771365877, 15217630381229926, 56792969753553826, 211954248632985377, 791024024778387681, 2952141850480565346, 11017543377143873702, 41118031658094929461, 153454583255235844141, 572700301362848447102, 2137346622196157944266, 7976686187421783329961, 29769398127490975375577, 111100906322542118172346, 414634227162677497313806, 1547436002328167871082877, 5775109782149993987017701, 21553003126271808076987926, 80436902722937238320934002, 300194607765477145206748081, 1120341528338971342506058321, 4181171505590408224817485202]
[[1, 2, 1], 7, [1, -7, 7, -1]]
[1, 1, 3, 15, 85, 493, 2871, 16731, 97513, 568345, 3312555, 19306983, 112529341, 655869061, 3822685023, 22280241075, 129858761425, 756872327473, 4411375203411, 25711378892991, 149856898154533, 873430010034205, 5090723162050695, 29670908962269963, 172934730611569081, 1007937474707144521, 5874690117631298043, 34240203231080643735, 199566529268852564365, 1163158972382034742453, 6779387305023355890351, 39513164857758100599651, 230299601841525247707553, 1342284446191393385645665, 7823407075306835066166435, 45598158005649617011352943, 265765540958590867001951221, 1548995087745895585000354381, 9028204985516782643000175063, 52620234825354800273000695995, 306693203966612018995004000905, 1787538988974317313697023309433, 10418540729879291863187135855691, 60723705390301433865425791824711, 353923691611929311329367615092573, 2062818444281274434110779898730725, 12022986974075717293335311777291775, 70075103400173029325901090765019923, 408427633426962458662071232812827761, 2380490697161601722646526306111946641, 13874516549542647877217086603858852083]
[[1, 3, 1], 9, [1, -9, 9, -1]]
[1, 1, 4, 28, 217, 1705, 13420, 105652, 831793, 6548689, 51557716, 405913036, 3195746569, 25160059513, 198084729532, 1559517776740, 12278057484385, 96664942098337, 761041479302308, 5991666892320124, 47172293659258681, 371386682381749321, 2923921165394735884, 23019982640776137748, 181235939960814366097, 1426867537045738791025, 11233704356405095962100, 88442767314195028905772, 696308434157155135284073, 5482024705943046053366809, 43159889213387213291650396, 339797089001154660279836356, 2675216822795850068947040449, 21061937493365645891296487233, 165820283124129317061424857412, 1305500327499668890600102372060, 10278182336873221807739394119065, 80919958367486105571315050580457, 637081484603015622762781010524588, 5015731918456638876530933033616244, 39488773863050095389484683258405361, 310894458985944124239346533033626641, 2447666898024502898525287581010607764, 19270440725210079063962954115051235468, 151715858903656129613178345339399275977, 1194456430504038957841463808600142972345, 9403935585128655533118532123461744502780, 74037028250525205307106793179093813049892, 582892290419072986923735813309288759896353, 4589101295102058690082779713295216266120929, 36129918070397396533738501893052441369071076]
[[1, 4, 1], 11, [1, -11, 11, -1]]
[1, 1, 5, 45, 441, 4361, 43165, 427285, 4229681, 41869521, 414465525, 4102785725, 40613391721, 402031131481, 3979697923085, 39394948099365, 389969783070561, 3860302882606241, 38213059042991845, 378270287547312205, 3744489816430130201, 37066627876753989801, 366921788951109767805, 3632151261634343688245, 35954590827392327114641, 355913757012288927458161, 3523182979295496947466965, 34875916035942680547211485, 345235977380131308524647881, 3417483857765370404699267321, 33829602600273572738468025325, 334878542144970356979980985925, 3314955818849429997061341833921, 32814679646349329613633437353281, 324831840644643866139273031698885, 3215503726800089331779096879635565, 31830205427356249451651695764656761, 315086550546762405184737860766932041, 3119035300040267802395726911904663645, 30875266449855915618772531258279704405, 305633629198518888385329585670892380401, 3025461025535332968234523325450644099601, 29948976626154810793959903668835548615605, 296464305236012774971364513362904842056445, 2934694075733972938919685229960212871948841, 29050476452103716614225487786239223877431961, 287570070445303193203335192632432025902370765, 2846650228000928215419126438538081035146275685, 28178932209563978960987929192748378325560386081, 278942671867638861394460165488945702220457585121, 2761247786466824634983613725696708643879015465125]
[[1, 5, 1], 13, [1, -13, 13, -1]]
[1, 1, 6, 66, 781, 9301, 110826, 1320606, 15736441, 187516681, 2234463726, 26626048026, 317278112581, 3780711302941, 45051257522706, 536834378969526, 6396961290111601, 76226701102369681, 908323451938324566, 10823654722157525106, 128975533213951976701, 1536882743845266195301, 18313617392929242366906, 218226525971305642207566, 2600404694262738464123881, 30986629805181555927279001, 369239152967915932663224126, 4399883205809809636031410506, 52429359316749799699713701941, 624752428595187786760533012781, 7444599783825503641426682451426, 88710444977310855910359656404326, 1057080739943904767282889194400481, 12596258434349546351484310676401441, 150098020472250651450528838922416806, 1788579987232658271054861756392600226, 21312861826319648601207812237788785901, 253965761928603124943438885097072830581, 3026276281316917850720058808927085181066, 36061349613874411083697266822027949342206, 429709919085176015153647143055408306925401, 5120457679408237770760068449842871733762601, 61015782233813677233967174255059052498225806, 727068929126355889036846022610865758244947066, 8663811367282456991208185097075330046441138981, 103238667478263128005461375142293094799048720701, 1230200198371875079074328316610441807542143509426, 14659163712984237820886478424183008595706673392406, 174679764357438978771563412773585661340937937199441, 2081498008576283507437874474858844927495548573000881, 24803296338557963110482930285532553468605644938811126]
[[1, 6, 1], 15, [1, -15, 15, -1]]
[1, 1, 7, 91, 1261, 17557, 244531, 3405871, 47437657, 660721321, 9202660831, 128176530307, 1785268763461, 24865586158141, 346332937450507, 4823795538148951, 67186804596634801, 935791468814738257, 13033893758809700791, 181538721154521072811, 2528508202404485318557, 35217576112508273386981, 490517557372711342099171, 6832028227105450516001407, 95157877622103595881920521, 1325378258482344891830885881, 18460137741130724889750481807, 257116550117347803564675859411, 3581171563901738525015711549941, 49879285344506991546655285839757, 694728823259196143128158290206651, 9676324240284239012247560777053351, 134773810540720150028337692588540257, 1877157023329797861384480135462510241, 26145424516076449909354384203886603111, 364158786201740500869576898718949933307, 5072077582308290562264722197861412463181, 70644927366114327370836533871340824551221, 983956905543292292629446752000910131253907, 13704751750239977769441417994141401013003471, 190882567597816396479550405165978704050794681, 2658651194619189572944264254329560455698122057, 37030234157070837624740149155447867675722914111, 515764627004372537173417823921940587004422675491, 7183674543904144682803109385751720350386194542757, 100055678987653653022070113576602144318402300923101, 1393595831283246997626178480686678300107246018380651, 19410285958977804313744428616036894057183041956406007, 270350407594406013394795822143829838500455341371303441, 3765495420362706383213397081397580844949191737241842161, 52446585477483483351592763317422301990788228980014486807]
[[1, 7, 1], 17, [1, -17, 17, -1]]
[1, 1, 8, 120, 1905, 30353, 483736, 7709416, 122866913, 1958161185, 31207712040, 497365231448, 7926635991121, 126328810626481, 2013334334032568, 32087020533894600, 511378994208281025, 8149976886798601793, 129888251194569347656, 2070062042226310960696, 32991104424426406023473, 525787608748596185414865, 8379610635553112560614360, 133547982560101204784414888, 2128388110326066163990023841, 33920661782656957419055966561, 540602200412185252540905441128, 8615714544812307083235431091480, 137310830516584728079225992022545, 2188357573720543342184380441269233, 34876410349012108746870861068285176, 555834208010473196607749396651293576, 8858470917818559036977119485352412033, 141179700477086471395026162368987298945, 2250016736715564983283441478418444371080, 35859088086971953261140037492326122638328, 571495392654835687194957158398799517842161, 9108067194390399041858174496888466162836241, 145157579717591548982535834791816659087537688, 2313413208287074384678715182172178079237766760, 36869453752875598605876907079963032608716730465, 587597846837722503309351798097236343660229920673, 9364696095650684454343751862475818465954962000296, 149247539683573228766190678001515859111619162084056, 2378595938841520975804707096161777927319951631344593, 37908287481780762384109122860586930978007606939429425, 604154003769650677169941258673229117720801759399526200, 9628555772832630072334951015911078952554820543452989768, 153452738361552430480189274995904034123156326935848310081, 2445615258012006257610693448918553467017946410430119971521, 38976391389830547691290905907700951438163986239946071234248]
[[2, 1, 1], 10, [1, 0, 0, -10, 0, 0, 10, 0, 0, -1]]
[1, 1, 1, 1, 2, 3, 5, 13, 22, 41, 111, 191, 361, 982, 1693, 3205, 8723, 15042, 28481, 77521, 133681, 253121, 688962, 1188083, 2249605, 6123133, 10559062, 19993321, 54419231, 93843471, 177690281, 483649942, 834032173, 1579219205, 4298430243, 7412446082, 14035282561, 38202222241, 65877982561, 124738323841, 339521569922, 585489396963, 1108609632005, 3017491907053, 5203526590102, 9852748364201, 26817905593551, 46246249913951, 87566125645801, 238343658434902, 411012722635453]
[[2, 2, 1], 19, [1, 0, 0, -19, 0, 0, 19, 0, 0, -1]]
[1, 1, 1, 1, 3, 5, 11, 43, 79, 191, 761, 1407, 3421, 13645, 25237, 61381, 244839, 452849, 1101431, 4393447, 8126035, 19764371, 78837197, 145815771, 354657241, 1414676089, 2616557833, 6364065961, 25385332395, 46952225213, 114198530051, 455521307011, 842523495991, 2049209474951, 8173998193793, 15118470702615, 36771572019061, 146676446181253, 271289949151069, 659839086868141, 2632002033068751, 4868100614016617, 11840331991607471, 47229360149056255, 87354521103148027, 212466136762066331, 847496480649943829, 1567513279242647859, 3812550129725586481, 15207707291549932657, 28127884505264513425]
[[2, 3, 1], 30, [1, 0, 0, -30, 0, 0, 30, 0, 0, -1]]
[1, 1, 1, 1, 4, 7, 19, 97, 184, 541, 2791, 5311, 15661, 80824, 153817, 453619, 2341087, 4455364, 13139281, 67810681, 129051721, 380585521, 1964168644, 3738044527, 11023840819, 56893079977, 108274239544, 319310798221, 1647935150671, 3136214902231, 9248989307581, 47733226289464, 90841957925137, 267901379121619, 1382615627243767, 2631280564926724, 7759891005219361, 40048119963779761, 76216294424949841, 224768937772239841, 1160012863322369284, 2207641257758618647, 6510539304389736019, 33600324916384929457, 63945380180574990904, 188580870889530104701, 973249409711840584951, 1852208383978916117551, 5462334716491983300301, 28190632556726992034104, 53650097755207992418057]
[[2, 4, 1], 43, [1, 0, 0, -43, 0, 0, 43, 0, 0, -1]]
[1, 1, 1, 1, 5, 9, 29, 181, 349, 1205, 7569, 14621, 50569, 317689, 613705, 2122681, 13335341, 25760961, 89102021, 559766605, 1081346629, 3740162189, 23496862041, 45390797429, 156997709905, 986308439089, 1905332145361, 6590163653809, 41401457579669, 79978559307705, 276629875750061, 1737874909906981, 3357194158778221, 11611864617848741, 72949344758513505, 140922176109377549, 487421684073897049, 3062134604947660201, 5915374202435078809, 20460098866485827305, 128536704063043214909, 248304794326163932401, 858836730708330849749, 5395479436042867365949, 10422885987496450082005, 36050682590883409862141, 226481599609737386154921, 437512906680524739511781, 1513269832086394883360161, 9506831704172927351140705, 18365119194594542609412769]
[[2, 5, 1], 58, [1, 0, 0, -58, 0, 0, 58, 0, 0, -1]]
[1, 1, 1, 1, 6, 11, 41, 301, 586, 2321, 17111, 33351, 132241, 974986, 1900381, 7535401, 55557051, 108288326, 429385601, 3165776881, 6170534161, 24467443841, 180393725126, 351612158811, 1394214913321, 10279276555261, 20035722518026, 79445782615441, 585738369924711, 1141684571368631, 4527015394166801, 33376807809153226, 65055984845493901, 257960431684892201, 1901892306751809131, 3707049451621783686, 14699217590644688641, 108374484677043967201, 211236762757596176161, 837597442235062360321, 6175443734284754321286, 12036788427731360257451, 47728354989807909849641, 351891918369553952346061, 685885703617929938498506, 2719678636976815799069201, 20051663903330290529404151, 39083448317794275134157351, 154973953952688692637094801, 1142592950571457006223690506, 2227070668410655752708470461]
[[2, 6, 1], 75, [1, 0, 0, -75, 0, 0, 75, 0, 0, -1]]
[1, 1, 1, 1, 7, 13, 55, 463, 907, 4051, 34201, 67051, 299701, 2530357, 4960813, 22173805, 187212163, 367033057, 1640561851, 13851169651, 27155485351, 121379403151, 1024799341957, 2009138882863, 8980435271305, 75821300135113, 148649121846457, 664430830673401, 5609751410656351, 10998025877754901, 49158901034560351, 415045783088434807, 813705265832016163, 3637094245726792555, 30707778197133519313, 60203191645691441107, 269095815282748088701, 2271960540804791994301, 4454222476515334625701, 19909453236677631771301, 168094372241357474058907, 329552260070489070860713, 1473030443698862002987555, 12436711585319648288364763, 24382413022739675909067007, 108984343380479110589307751, 920148562941412615864933501, 1803969011422665528200097751, 8063368379711755321605786001, 68078556946079213925716714257, 133469324432254509410898166513]
[[2, 7, 1], 94, [1, 0, 0, -94, 0, 0, 94, 0, 0, -1]]
[1, 1, 1, 1, 8, 15, 71, 673, 1324, 6581, 62511, 123047, 611941, 5812780, 11441977, 56903911, 540525959, 1063980744, 5291451761, 50263101337, 98938767145, 492048109841, 4673927898312, 9200241363671, 45755182763431, 434625031441609, 855523508054188, 4254739948889221, 40415453996171255, 79554486007675743, 395645060063934101, 3758202596612485036, 7397711675205789841, 36790735845996982151, 349472426030964937023, 687907631308130779400, 3421142788617655405921, 32497177418283126658033, 63968011999980956694289, 318129488605595955768481, 3021888027474299814259976, 5948337208366920841789407, 29582621297531806231062791, 281003089377691599599519665, 553131392366123657329720492, 2750865651181852383533071061, 26130265424097844462941068799, 51435271152841133210822216279, 255800922938614739862344545861, 2429833681351721843453919878572, 4782927085821859264949136393385]
[[3, 1, 1], 16, [1, 0, 0, 0, 0, -16, 0, 0, 0, 0, 16, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 2, 3, 4, 6, 9, 22, 36, 51, 82, 129, 321, 529, 753, 1217, 1921, 4786, 7891, 11236, 18166, 28681, 71462, 117828, 167779, 271266, 428289, 1067137, 1759521, 2505441, 4050817, 6395649, 15935586, 26274979, 37413828, 60490982, 95506441, 237966646, 392365156, 558701971, 903313906, 1426200961, 3553564097, 5859202353, 8343115729, 13489217601, 21297507969]
[[3, 2, 1], 35, [1, 0, 0, 0, 0, -35, 0, 0, 0, 0, 35, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 3, 5, 7, 13, 23, 83, 147, 215, 423, 771, 2801, 4971, 7281, 14351, 26181, 95133, 168845, 247317, 487493, 889373, 3231703, 5735737, 8401475, 16560393, 30212491, 109782751, 194846191, 285402811, 562565851, 1026335311, 3729381813, 6619034735, 9695294077, 19110678523, 34865188073, 126689198873, 224852334777, 329354595785, 649200503913, 1184390059161, 4303703379851, 7638360347661, 11188360962591, 22053706454501, 40234396823391]
[[3, 3, 1], 60, [1, 0, 0, 0, 0, -60, 0, 0, 0, 0, 60, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 4, 7, 10, 22, 43, 202, 370, 547, 1264, 2521, 11881, 21781, 32221, 74521, 148681, 700744, 1284667, 1900450, 4395442, 8769643, 41331982, 75773530, 112094287, 259256524, 517260241, 2437886161, 4469353561, 6611662441, 15291739441, 30509584561, 143793951484, 263616086527, 389975989690, 901953370462, 1799548228843, 8481405251362, 15548879751490, 23001971729227, 53199957117784, 106142835917161, 500259115878841, 917120289251341, 1356726356034661, 3137895516578761, 6260627770883641]
[[3, 4, 1], 91, [1, 0, 0, 0, 0, -91, 0, 0, 0, 0, 91, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 5, 9, 13, 33, 69, 397, 741, 1101, 2917, 6189, 35673, 66613, 99009, 262445, 556921, 3210121, 5994361, 8909641, 23617081, 50116681, 288875165, 539425809, 801768613, 2125274793, 4509944349, 25995554677, 48542328381, 72150265461, 191251114237, 405844874709, 2339311045713, 4368270128413, 6492722122809, 17210475006485, 36521528779441, 210511998559441, 393095769228721, 584272840787281, 1548751499469361, 3286531745274961, 18943740559303925, 35374250960456409, 52578062948732413, 139370424477235953, 295751335545967029]
[[3, 5, 1], 128, [1, 0, 0, 0, 0, -128, 0, 0, 0, 0, 128, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 6, 11, 16, 46, 101, 686, 1296, 1931, 5766, 12801, 87041, 164481, 245121, 732161, 1625601, 11053446, 20887691, 31128336, 92978606, 206438501, 1403700526, 2652572176, 3953053451, 11807550726, 26216064001, 178258913281, 336855778561, 502006659841, 1499465963521, 3329233689601, 22637478286086, 42778031304971, 63750892746256, 190420369816366, 422786462515301, 2874781483419566, 5432473119952656, 8095861372114571, 24181887500714886, 53690551505753601, 365074610915998721, 689881308202682241, 1028110643365804161, 3070909292220974081, 6818277254768192001]
[[3, 6, 1], 171, [1, 0, 0, 0, 0, -171, 0, 0, 0, 0, 171, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 7, 13, 19, 61, 139, 1087, 2071, 3091, 10267, 23599, 184681, 351919, 525313, 1745227, 4011661, 31394581, 59824021, 89299981, 296678221, 681958741, 5336893987, 10169731513, 15180471319, 50433552241, 115928974279, 907240583107, 1728794533051, 2580590824111, 8573407202647, 19707243668659, 154225562234101, 293884900887019, 438685259627413, 1457428790897647, 3350115494697721, 26217438339213961, 49958704356260041, 74573913545835961, 247754321045397241, 569499926854943881, 4456810292104139167, 8492685855663319813, 12677126617532485819, 42116777148926633221, 96811637449845762019]
[[3, 7, 1], 220, [1, 0, 0, 0, 0, -220, 0, 0, 0, 0, 220, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 8, 15, 22, 78, 183, 1618, 3102, 4635, 16948, 40041, 354201, 679141, 1014861, 3711401, 8768761, 77568268, 148728595, 222249742, 812779738, 1920318583, 16987096358, 32570882982, 48671678455, 177995051088, 420541000881, 3720096534001, 7132874644281, 10658875331721, 38980103408401, 92096558874321, 814684153849728, 1562066976214375, 2334245025968262, 8536464651388598, 20168725852475383, 178412109596556298, 342085534916303662, 511189001811717475, 1869446778550694428, 4416858865133234521, 39071437317491979401, 74915170079694287421, 111948057151740158581, 409400308037950691001, 967271922738325884681]
[[4, 1, 1], 23, [1, 0, 0, 0, 0, 0, 0, -23, 0, 0, 0, 0, 0, 0, 23, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 14, 33, 53, 74, 96, 141, 209, 300, 714, 1151, 1611, 2094, 3083, 4578, 6579, 15665, 25257, 35355, 45959, 67673, 100497, 144431, 343906, 554491, 776186, 1008991, 1485711, 2206346, 3170896, 7550257, 12173533, 17040724, 22151830, 32617957, 48439105, 69615274, 165761738]
[[4, 2, 1], 55, [1, 0, 0, 0, 0, 0, 0, -55, 0, 0, 0, 0, 0, 0, 55, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 3, 5, 7, 9, 15, 25, 39, 135, 235, 339, 447, 775, 1323, 2091, 7261, 12651, 18261, 24091, 41801, 71391, 112861, 391933, 682885, 985717, 1300429, 2256445, 3853765, 6092389, 21157095, 36863105, 53210419, 70199037, 121806195, 208031893, 328876131, 1142091171, 1989924751, 2872376871, 3789447531, 6575278051, 11229868431, 17753218671, 61651766113]
[[4, 3, 1], 99, [1, 0, 0, 0, 0, 0, 0, -99, 0, 0, 0, 0, 0, 0, 99, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 4, 7, 10, 13, 25, 46, 76, 343, 619, 904, 1198, 2383, 4459, 7426, 33562, 60589, 88507, 117316, 233443, 436888, 727651, 3288685, 5937037, 8672707, 11495695, 22874965, 42810517, 71302351, 322257520, 581768971, 849836704, 1126460719, 2241513061, 4194993730, 6986902726, 31577948227, 57007422055, 83275324210, 110381654692, 219645404947, 411066574975, 684645164776, 3094316668678]
[[4, 4, 1], 155, [1, 0, 0, 0, 0, 0, 0, -155, 0, 0, 0, 0, 0, 0, 155, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 5, 9, 13, 17, 37, 73, 125, 693, 1277, 1877, 2493, 5589, 11165, 19221, 106641, 196541, 288921, 383781, 860561, 1719261, 2959881, 16421945, 30265929, 44491833, 59099657, 132520697, 264754953, 455802425, 2528872813, 4660756417, 6851453237, 9100963273, 20407326669, 40770543425, 70190613541, 389429991181, 717726222181, 1055079306541, 1401489244261, 3142595786221, 6278398932421, 10808898682861, 59969689768985]
[[4, 5, 1], 223, [1, 0, 0, 0, 0, 0, 0, -223, 0, 0, 0, 0, 0, 0, 223, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 6, 11, 16, 21, 51, 106, 186, 1221, 2281, 3366, 4476, 11161, 23421, 41256, 270946, 506211, 747051, 993466, 2477531, 5199246, 9158611, 60148681, 112376401, 165841771, 220544791, 550000561, 1154209081, 2033170351, 13352736126, 24947054651, 36816125926, 48959949951, 122097646851, 256229216626, 451354659276, 2964247271181, 5538133755961, 8173014113616, 10868888344146, 27105127600201, 56881731881781, 100198701188886, 658049541465946]
[[4, 6, 1], 303, [1, 0, 0, 0, 0, 0, 0, -303, 0, 0, 0, 0, 0, 0, 303, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 7, 13, 19, 25, 67, 145, 259, 1963, 3703, 5479, 7291, 20011, 43639, 78175, 592669, 1118071, 1654381, 2201599, 6043033, 13178683, 23608549, 178983925, 337653517, 499617325, 664875349, 1824975733, 3979918477, 7129703581, 54052552531, 101970243841, 150882777511, 200790153541, 551136628111, 1201922201221, 2153146872871, 16323691880287, 30794675986243, 45566099190739, 60637961493775, 166441436713567, 362976524850115, 650243225903419, 4929700895293993]
[[4, 7, 1], 395, [1, 0, 0, 0, 0, 0, 0, -395, 0, 0, 0, 0, 0, 0, 395, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 8, 15, 22, 29, 85, 190, 344, 2955, 5615, 8324, 11082, 33195, 74663, 135486, 1164066, 2212001, 3279291, 4365936, 13078451, 29416836, 53381091, 458638853, 871522485, 1292031987, 1720167359, 5152876205, 11590158525, 21032014319, 180702543820, 343377646795, 509057323244, 677741573167, 2030220146025, 4566493041818, 8286560260546, 71196343626031, 135289921314451, 200567293325806, 267028459660096, 799901584657351, 1799186668317571, 3264883710640756, 28051178686112198]
[[5, 1, 1], 31, [1, 0, 0, 0, 0, 0, 0, 0, 0, -31, 0, 0, 0, 0, 0, 0, 0, 0, 31, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 11, 15, 20, 46, 73, 101, 130, 160, 221, 313, 436, 590, 1365, 2171, 3008, 3876, 4775, 6604, 9363, 13052, 17671, 40891, 65041, 90121, 116131, 143071, 197881, 280561, 391111, 529531, 1225352, 1949043, 2700604, 3480035, 4287336]
[[5, 2, 1], 79, [1, 0, 0, 0, 0, 0, 0, 0, 0, -79, 0, 0, 0, 0, 0, 0, 0, 0, 79, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5, 7, 9, 11, 17, 27, 41, 59, 199, 343, 491, 643, 799, 1271, 2059, 3163, 4583, 15485, 26703, 38237, 50087, 62253, 99067, 160529, 246639, 357397, 1207597, 2082445, 2981941, 3906085, 4854877, 7725901, 12519157, 19234645, 27872365, 94177047, 162403961, 232553107, 304624485, 378618095]
[[5, 3, 1], 147, [1, 0, 0, 0, 0, 0, 0, 0, 0, -147, 0, 0, 0, 0, 0, 0, 0, 0, 147, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 7, 10, 13, 16, 28, 49, 79, 118, 520, 931, 1351, 1780, 2218, 3979, 7063, 11470, 17200, 75853, 135829, 197128, 259750, 323695, 580798, 1031059, 1674478, 2511055, 11073955, 19830013, 28779229, 37921603, 47257135, 84792421, 150527461, 244462255, 366596803, 1616721514, 2895045979, 4201570198, 5536294171, 6899217898]
[[5, 4, 1], 235, [1, 0, 0, 0, 0, 0, 0, 0, 0, -235, 0, 0, 0, 0, 0, 0, 0, 0, 235, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 9, 13, 17, 21, 41, 77, 129, 197, 1069, 1957, 2861, 3781, 4717, 9413, 17869, 30085, 46061, 250041, 457781, 669281, 884541, 1103561, 2202421, 4181121, 7039661, 10778041, 58508425, 107118649, 156608713, 206978617, 258228361, 515356921, 978364297, 1647250489, 2522015497, 13690721309, 25065305937, 36645769381, 48432111641, 60424332717]
[[5, 5, 1], 343, [1, 0, 0, 0, 0, 0, 0, 0, 0, -343, 0, 0, 0, 0, 0, 0, 0, 0, 343, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 11, 16, 21, 26, 56, 111, 191, 296, 1906, 3541, 5201, 6886, 8596, 18881, 37741, 65176, 101186, 651701, 1210791, 1778456, 2354696, 2939511, 6456976, 12907091, 22289856, 34605271, 222879691, 414086761, 608226481, 805298851, 1005303871, 2208266641, 4414187161, 7623065431, 11834901451, 76224202476, 141616461251, 208011677776, 275409852051, 343810984076]
[[5, 6, 1], 471, [1, 0, 0, 0, 0, 0, 0, 0, 0, -471, 0, 0, 0, 0, 0, 0, 0, 0, 471, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 13, 19, 25, 31, 73, 151, 265, 415, 3091, 5803, 8551, 11335, 14155, 33931, 70663, 124351, 194995, 1452565, 2727091, 4018573, 5327011, 6652405, 15947119, 33211153, 58444507, 91647181, 682702261, 1281726661, 1888720381, 2503683421, 3126615781, 7495111621, 15609170941, 27468793741, 43073980021, 320868609907, 602408803273, 887694560119, 1176725880445, 1469502764251]
[[5, 7, 1], 619, [1, 0, 0, 0, 0, 0, 0, 0, 0, -619, 0, 0, 0, 0, 0, 0, 0, 0, 619, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 8, 15, 22, 29, 36, 92, 197, 351, 554, 4684, 8863, 13091, 17368, 21694, 56351, 121339, 216658, 342308, 2894445, 5476913, 8089712, 10732842, 13406303, 34824322, 74986899, 133894034, 211545727, 1788762067, 3384722965, 4999428421, 6632878435, 8285073007, 21521374141, 46341781837, 82746296095, 130734916915, 1105452062702, 2091753315051, 3089638673962, 4099108139435, 5120161711470]
[[6, 1, 1], 40, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 9, 12, 16, 21, 27, 61, 96, 132, 169, 207, 246, 325, 444, 603, 802, 1041, 2361, 3721, 5121, 6561, 8041, 9561, 12641, 17281, 23481, 31241, 40561, 92002, 145003, 199564, 255685, 313366, 372607]
[[6, 2, 1], 107, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -107, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 107, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5, 7, 9, 11, 13, 19, 29, 43, 61, 83, 275, 471, 671, 875, 1083, 1295, 1935, 3003, 4499, 6423, 8775, 29105, 49863, 71049, 92663, 114705, 137175, 205013, 318219, 476793, 680735, 930045, 3084813, 5284949, 7530453, 9821325, 12157565, 14539173]
[[6, 3, 1], 204, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -204, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 204, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 7, 10, 13, 16, 19, 31, 52, 82, 121, 169, 733, 1306, 1888, 2479, 3079, 3688, 6133, 10414, 16531, 24484, 34273, 148717, 264997, 383113, 503065, 624853, 748477, 1244809, 2113849, 3355597, 4970053, 6957217, 30188740, 53792971, 77769910, 102119557, 126841912, 151936975]
[[6, 4, 1], 331, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -331, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 331, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 9, 13, 17, 21, 25, 45, 81, 133, 201, 285, 1525, 2781, 4053, 5341, 6645, 7965, 14581, 26493, 43701, 66205, 94005, 503121, 917533, 1337241, 1762245, 2192545, 2628141, 4811417, 8742373, 14421009, 21847325, 31021321, 166028281, 302782921, 441285241, 581535241, 723532921, 867278281]
[[6, 5, 1], 488, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -488, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 488, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 11, 16, 21, 26, 31, 61, 116, 196, 301, 431, 2741, 5076, 7436, 9821, 12231, 14666, 29301, 56136, 95171, 146406, 209841, 1334681, 2471721, 3620961, 4782401, 5956041, 7141881, 14269121, 27337761, 46347801, 71299241, 102192081, 649986726, 1203722771, 1763400216, 2329019061, 2900579306, 3478080951]
[[6, 6, 1], 675, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -675, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 675, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 13, 19, 25, 31, 37, 79, 157, 271, 421, 607, 4471, 8371, 12307, 16279, 20287, 24331, 52675, 105319, 182263, 283507, 409051, 3013201, 5641651, 8294401, 10971451, 13672801, 16398451, 35502301, 70984351, 122844601, 191083051, 275699701, 2030892757, 3802464013, 5590413469, 7394741125, 9215446981, 11052531037]
[[6, 7, 1], 892, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -892, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 892, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 8, 15, 22, 29, 36, 43, 99, 204, 358, 561, 813, 6805, 12846, 18936, 25075, 31263, 37500, 87445, 181098, 318459, 499528, 724305, 6062925, 11445253, 16871289, 22341033, 27854485, 33411645, 77912633, 161357449, 283746093, 445078565, 645354865, 5402059048, 10197707059, 15032298898, 19905834565, 24818314060, 29769737383]
[[7, 1, 1], 50, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 10, 13, 17, 22, 28, 35, 78, 122, 167, 213, 260, 308, 357, 456, 605, 804, 1053, 1352, 1701, 3801, 5951, 8151, 10401, 12701, 15051, 17451, 22301, 29601, 39351, 51551]
[[7, 2, 1], 139, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -139, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 139, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5, 7, 9, 11, 13, 15, 21, 31, 45, 63, 85, 111, 363, 619, 879, 1143, 1411, 1683, 1959, 2791, 4179, 6123, 8623, 11679, 15291, 50041, 85347, 121209, 157627, 194601, 232131, 270217, 385031, 576573, 844843, 1189841]
[[7, 3, 1], 270, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -270, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 270, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 7, 10, 13, 16, 19, 22, 34, 55, 85, 124, 172, 229, 982, 1744, 2515, 3295, 4084, 4882, 5689, 8926, 14593, 22690, 33217, 46174, 61561, 264061, 468991, 676351, 886141, 1098361, 1313011, 1530091, 2400841, 3925261, 6103351, 8935111]
[[7, 4, 1], 443, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -443, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 443, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 9, 13, 17, 21, 25, 29, 49, 85, 137, 205, 289, 389, 2061, 3749, 5453, 7173, 8909, 10661, 12429, 21285, 37229, 60261, 90381, 127589, 171885, 910809, 1656821, 2409921, 3170109, 3937385, 4711749, 5493201, 9407549, 16454793, 26634933, 39947969]
[[7, 5, 1], 658, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -658, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 658, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 11, 16, 21, 26, 31, 36, 66, 121, 201, 306, 436, 591, 3726, 6886, 10071, 13281, 16516, 19776, 23061, 42796, 78981, 131616, 200701, 286236, 388221, 2447761, 4523751, 6616191, 8725081, 10850421, 12992211, 15150451, 28116341, 51889881, 86471071, 131859911]
[[7, 6, 1], 915, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -915, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 915, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 13, 19, 25, 31, 37, 43, 85, 163, 277, 427, 613, 835, 6103, 11407, 16747, 22123, 27535, 32983, 38467, 76891, 148255, 252559, 389803, 559987, 763111, 5577841, 10425511, 15306121, 20219671, 25166161, 30145591, 35157961, 70277491, 135504181, 230838031, 356279041]
[[7, 7, 1], 1214, [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1214, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1214, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1]]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 8, 15, 22, 29, 36, 43, 50, 106, 211, 365, 568, 820, 1121, 9318, 17564, 25859, 34203, 42596, 51038, 59529, 127506, 254969, 441918, 688353, 994274, 1359681, 11302341, 21304487, 31366119, 41487237, 51667841, 61907931, 72207507, 154663601, 309276213, 536045343, 834970991]

0 件のコメント:

コメントを投稿