160722

Ruby

Integrality and the Laurent phenomenon for Somos 4 sequences(5)

整数a, b, c, d, e が
a^3 * d + e^2 = bc
を満たすとき、以下の数列を考える。

a(1) = 1, a(2) = a, a(3) = e^2, a(4) = c * e^3,

a(n + 4) * a(n) = e^3 * a(n + 3) * a(n + 1) + ad * e^3 * a(n + 2)^2

連続する4項 a(n), a(n + 1), a(n + 2), a(n + 3) があるディオファントス方程式
の整数解となっていることを確認してみた。

def A(a1, a2, a3, a4, k, l, n)
  a, b, c, d = a1, a2, a3, a4
  ary = [a1]
  while ary.size < n
    break if (k * b * d + l * c * c) % a > 0
    a, b, c, d = b, c, d, (k * b * d + l * c * c) / a
    ary << a
  end
  ary
end

def x(s, t, u, v, k, l)
  a, b = s * s * v * v + k * (s * u ** 3 + t ** 3 * v) + l * t * t * u * u, s * t * u * v
  return false if a % b > 0
  a / b
end

def Diophantine(s, t, u, v, k, l, x)
  s * s * v * v + k * (s * u ** 3 + t ** 3 * v) + l * t * t * u * u == x * s * t * u * v
end

# a1, a2, a3, a4, k, lを以下のように定める
def f(a, c, d, e)
  return false if (a ** 3 * d + e * e) % c > 0
  return 1, a, e * e, c * e ** 3, e ** 3, a * d * e ** 3
end

def g(a1, a2, a3, a4, k, l, n)
  p ary = A(a1, a2, a3, a4, k, l, n)
  x = x(a1, a2, a3, a4, k, l)
  p (0..n - 4).map{|i| Diophantine(ary[i], ary[i + 1], ary[i + 2], ary[i + 3], k, l, x)} if x != false
end

def h(a, c, d, e, n)
  f = f(a, c, d, e)
  g(*f, n) if f != false
end

n = 20
# テスト用
h(3, 133, 30, 11, n)

# f(a, c, d, e)がfalseのときは何も出力されない
(1..3).each{|a|
  (1..3).each{|c|
    (1..3).each{|d|
      (1..3).each{|e|
        h(a, c, d, e, n)
      }
    }
  }
}

