170507

Ruby


Number of representations of 10^n as sum of k triangular numbers

k が6, 8 のときに規則性がある。

def s(k, n)
  s = 0
  (1..n).each{|i| s += i if n % i == 0 && i % k == 0}
  s
end

def A(k, n)
  ary = [1]
  a = [0] + (1..n).map{|i| 2 * s(2, i) - s(1, i)}
  (1..n).each{|i| ary << (1..i).inject(0){|s, j| s - k * a[j] * ary[-j]} / i}
  ary
end

m = 3
n = 10 ** m
(1..100).each{|i|
  a = A(i, n)
  p [i, (0..m).map{|j| a[10 ** j]}]
}

出力結果
[1, [1, 1, 0, 0]]
[2, [2, 2, 2, 2]]
[3, [3, 9, 30, 78]]
[4, [4, 32, 272, 2880]]
[5, [5, 90, 2600, 83880]]
[6, [6, 231, 20400, 2003001]]
[7, [7, 567, 147511, 46076450]]
[8, [8, 1332, 1030302, 1007141184]]
[9, [9, 2979, 6750900, 20612437776]]
[10, [10, 6341, 41591741, 397737367822]]
[11, [11, 12892, 242585717, 7258733595410]]
[12, [12, 25158, 1346684988, 125940317363157]]
[13, [13, 47346, 7145580338, 2086440134887550]]
[14, [14, 86282, 36383662861, 33132657211536701]]
[15, [15, 152778, 178404108813, 506119212593601678]]
[16, [16, 263584, 845008027992, 7459911528848051232]]
[17, [17, 444125, 3875970033454, 106366350249753658347]]
[18, [18, 732276, 17253879294006, 1470241717851559433265]]
[19, [19, 1183491, 74674844682795, 19737083066556180555180]]
[20, [20, 1877676, 314733772865202, 257743659543879717605382]]
[21, [21, 2928282, 1293659282055567, 3278919983646414241580145]]
[22, [22, 4494193, 5192410364798734, 40689036635374198080187200]]
[23, [23, 6795097, 20375281865527130, 493107574525089987331703278]]
[24, [24, 10131156, 78251281586187426, 5842412953614743357001098430]]
[25, [25, 14907935, 294415231452853070, 67741972518495737868468490110]]
[26, [26, 21667711, 1086181579309557575, 769363768363979087935689960491]]
[27, [27, 31128462, 3932591936984003709, 8565955270277141782841472118026]]
[28, [28, 44232034, 13983719082095273847, 93567288088577633432099207461496]]
[29, [29, 62203202, 48869975111328487816, 1003426663894029699966686656123132]]
[30, [30, 86621580, 167966746125385693221, 10571768629387274811665279839656675]]
[31, [31, 119508596, 568110213674533249213, 109490724124333944968633230250789316]]
[32, [32, 163432032, 1891988536729339032080, 1115383211760636782200793944815208692]]
[33, [33, 221630937, 6207453228350773887246, 11182047224644846290030035287748405496]]
[34, [34, 298164054, 20074065058884924294308, 110379330479443501083252040822091785132]]
[35, [35, 398085261, 64016029204520969002903, 1073319265602861048417006103117247591817]]
[36, [36, 527649912, 201403126399797207319455, 10285804575120179718911699867862910259766]]
[37, [37, 694556378, 625387571704231391408568, 97184762379609449976524774000135058811643]]
[38, [38, 908227531, 1917384504114038712429564, 905692791658237702524015191542400232300361]]
[39, [39, 1180137387, 5806416282772424936449833, 8328166969507939881527435674941240159366309]]
[40, [40, 1524188628, 17373991390513793373870792, 75588911774854943077103327159615202817028772]]
[41, [41, 1957147259, 51384139718062181645309168, 677412775876584392000497062810168481449715214]]
[42, [42, 2499141225, 150257061374739621991442040, 5996176890580778188141465137865434497002107219]]
[43, [43, 3174230416, 434558731461306656908319553, 52438904357215231031836671672679724885535645326]]
[44, [44, 4011056126, 1243354685616868083201616586, 453228234079329840298439460451077062095062425595]]
[45, [45, 5043578706, 3520415084517199345693237686, 3872439774194071291996868210809075098235371690996]]
[46, [46, 6311912862, 9866403039568399741129898298, 32716850282609223308302899364491285989634727446074]]
[47, [47, 7863270798, 27377811890098209253302990248, 273392774614676131191373096265691357737735250293030]]
[48, [48, 9753024192, 75234583553344059445295491860, 2260144347128520486967951684848179161216273821383334]]
[49, [49, 12045896821, 204792831768752932701195373062, 18489251254356858357656266307573641347825603283845857]]
[50, [50, 14817300520, 552313660584536111039091447827, 149703755958721844885004574115749734947557715569923275]]
[51, [51, 18154828071, 1476121338171422203406396385042, 1199965027569773574285474618847562111902378409413216239]]
[52, [52, 22159917572, 3910311168087104865707576620953, 9523917058122963247757191413928647798073666990866027565]]
[53, [53, 26949703834, 10269229046962650709324610472632, 74861559955105313394526460151288121412061943720080400585]]
[54, [54, 32659073397, 26741306953324513170973186679934, 582881468798447636141086229312530682942482686654280356123]]
[55, [55, 39442940845, 69059527431549373545582774323085, 4496333312116471695938682709590611284833198031249873762960]]
[56, [56, 47478765236, 176903230326576585020279081565070, 34369203758649563079215339334151725489171819762552655826555]]
[57, [57, 56969326647, 449563828456858107756391227471585, 260367191376079129172930958732104331105852756789322707399849]]
[58, [58, 68145784067, 1133600517649856146314420556168814, 1955146663996772955891509922824076231481504121394631479180968]]
[59, [59, 81271037154, 2836670924990303463682556984227197, 14555151412787470360435265417879386739593496900453072700239598]]
[60, [60, 96643415706, 7045356181837789546441335728620089, 107439525165909360329875870430990868820225948844037761574343956]]
[61, [61, 114600722082, 17370192446168069511184604391161256, 786474844458523986016638719951294543607178075749351774966162642]]
[62, [62, 135524653248, 42518161576201876245939760542993800, 5710055345975768956250358236796905237385631408326373491126507667]]
[63, [63, 159845630616, 103340600818653272598830031775774074, 41123477900736691449399374958920369390688767967849562762473876441]]
[64, [64, 188048067392, 249431165661412219474572136066897888, 293826384763519601255581141064012323205810133214142300147506796096]]
[65, [65, 220676104753, 597954907105160383047774668717763157, 2083045510111285315679441348576237084499343480755650816347393352446]]
[66, [66, 258339849834, 1423892346685780912063844602192014990, 14654384309170877898248097288688784990844510840153975462389983548120]]
[67, [67, 301722150225, 3368435580800175876977628166747381080, 102317384245768352281829452133694546489778068414176597888715675233672]]
[68, [68, 351585941456, 7917197742543990620104710017908320632, 709079477775636804785498424780123199317159265905437976314981750709861]]
[69, [69, 408782205786, 18490777477145605916232765302112842505, 4878127297815823739800542338919390105543601803053894787691417482165243]]
[70, [70, 474258582511, 42916680537800752287796082155968232669, 33317446949710952723514353547487955408398447989475830679889715107980059]]
[71, [71, 549068671967, 98998771169535594723882699195022964884, 225941984169921604525554918076851548688038011721442023869111577960928101]]
[72, [72, 634382077428, 226991896128039177052165518506440283304, 1521506258221441317745293648234617374041052446419454692692053290995595085]]
[73, [73, 731495231187, 517381201077910681736323071372205585572, 10175266820023070939897341529646024803077255692152224202870159036843871282]]
[74, [74, 841843053261, 1172390644366726875615775142774533107096, 67585820720007784847105363244947977089514618680757806240396624569096431479]]
[75, [75, 967011493380, 2641410829260121376663522826559131557541, 445907113171214114050457879006541480708635207512557190029378693170139367812]]
[76, [76, 1108751009206, 5917535383978282180602521992759372500931, 2922485838041651605245603596097947797733585343026418021409855549086747757504]]
[77, [77, 1268991036082, 13183338164091513672724841559059504721011, 19029121938192456659537332657312480784110581423180538480794083153946453159127]]
[78, [78, 1449855506034, 29209682281875384750830175982779105251022, 123106641779305872473880489941540146739475162629762820230499882304217613749145]]
[79, [79, 1653679476242, 64369701011602311980184573991995931271583, 791366596158525779598259320528108715110756151647674476538703507720960429133632]]
[80, [80, 1883026929760, 141099256576030704070452579260251052953372, 5055260988823061458474374300611370693663630638444610465164781012551495291996692]]
[81, [81, 2140709813901, 307674127883196148990297083958963475723277, 32093295374737135379856775155629297736381359124937683801005299910055345018708492]]
[82, [82, 2429808384412, 667442436044890490755738899308422593832971, 202499639625533040043862312173653863502153494843277443626218398801576505772271776]]
[83, [83, 2753692926347, 1440542108546769293032907917209159797387780, 1270009308541837399820586566473246614653147556197517100387053596983260830182227339]]
[84, [84, 3116046925404, 3093565453666685348533118531541298666108788, 7917625250597296899031215590507160284432996842056474526453884838170737562119747880]]
[85, [85, 3520891766426, 6610662572605959975203415436335628488892744, 49070475025400814354904156581496972387248239045050335343795888482124480410515471627]]
[86, [86, 3972613038777, 14057670597620701902012153644347705743370378, 302352801691344072512388152290387488916594816234072869711633464348193720474773774336]]
[87, [87, 4475988531393, 29750485606338854236282345993688415858263124, 1852279619772792075507504263009675700112006825174951062985331023892196550980510263097]]
[88, [88, 5036218003476, 62663695949551090834211467484425603953035016, 11283078479422067402282657089499559840483019079593902614140874845188756969957600529212]]
[89, [89, 5658954820047, 131373403511292714930456445495802120121437802, 68344912179794902439888559139444973662652493791348138073450195733710488707812312430450]]
[90, [90, 6350339544903, 274154881862118437062782426011794489047911556, 411690307375257924204783670075589754185356145383095915851179270197774795538585222655541]]
[91, [91, 7117035586934, 569519446547134931322063413270657432919655503, 2466315773095977065933386196484387620145600233152830434294712624674945427596363105142788]]
[92, [92, 7966266999250, 1177799903932894142499310753444085592327078661, 14694925954812773672812620381862645244980264410155969448081421406973530550211327324073958]]
[93, [93, 8905858534146, 2424993623998760682929042158388991640300487364, 87086995867135984830404267310685378355125983823696931051380172817468674483310994141551174]]
[94, [94, 9944278060596, 4971082727338014844510371575618155267946087589, 513372177987547476500845005972405820503712422853250255014942546681847202940966607922719730]]
[95, [95, 11090681454716, 10146524327162079495407983845731760637584712353, 3010438971112358945295073809723436351792056486474582248791503467116232443482852751748835848]]
[96, [96, 12354960077472, 20622134365328614945750886527321115137296110016, 17561865001317034355991431401049730760715063400251028202349540844598805800490204733118543152]]
[97, [97, 13747790957833, 41737216659047810127266395921039168566582703253, 101924609165750298948632610396123288952244250541341277739523961126769083841603631974407612562]]
[98, [98, 15280689803582, 84122073857452440484902427497347733040436549884, 588543933502356215777828991621313302904006531193599219974069043224412135179947953835613566588]]
[99, [99, 16966066966101, 168855666620026104198829795805684560415730663729, 3381375802514361493989633146565427878933287283293392633511053125712310039435758471772631927276]]
[100, [100, 18817286489640, 337569020292608703618931591810026288085927961928, 19330609417148743978329847749614366418319592600892466793661057390223423277408685814610773864036]]