出力結果
[1, 3, 121, 177023, 2460698229, 1383391404675863, 8688298479390987330929, 1455780005631999673771330516947, 4764115435770257032716350566474633731689, 223337535292722331216632575726395706629291248170767, 362740488296214246554305584172734945255544810003424782725680421, 5684399354734693943514581605677865492494211340843132464513825699922941136167, 3663178425075173516124169809409408606242603593700025583156605461905659549116130050238057441, 25250176864369887877947189457135530660164015908973302044152819670980403663047598549079989054148703322698403, 4958058020712814432486705115374786533372502495669393443814623968130512717844083284910928004315372729188382986639113180026201, 17688524650722567116776685594211248483217560907027356274244353315433206710285529509934590173847675452395966246426606926505783153051495924349343, 966153896093880153156929695756396704236036978843578716850207392035008377304823716339303902561584926011695191963421912993623952454349316232639228043806839995631829, 1736866319359273848679563666416661400990572249601952304669372511916616818806800257482633495658057209912056650881639272012572504523762082920288405407289575637034423994331294978413198903, 30800398154111222623972673388270929472329720054055277747294164271353605934320605102397826636172957633550948666223675969513619166894174107884459941000174711694283507515473234541353206828914602568204023767889, 22668868718816480695376897795197644842873892175907257844188449489310389324565259905661276413078971420475323254044594866811488882682691048703019039490288373902569924260019965595621220648709917837833509063205069058985862670936440947]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 1, 1, 2, 3, 7, 23, 59, 314, 1529, 8209, 83313, 620297, 7869898, 126742987, 1687054711, 47301104551, 1123424582771, 32606721084786]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 4, 8, 192, 6656, 180224, 78905344, 23236444160, 12516608442368, 67807156962852864, 175629443127729717248, 2339805680824409902809088, 121119885296813220774402850816, 3155644309941486351655288610750464, 1004552344054822639968667523226426933248, 450052264685681437023654271100054026189799424, 160457898335979161391188030579843920882272693125120, 922120145666159773612399879826786853163802369198749908992, 3510013188391437859050276507929957613492604112525994651673427968]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 9, 27, 2916, 728271, 84499119, 776778080445, 5304120838292007, 38986309426650166746, 18666112111965734924549727, 3494222771037136138944228291003, 2467056534033570692316760428517962387, 40347972967792950971522484157433217291666021, 212734267862962557903675868809014394782648912731632, 16634667074447412777118732663112633292559908647961813057225, 7840775361153519332149631359093812956048047127037951671835489855429, 1301360824654082785415709979757911093734461325843921401572238058876451962111, 10550192525849390852072197003957518456442089031802364483461454465318842858944100524401, 137015738831254637464169580269850081068515748485470124133351516425030995416555829634802395312482]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 1, 1, 3, 5, 23, 119, 551, 8199, 68821, 1448467, 38745265, 837004657, 61242422289, 2605518436049, 249891170973299, 34505654202377909, 3507312493608222887, 1250318065223597979975]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 4, 8, 320, 11264, 589824, 442499072, 142002356224, 337618789203968, 2573314605832994816, 10727970629163730075648, 950173561853634178703163392, 63391595443901305275358988206080, 7727691790859300963376797002061840384, 11468813785052837368629076817506365800972288, 7126789281412788331963293294096032014913081704448, 40149298413431988219191238797751056906768137797492539392, 581852478839600216755543171570472019728594452514655059782402048, 5141366822326650412774298308001260178423100239681334512028094050598912]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 9, 27, 5103, 1279395, 259874649, 4599843465897, 31852308981148353, 1067737204554735183219, 721098447044896289098382103, 148204380761084811146737900863771, 1015676771183082789739205159435419740753, 19631201791154966708345587290597525153931584753, 186189522078151873836757498608392193642359678875387929, 174871123584587100152437431758334264699538181739719028914917035, 93101579394604217992798816734786584984671504500458650133601204741633183, 107958121802104871161581380563052286127403191291993540552806753001765525822869363, 5251602116636684499413025343102459737599644015749188801392940514558066011410836927379799529, 79089923664892336887420401583933827171952421585830185821282513831293602309741040388464282458160450009]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 1, 1, 4, 7, 55, 367, 2911, 80596, 1000009, 61030441, 2720324089, 172396803289, 32721647884468, 2919452283241615, 1365801588433808863, 407553285320316023431, 207387914271185385769879, 267704249987574459112515364]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 4, 8, 448, 15872, 1458176, 1409024000, 513265369088, 3379272752300032, 30458876996203053056, 283270915168368760717312, 58300902013371333032040988672, 4773825340878911862045364417724416, 3033407016633635356261812490210788769792, 6925344672348932254103378738359939947957321728, 8324407778521582460737575602655185360838909189160960, 283433098415021797859089279006348864821785601009868378996736, 5724940123793036352708507790955556606089573579582253910294991470592, 333453092761760281747081977017297518961647793214079688776547297793029439488]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 9, 27, 7290, 1830519, 626568939, 14620086993393, 103481899737101919, 10414610900292311453304, 7945616912034173684196999915, 2119394852565579811393266152002887, 55176038084425243752885396232821157874559, 1171512365741549357466162867815179963947490858521, 39472609797770081411671380989569937306340999443844142866, 80198448554539561949479443639356968995504753549726393696652862157, 48262777404433010289356204042073294162223976065169179603341617085767152245, 488609134654047591359918352160807776601705902710985832040268106948086429756368924079, 31583589469040791300614228454972096872696902425385115983676987855791714377062243107530333417941, 754307197894300255286799639694288360281651708782706439590783556521828159067309304300426151405150042986148]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 1, 2, 3, 7, 23, 59, 314, 1529, 8209, 83313, 620297, 7869898, 126742987, 1687054711, 47301104551, 1123424582771, 32606721084786, 1662315215971057]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 9, 54, 3645, 964467, 196101729, 822493698147, 6160917908796534, 52760632054914279495, 11200866643391172215305923, 2356693087807058251036367018187, 1094739602376453236257394129565944907, 9117270123865550000821051198759957490902098, 54682972398074036949693575165516533807336378238775, 1638177762391278692832413275146678986039732081081884393809, 442114534135935737605219354970016450590447654018914352488132587027, 79542845374443729391686002365496272225143251716781792822888069680493961969, 160850906989049793734685662102450219490126112452853210376600456143267945037242637442, 1276371176314045233761441838481410152954588568432642059870984594284763121079844114453108048685]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 4, 16, 384, 16384, 1114112, 482344960, 216358977536, 344903053737984, 1866847598661337088, 10645086381621603467264, 393485413354218116341563392, 22295262781945018149257458221056, 2344043679417958812330655215299592192, 1440292290690560207840297414117839540846592, 876287154400705551439127180406766744319945605120, 2225742460733555528006749832076790754183487225986023424, 16182217431613351234332354848261835578345124760069369067732992, 133795777003109437109801537905355309146266732864885719694145128235008]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 1, 2, 5, 17, 109, 706, 9529, 149057, 3464585, 141172802, 5987285341, 540281496721, 53055650250901, 8453268527614082, 2173247123169247025, 610193552206250342657, 364280506115937098013649, 225791960727416355391439746]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 9, 54, 8019, 2184813, 932678955, 10899688037526, 88967845857343329, 5429973621139537200417, 2400754271786284336027165161, 748203245760721955546580461315622, 6480395769576517998227876893169241990531, 85710559506717237522709416676099547606124606333, 2138127481097338746941325635114580796275960367738979163, 1295316397019287809282572073087203692732700003887523101210695270, 519706010764463584639601826512415006402580806997401430147962031107699489, 1935674542253281454596645181729259228669978840184462687579838439267536749180848033, 41894151978353324375345551924558947476791560503880669500931957122886987230365291199477906217, 688136939237916046207560298446601189261128289710045655655387717052307957988587492918955948149773790038]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 1, 3, 5, 23, 119, 551, 8199, 68821, 1448467, 38745265, 837004657, 61242422289, 2605518436049, 249891170973299, 34505654202377909, 3507312493608222887, 1250318065223597979975, 271100112874619989235287]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 4, 24, 448, 23552, 1933312, 658505728, 410437812224, 564118184525824, 2931315591836860416, 22348554704472292458496, 580695977168794611374620672, 38305717359845322624901398396928, 4176945150423851732390085143746838528, 1918760754417068268217846854377824040517632, 1493287406572201661172294710912930151584912900096, 2840446010435033676307875355191775250771122010242154496, 18980284452357603953590002824461895503306065401724039587692544, 185450058720924617419624612259274123597786411577883669355345020452864]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 1, 9, 81, 8748, 2657205, 1334448351, 10951989803541, 106308454538203767, 5097814193227278145644, 1815629005752239315341329867, 668048078232832455187735011831459, 3376664626463197730017155846533801266803, 39562082064276014568762326539147685855209849827, 901695251021853652073452410516473227207806077128279620, 312829777515801402273569352283722024713030070432237647093195391, 118464453106828692388165648041095797021462761291902996634377759156082213, 273265915764465477764354701458956706331179498897209334595578146914422371588755503, 3820419678135963163661689290703792507487600962953794955949896705631129718900345000975195613, 58397193880063610211440295143032699101182628226007894004055426898277135491811382817606941704130325412]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 2, 1, 1, 4, 3, 35, 158, 731, 25171, 144164, 8686977, 355986889, 8034946274, 2242256900185, 106749998473321, 30656079907867636, 11391480158408215083, 1380587103957029339771, 2827681810720906787049854]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 2, 4, 8, 384, 6656, 696320, 355991552, 69566726144, 362861385744384, 1595296951341940736, 8411803135396475305984, 936339968206821249291124736, 36052492217052443952862562615296, 10313974648861545110183803245211680768, 11656907217284299049109629310745823684853760, 5408434750921063022765120257033947071653529780224, 72682782357186131137193694160464024799165823204234100736, 702548775988473543890129942513827417307260914687259954351439872, 9858713052352119334426692072286717454864594408666511674666316805963776]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 2, 9, 27, 5832, 728271, 263063295, 2594942435322, 9389934799383807, 590872341728054445021, 175470240122257851084712356, 24408898988714112799519730339409, 218538061463175514115660129249335337121, 1806718346353487934006469097349620528067080106, 21483300539591969614499775555364913333441341176000537, 12414787454205292085841054313543931319645815346552701594319147, 2885233765227873494083682725214261129805436294885001061872266937829840, 5532922426900605861550641907609924357619033075578750742047542662947132166246991, 107253468590628824485624920016637579014316897011551682697851549955645761581178378373059167, 806159619870210688313965906428265654465539160435472325929138415919054939385136395429433961747999122]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 2, 1, 1, 6, 5, 149, 994, 15629, 1256173, 14937574, 6584850873, 586361017577, 145043600817218, 156007090120528345, 26671380119559720857, 172626349038477965252038, 205292645065228322826527917, 799161522757591557347798895741, 11493091660914207682976401529652002]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 2, 4, 8, 640, 11264, 3457024, 2720006144, 980527611904, 23425739474862080, 156351573816537776128, 6906949442738340635869184, 2117910019869426432512792461312, 178252598697833537414137102714535936, 981037932821518999832484115893198625177600, 2553771145243154954373968665550201731907015671808, 16261155593091424746274158971815942629193125976858427392, 1886751678216182153831240874160572018236978155030458316428935168, 47916864556368010829229239896005949704349575389917313357842681673285632, 47047320427486569841075947720885203932537588956393443275591308618970276969840640]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 2, 9, 27, 10206, 1279395, 1353580227, 20362046060862, 88306395882904827, 37522031666632836238953, 15862281219129516344553292002, 9324873946764922395820802536693665, 414704662375932234311963900478149259818361, 4983774030654280441785163132963066569538164872898, 1250047696563139367734369085162877512787142362913343568129, 1788691289301311993425985290633820398565609495090914663930218867603, 987335353976469618164228311223477468089267202797402391692308714214169189406, 76018860894094081116341051785749738930541507991985906029099190997712371727675886780315, 3021154453161083186110921695145460818400056617124548801989244968946321076185796592249608822300107, 393950461608436366742079814848377044871850142914946113606882330900954334543552174802110131227410575546932478]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 2, 1, 1, 8, 7, 391, 3422, 117655, 16609087, 357781304, 495986377897, 76545201396097, 90516797481207266, 223740326191428341089, 133644783486453073223377, 4081973702961287640284345864, 11273793650687896265213471329495, 453569284129388623834688601607286119, 19559674248129996716659668611099214199358]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 2, 4, 8, 896, 15872, 9887744, 10370940928, 6707254132736, 358698642237816832, 3228211391887839330304, 612203452218220966228000768, 336500909904462794958863928918016, 74381200918413690202707814609848369152, 1796495989087359780997703042880483326106271744, 8333411527913976469820515387979330689375991201005568, 475106856518378357452294775631980407696708372651097798475776, 136615384812388918366403920602143363833313918571884654740874253565952, 11100860290223089202874681275651289864094379068089417001615678757648092626944, 112565351800032330989485249441211298947437990911614054034781948676989224120679093239808]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 2, 9, 27, 14580, 1830519, 3974647239, 78055155600786, 440126610040994679, 564995381957717208214581, 307474561855090322046822573216, 709337558630416768144763068922013585, 59383899127691155781543246378063182138255473, 1016832946415080692530157544850444499047363066464506, 1921326395514951229792694571887735954734091438082805876913673, 4579043876642677980282452497515325594725111991335289188068100074761179, 12187436864853497120806568933244691111855706768582248669281501402707842208799852, 3962294242692525549125632638501941895031386355985243663279636748413539364145625823481765639, 267490971509736807129183890213615199177586832998423582808692795000048921448544657585522111526660444695, 574658055384866042988252491838364223791237557375271242208618372285534430732324311370111405623507208814383126189658]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 2, 4, 16, 512, 10240, 1376256, 457179136, 132338679808, 468872989769728, 1449648906618011648, 11050869715246939897856, 567297073930391236301029376, 18198958765380821267243146936320, 4661908182555221395031308136414707712, 2394085646758446989966640295410113148092416, 1227387141883651866146355236221371717059361112064, 7554391896587376802905048990111886491570771490286600192, 36206323720715415500739725430984903320169743165579938314059776, 529895328544636435561933105609768847899385930648018241410362870071296]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 2, 4, 16, 768, 16384, 5242880, 2550136832, 1580547964928, 16747761114284032, 80416274946327576576, 3918383589161088116064256, 463086288758301393146248953856, 47124911063484428000639941659852800, 103705288233392561159808292499836006039552, 116185717357520209274102193605842117071801942016, 837759873351207278423610826245824600668313442412658688, 23915438290037547193638253987784012749285628185664785878089728, 430913321424130028976900722454172824086197072101420219442571767709696, 182383494580441777392425677220513881322463533555544423608735424332962979643392]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 2, 4, 16, 1024, 22528, 13303808, 8334082048, 9763265970176, 194115822946353152, 1316739008666588413952, 229363126580783413194653696, 45006105079366449033974307094528, 15450814941520149063917725745055531008, 95369813373077747795866659627296851952140288, 199669058284995951770576570000570026911579246690304, 10248824222283008073799946934756324653372671779139754131456, 629939510632135803693886544249116458517409191778747057192329805824, 63417116151209802572872319580451437162292285916196054918731903496347451392, 121436686264106556599221110642363931724721006043022369636059701807794958529007190016]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 2, 1, 3, 8, 13, 167, 558, 7879, 149117, 1241704, 97231443, 2231567297, 145381499458, 19405138567553, 880120985044083, 394822112398982056, 63356092292383612637, 18939830084483189769031, 17617864869769984907829678]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 2, 4, 24, 640, 14848, 2351104, 648544256, 258562064384, 780778883514368, 2177966920685322240, 21986113503487374393344, 824664609103310692972232704, 28308866149938795697672911060992, 7282187293161598001204994450145673216, 2768345916786329414596939313059812704518144, 1789132071627899598069975137783011379037675192320, 8013397051674701184977292729629180628490266190081425408, 31403578069342034632100085848375111493531757265219495527448576, 533500418958104203065891197392003963755505942463824271575707325300736]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 2, 9, 81, 17496, 2657205, 6155681103, 50021409016746, 555974687032917183, 187321557027266733987783, 49233845782435341451246691868, 128415856691510965083941557759132011, 1874491754280042294236269219279977299870433, 27563673562602860154378527594246958526628108256330, 13502745242988953754870969454300833657266923960329316150521, 6280156467513456567412210351243081078315701705861061899292998132801, 18250452033737474193665645799021879031651763018951021728378654368211959000144, 473194607395393227985429807612998052045315130369301827238576395655586474517843269229397, 9938399354530556137447135189620115420519896345247570063018339222270737955548038252014718851370031, 6555759541983808991960823047948962051425874003745990904023448019407144924890583990891454240214276222686564386]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 3, 1, 1, 6, 3, 111, 693, 6507, 721008, 5645781, 2303455563, 269929985841, 24190699933341, 48586509838529946, 6455746766482261983, 26814789861863891391711, 59025454175157366438411453, 52239855453177167370830568447, 1836009666562633431453360266915268]
[1, 3, 4, 8, 576, 6656, 2097152, 1340866560, 307207602176, 7257248115982336, 38200877566711037952, 1012709575807905858322432, 305393635277321695593509158912, 16251941992406578670324494828044288, 62041363142513708294510812686355259195392, 155933466057957635381463657911445633663745654784, 368877729989503631709046013971980482166245211720646656, 47172905124463309068838385622908878364623338254616418498641920, 1001144597199488220557877193237050511562495516766510789216753850253312, 361443841820716000234583111366147801154006538057071054229072714116207438987264]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 3, 9, 27, 8748, 728271, 747737487, 8132343484599, 23456432006998839, 8005942430482300653852, 2410548572634042717158749731, 826128620571085285488396434659233, 27678831489551707816528731985887695359707, 231921864714878554722640094272037032324515542409, 27889361915702420583450501263293428207211711282653617748, 30502903359729972465939433286073590186588631627537023211129643701, 9177012164047535505928263004417736487283140731671569143136085311103247181, 354753113295966337406869306073009229474052498962178554717138522863430020851290728973, 10720525653663749313030140905273077717187084355195167277351702753403983336778710327478370956069, 421276492213726900377625103748319862437146693465734024385364579206729541120067559098718585206438526450852]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 3, 1, 1, 9, 5, 491, 4569, 163259, 41082947, 708002019, 2241724426975, 582536013178249, 743968223906838123, 5231427144168666195049, 2840860787464703182019161, 285511086319727653454410609041, 2072740928260041189256647415382045, 94618129480450260846386435554572883619, 18583119208288804798794991587775457888714289]
[1, 3, 4, 8, 960, 11264, 11239424, 11551113216, 7400497086464, 627660954359824384, 5394430809147168522240, 1664719973776448560140648448, 1318267155043898446478851969122304, 302571715987775977304250471905501380608, 16210298833345051011084961811822397625357828096, 105333282380780067684059433395243097091134716408496128, 9761381646773116723541601358848893835899832517119808100106240, 5943860682397933022756042381162386533432306246411984387412252682092544, 591127306376805629146341050787428574688153222576670880574109823034257557159936, 16537762286586899012783343775160923731402945311793522278031597314996657483305999732310016]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 3, 9, 27, 15309, 1279395, 4322209653, 75989816973927, 369153385527822957, 764846935290736117024527, 368175580229884453731867262257, 1295412690387028713336989253969725223, 131953342953538945632222692502976790664699465, 2070434126746668356007380733802468965697782026054379, 7857959296566695086209946784062557360577439786829841896418737, 22147623802732845743453590954619179418281211628630415189058265146529699, 85190636190202843491834235769192763621973639889645319196198988437440008463480693, 47110050269845241501116343091866796215900479444158461120635666799445242242462334495223716811, 3734665453147324601246224556307591910210616278315914999746963193868988222029802414142123817020405530493, 16621471042659135909725628240398723334693326825601990070206146279735683520390250196375519481222618888251239313388175]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 3, 1, 1, 12, 7, 1303, 16077, 1282735, 571090438, 18411437217, 184046500609183, 84318293200719853, 536535774461493675129, 8838728934510360474216664, 18126409696855867388216520367, 8454080399466376599949243404178419, 144781446634924815585907195482618318073, 73072457726611050633763580103934072132187935, 44488426097671709331690826299377055931452920328378]
[1, 3, 4, 8, 1344, 15872, 32768000, 46307475456, 61896837300224, 10749836750315585536, 129950871015912936308736, 181063545188001240556087803904, 271211092990298357352092904913371136, 245808521189307648934433439865547910021120, 43493733864784774173133888110962327427326024876032, 545213208928978208661249579959471048696544543313183637504, 506155167413895101262559484671207957009223570644411342291822706688, 803548876663604200557573604403376741753176010247878604599883005081832914944, 504687493900673077709480372110204726998345428911957517859947119856894939240981331968, 89017173587125267081796141237858391011768124570114628339372588904134155763939877425253676220416]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 3, 9, 27, 21870, 1830519, 13062288339, 315829444258179, 2609558257203229599, 13744279881659640894857190, 9099300245257965362487462996867, 147374131091039126194497400287419605929, 28667541877258282971860718967521337470019089603, 896432785546157624462904574077559839513061452642814761, 22339211281990562014875750118166606858210308351579502249505342450, 118652779061495193792902654951619929932720456290820442828996668147154042157, 4330285543686179504116589393898132069219562940255003193765797224373991065603463020193, 6729919562639236261075296619738285271526701062117068975266726166104468960970659011541647885014537, 1169097783922738409636361884128678969358810497347518015268434010644154282220762673311018217664836525690877213, 93909303533245507593454807319978084775251052070535212940875296516224041634071917601530141900731311278460175113324821632730]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 3, 1, 2, 9, 7, 257, 1230, 22973, 1491823, 13300461, 5676552098, 391725842029, 68292193811547, 63758060867059189, 6864580931054231246, 32328906876212522240025, 32252527024305471095768059, 52650201335658293911652567801, 702562909927603919614981152336258]
[1, 3, 9, 54, 10935, 964467, 1232411679, 8133505746066, 30619786483945269, 6612298917588153000639, 1239873758754491259957802941, 561451418504281774937963279949174, 7340264323933038162717776151544723892907, 41023625349927806658381189196352272212986978295, 4021476165753164301629074394861558050219094521049177619, 1662339395374609790854324516977749932213016219707841609496105234, 429306611690011711588142387316352300520103171071074205184674566686463593, 6592474494218689278028908418744263661524057835022077150967472562692985477173160251, 77289964294473015231179493348418385202698705093856485632059646035341840744332139433899349873, 2656622246575587900335554880143933500391368500965051518587401499011495832306584424967657120848761999926]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 3, 4, 16, 1152, 16384, 16449536, 10280239104, 12444130869248, 409570349089292288, 2499581496811824611328, 807446078937757466929135616, 236701733368248831466522229604352, 87964771968597647314795592881035804672, 1303235999169517368604094773492438329444007936, 3516321754667745157056990112137482577905420691570688, 354872157768971867666594869983776647506603677168302710325248, 48807655263920512092317047074141864785104775022809466071176380940288, 5691855723736036512560772624602430798132184811685876889715699993584917807104, 37113792274344430104703329205641406672717702313477749088648555336771101942094072119296]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 3, 1, 2, 15, 17, 2059, 16743, 2562664, 458792801, 32436517173, 118111533362567, 24840505832464177, 275415717155796715422, 1174085029919200979483695, 6026923883515502527140830213, 566260227380796281406751576962543, 3600927244557467991718373053951155023, 2476446123014854770449243475290947999960972, 252037866622932933813027945920895735076229855289]
[1, 3, 9, 54, 24057, 2184813, 15979899429, 213694555584087, 3103363989806876100, 5691861147878966585279259, 2201574173303749483453223688579, 37703401233844931913372134612859507609, 2246617507985734251312352299071861396670919743, 84151799506554016700764853992740311251099591215757878, 596008704032879062100675623755789774309436616997596179900060359, 1004522306653773210115198224060917162564529830791332390582498318438985479, 39438125356028995272656495602052258200519378165224172355177196318598776045247467999, 10455514883671220946836805763416248617500559156353063955223229910901948904700433776906535033865, 1109932476427624620887879859681861881624780621583755870771290660399649345552595504764794223691739176800232, 27621200507285780452996321008822661284727028547186173819658774497356610385963651761394438999084170083280012864808246909]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 3, 9, 81, 13122, 1240029, 1851009003, 9633985299963, 45730708117467039, 7905784630363537701312, 1202494885718288023969893171, 679611928765713678257964968806029, 5733409570201076745243159476377253067303, 28278071847785716636562074670936014678314139731, 2645765857897882173953423145637670116458353878849762362, 697959494086769971706447933872692012448345176564914902768558647, 191841143903957767415908885455470574818882025636218360168344744386790701, 1880016656963442135580928039741855844237810046670786053519490946589193702306416413, 14517453495798953553208860694865943095838997886987841681543715726871234043701037594722070669, 517920721804663191406332738844647604183254308941538062261871706278110765481904785957219953229642269716]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 3, 9, 81, 19683, 1948617, 7447082733, 56454526236591, 607355962886759589, 327634524941960422272213, 75084833344953502409743630071, 329842053215193333653241622598642301, 6307897261823042647212952625494153390210137, 92825554853992354275259096652157121655013541452507, 96858306845257683111760942458642849253339336542098295392577, 54244560645654062228019192889331154162825234484155934467030364559961, 262490121532706886100260383318685739049924517769791404416723963909872709605771, 12530363432174911347548824583493150056750152185020540387714326432867162341848821621303473, 304712965871395859899575807043164719976656702693066512136414938497014426120510366784741006692369349, 508718160840521637299234954530253486206111889498439849311894025939891704086181131011525457268771138756890936071]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]
[1, 3, 9, 81, 26244, 2657205, 19241884287, 189510218978751, 3946315328858137383, 4055902563575369941396542, 1275212006809536208751306492103, 21810478078555161408261649976252402025, 705369368808320092406513809492041893178525339, 34488189944965230614060773308708445231985541285529527, 110737014570630699718859171872478844234748567157331769413524976, 109947897702707865610855646363316553630620964367199119781891834900242139, 4369645660825450145885058651666079621751552754982028520304618089820689536182800141, 463994086297020499849233360318283641597144858257101531303130302529870307014568537747167437005, 54337783154587471735160491066365478186301024466649580512129305971290777334159400499540809231091786997673, 534129263479711786315770316147867131674746583309100903950217452971980354356991855006155411709813043027840791482775174]
[true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true]