170528(3)

Ruby


Number of ways of writing n as a sum of k squares

A186690 と関係がある。

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

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

def B(k, n)
  A([[2, 5 * k], [1, -2 * k], [4, -2 * k]], n)
end

n = 30
(1..48).each{|i| p [i, B(i, n)]}

出力結果
[1, [1, 2, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0]]
[2, [1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, 0, 0, 8, 0, 0, 4, 8, 4, 0, 8, 0, 0, 0, 0, 12, 8, 0, 0, 8, 0]]
[3, [1, 6, 12, 8, 6, 24, 24, 0, 12, 30, 24, 24, 8, 24, 48, 0, 6, 48, 36, 24, 24, 48, 24, 0, 24, 30, 72, 32, 0, 72, 48]]
[4, [1, 8, 24, 32, 24, 48, 96, 64, 24, 104, 144, 96, 96, 112, 192, 192, 24, 144, 312, 160, 144, 256, 288, 192, 96, 248, 336, 320, 192, 240, 576]]
[5, [1, 10, 40, 80, 90, 112, 240, 320, 200, 250, 560, 560, 400, 560, 800, 960, 730, 480, 1240, 1520, 752, 1120, 1840, 1600, 1200, 1210, 2000, 2240, 1600, 1680, 2720]]
[6, [1, 12, 60, 160, 252, 312, 544, 960, 1020, 876, 1560, 2400, 2080, 2040, 3264, 4160, 4092, 3480, 4380, 7200, 6552, 4608, 8160, 10560, 8224, 7812, 10200, 13120, 12480, 10104, 14144]]
[7, [1, 14, 84, 280, 574, 840, 1288, 2368, 3444, 3542, 4424, 7560, 9240, 8456, 11088, 16576, 18494, 17808, 19740, 27720, 34440, 29456, 31304, 49728, 52808, 43414, 52248, 68320, 74048, 68376, 71120]]
[8, [1, 16, 112, 448, 1136, 2016, 3136, 5504, 9328, 12112, 14112, 21312, 31808, 35168, 38528, 56448, 74864, 78624, 84784, 109760, 143136, 154112, 149184, 194688, 261184, 252016, 246176, 327040, 390784, 390240, 395136]]
[9, [1, 18, 144, 672, 2034, 4320, 7392, 12672, 22608, 34802, 44640, 60768, 93984, 125280, 141120, 182400, 262386, 317376, 343536, 421344, 557280, 665280, 703584, 800640, 1068384, 1256562, 1234080, 1421184, 1851264, 2034720, 2057280]]
[10, [1, 20, 180, 960, 3380, 8424, 16320, 28800, 52020, 88660, 129064, 175680, 262080, 386920, 489600, 600960, 840500, 1137960, 1330420, 1563840, 2050344, 2611200, 2986560, 3358080, 4194240, 5318268, 5878440, 6299520, 7862400, 9619560, 10216320]]
[11, [1, 22, 220, 1320, 5302, 15224, 33528, 63360, 116380, 209550, 339064, 491768, 719400, 1095160, 1538416, 1964160, 2624182, 3696880, 4763220, 5686648, 7217144, 9528816, 11676280, 13495680, 16317048, 20787470, 25022184, 27785120, 32503680, 40862184, 47430768]]
[12, [1, 24, 264, 1760, 7944, 25872, 64416, 133056, 253704, 472760, 825264, 1297056, 1938336, 2963664, 4437312, 6091584, 8118024, 11368368, 15653352, 19822176, 24832944, 32826112, 42517728, 51425088, 61903776, 78146664, 98021616, 115331264, 133522752, 164079696, 201364416]]
[13, [1, 26, 312, 2288, 11466, 41808, 116688, 265408, 535704, 1031914, 1899664, 3214224, 5043376, 7801744, 12066912, 17689152, 24443978, 34039200, 48210760, 64966096, 83323344, 109157152, 145532816, 185245632, 227110416, 284788010, 363737712, 448126016, 531517376, 643027632, 800145632]]
[14, [1, 28, 364, 2912, 16044, 64792, 200928, 503360, 1089452, 2186940, 4196920, 7544992, 12547808, 19975256, 31553344, 48484800, 70439852, 99602104, 142487436, 200569824, 268594872, 354052608, 476105504, 630908096, 800698080, 1008274932, 1296257144, 1648943296, 2022013760, 2457911512, 3056208064]]
[15, [1, 30, 420, 3640, 21870, 96936, 331240, 911040, 2128260, 4495430, 8972712, 16946280, 29822520, 49476840, 80027280, 127083328, 193511790, 282611280, 409172940, 590913960, 825736296, 1115671760, 1509537960, 2048372160, 2698852520, 3463029894, 4472616120, 5803339360, 7347537600, 9095661240, 11335886864]]
[16, [1, 32, 480, 4480, 29152, 140736, 525952, 1580800, 3994080, 8945824, 18626112, 36714624, 67978880, 118156480, 197120256, 321692928, 509145568, 772845120, 1143441760, 1681379200, 2428524096, 3392205824, 4658843520, 6411152640, 8705492608, 11488092896, 15000919872, 19697555200, 25593401600, 32467266240, 40864033536]]
[17, [1, 34, 544, 5440, 38114, 199104, 808384, 2641664, 7213984, 17215458, 37569728, 77129408, 149405248, 272064192, 470966912, 790414592, 1291650786, 2035437440, 3101265120, 4648909760, 6883061184, 9931183488, 13967503552, 19489000192, 27036220096, 36719672546, 48877735232, 64882013952, 85898222336, 111723674688, 142979339392]]
[18, [1, 36, 612, 6528, 48996, 275400, 1207680, 4269312, 12573540, 32041636, 73617480, 157553280, 318102912, 605381832, 1090632960, 1888224000, 3176573796, 5177295432, 8148505828, 12507419520, 18918517320, 28067389440, 40578145920, 57669043968, 81375600000, 113272212204, 154398101832, 207972274944, 279331331328, 371269791432, 484986858240]]
[19, [1, 38, 684, 7752, 62054, 373464, 1759704, 6697728, 21210156, 57739518, 140116184, 313328088, 658369608, 1305768920, 2449182384, 4387011840, 7597766246, 12766353840, 20748447108, 32728127192, 50601708504, 76895771568, 114223115480, 166029979392, 238352317656, 338575421950, 472600643976, 648718685984, 883678139136, 1195524774792, 1594639240368]]
[20, [1, 40, 760, 9120, 77560, 497648, 2508000, 10232640, 34729720, 100906760, 259114704, 606957280, 1327461600, 2738111280, 5341699520, 9915552192, 17701924600, 30615844560, 51294999960, 83279292960, 131880275664, 204949382400, 312126610080, 464844224960, 680432137440, 984382611928, 1404010658960, 1968103484480, 2724593155520, 3743846975920, 5089580732736]]
[21, [1, 42, 840, 10640, 95802, 652848, 3504816, 15266880, 55350120, 171361498, 465944304, 1145653488, 2610853840, 5595003120, 11337146784, 21817881792, 40208417466, 71565375840, 123411903160, 206218644912, 335056780464, 532597541344, 830096613360, 1266359895360, 1893781702512, 2790751314330, 4058779021584, 5809617168320, 8190877926720, 11431035439824, 15805879161632]]
[22, [1, 44, 924, 12320, 117084, 844536, 4812192, 22297792, 86075484, 283367436, 815677016, 2108077536, 5012882336, 11159625400, 23460347328, 46790491968, 89096422492, 163282917336, 289559673084, 497610124704, 830202403800, 1351064867328, 2153312518240, 3361695239232, 5140361517984, 7724269359972, 11444537517336, 16709010117184, 24015334687168, 34075597680696, 47873378766400]]
[23, [1, 46, 1012, 14168, 141726, 1078792, 6503112, 31946816, 130905236, 457207478, 1392036360, 3784029000, 9401213016, 21752359112, 47412641232, 97936966080, 192747766686, 363967164176, 663612939132, 1171941833480, 2007831887432, 3348062963344, 5456890474248, 8710505815360, 13617909938952, 20885881710454, 31527898462552, 46904811133408, 68719323996224, 99237530067544, 141662701280848]]
[24, [1, 48, 1104, 16192, 170064, 1362336, 8662720, 44981376, 195082320, 721175536, 2319457632, 6631997376, 17231109824, 41469483552, 93703589760, 200343312768, 407488018512, 793229226336, 1487286966928, 2697825744960, 4744779429216, 8110465650176, 13523760003648, 22063059606912, 35250721087168, 55204237463376, 84944161233120, 128716413627520, 192127452262272, 282507110257440, 409984511707776]]
[25, [1, 50, 1200, 18400, 202450, 1702560, 11389600, 62339200, 285385200, 1114064850, 3779134240, 11360877600, 30885301600, 77374394400, 181284196800, 401031812480, 842726826450, 1691534395200, 3262594952400, 6077725252000, 10968671291040, 19220947905600, 32802221530400, 54693728246400, 89267475949600, 142743029326162, 223991253535200, 345718693238400, 525491835433600, 786742987874400, 1161295395893440]]
[26, [1, 52, 1300, 20800, 239252, 2107560, 14797120, 85155200, 410468500, 1688240372, 6030043240, 19043826880, 54177864000, 141373532200, 343594659200, 786344740480, 1706685733012, 3532307607400, 7010460268500, 13412537087040, 24832297608040, 44603133286400, 77924078814400, 132816314883200, 221394909419840, 361407558819164, 578472382307304, 909636568464000, 1407681394953600, 2145304809169704, 3221568346322560]]
[27, [1, 54, 1404, 23400, 280854, 2586168, 19014840, 114791040, 581257404, 2513392494, 9436118328, 31274226360, 93086496360, 253106219448, 638406025200, 1511651306880, 3387901252374, 7229247074928, 14765641285044, 29018207233080, 55108831380408, 101440703660400, 181434042582840, 316176906314880, 538265644820280, 896820392178414, 1464212332875816, 2346272971038368, 3696677780664960, 5733430059474216, 8759016189382896]]
[28, [1, 56, 1512, 26208, 327656, 3147984, 24189984, 152867520, 811401192, 3681079640, 14500933104, 50376047904, 156797510688, 444306558864, 1163495873088, 2851049839680, 6597606440936, 14512424533488, 30505974273096, 61591664700384, 119983597365744, 226303038736128, 414352982942304, 738358447579200, 1283861585339424, 2183013918429512, 3635198568784944, 5936645280445376, 9523977599887936, 15031150280922384, 23358459198626496]]
[29, [1, 58, 1624, 29232, 380074, 3803408, 30488976, 201299904, 1117791544, 5310177994, 21911472464, 79683652176, 259172461296, 765264394832, 2081117152992, 5278842061632, 12613606876714, 28597873335584, 61865177248552, 128334714844560, 256462892399504, 495608683851936, 928859670458448, 1692575040345792, 3006249397711056, 5216545741621770, 8858986222461872, 14744872013818688, 24088488255932096, 38685989126061808, 61146089973555552]]
[30, [1, 60, 1740, 32480, 438540, 4563672, 38099040, 262336320, 1521151500, 7553367900, 32592806520, 123909200160, 420775407200, 1294230433560, 3655476494400, 9600504649920, 23690038522380, 55357851461880, 123233778584940, 262666576468320, 538518903906552, 1066248567851520, 2045337982427040, 3811126447857600, 6914885182908000, 12245499738857172, 21207036616238520, 35971884261238720, 59847918853661760, 97810513435518360, 157231420280219584]]
[31, [1, 62, 1860, 35960, 503502, 5440872, 47229864, 338599360, 2046701220, 10604798246, 47775740520, 189619489320, 671636175480, 2150888860840, 6309132101904, 17159352237120, 43733123309262, 105329431676880, 241275541236780, 528400328616040, 1111479953165352, 2254843638530128, 4426891212365160, 8434447043309760, 15633379938039144, 28255162424156774, 49899492947343864, 86254925765004640, 146147632445771200, 243076976890113528, 397406328481552528]]
[32, [1, 64, 1984, 39680, 575424, 6448000, 58115328, 433131008, 2724906944, 14709082432, 69079796864, 285848172800, 1054968628480, 3515371815296, 10706472186368, 30156949879296, 79395777333184, 197101549419648, 464573878394560, 1045365667116800, 2256126097001600, 4689805691447296, 9423431444080384, 18357649066674688, 34759556728866048, 64119097033510336, 115474354635222656, 203405736067767808, 350982387781513728, 594109828315028864, 987881573708613120]]
[33, [1, 66, 2112, 43648, 654786, 7598976, 71015296, 549441024, 3592319808, 20171792322, 98614192512, 424874032512, 1632114867328, 5654728387968, 17875388306688, 52141706828288, 141820480610754, 362929297530624, 880219339775424, 2034965483337600, 4506220683398016, 9598370934442752, 19739221443625344, 39316657099703808, 76047426405791104, 143176642846968258, 262953752848837248, 471999462924701184, 829405814646351360, 1428832080883861632, 2416450963949279488]]
[34, [1, 68, 2244, 47872, 742084, 8908680, 86217472, 691558912, 4692511428, 27371629892, 139099807880, 623201303808, 2489047659264, 8959303016840, 29382088665600, 88742373537280, 249369222884036, 657886900167816, 1641869055038916, 3899884805017344, 8860642360669320, 19339935141232640, 40707711590868224, 82900782829125120, 163797472570290944, 314751918832242124, 589511537253470856, 1078301571249403392, 1929572788503833088, 3383020746695382408, 5819255124075374080]]
[35, [1, 70, 2380, 52360, 837830, 10392984, 104039320, 864089600, 6077113420, 36774470110, 194015502744, 902784041880, 3744835385480, 13992143079320, 47578912132400, 148753125911040, 431833448394950, 1174553336992560, 3016461775970020, 7361385861881240, 17160396820563864, 38381971776042800, 82689238761879960, 172174741181345280, 347497817081977240, 681525527444317150, 1301746850099643080, 2426411195927285280, 4421575623848670720, 7889409364696389320, 13803058326450694448]]
[36, [1, 72, 2520, 57120, 942552, 12068784, 124830048, 1072272960, 7806968280, 48949482920, 267772521744, 1292543231328, 5562557800800, 21555364466160, 75951250082496, 245716726338240, 736831099167192, 2066216674168080, 5460799823164920, 13692203696753568, 32748641010875664, 75059361782712576, 165514090360142880, 352371149981311680, 726465611491844448, 1454148845606087352, 2832525877217028048, 5380289107609290560, 9984123911261833920, 18129960445211327088, 32262229857439895616]]
[37, [1, 74, 2664, 62160, 1056794, 13954032, 148972656, 1322047296, 9953399304, 64587557050, 365921147824, 1830232825776, 8163258314256, 32778380918704, 119597548195872, 400204562625984, 1239391811991194, 3583005215371488, 9745233570636952, 25105772340917616, 61609295691064944, 144700202292539232, 326597524550490288, 710935642739815488, 1497196642542832176, 3058672552252501626, 6075984718042868304, 11761007346738767552, 22225028881973326912, 41072046351699738384, 74337473128386333600]]
[38, [1, 76, 2812, 67488, 1181116, 16067768, 176886048, 1620116928, 12599607484, 84522263724, 495394207384, 2564719221344, 11843630888736, 49234074774904, 185886180236992, 643060422614592, 2056130097966268, 6127365507990040, 17150568272891100, 45397380449863456, 114303284464647704, 275101130649948672, 635553953336625376, 1414581434263117632, 3043086948436643616, 6344945154722340932, 12853691613921890904, 25354342195911065920, 48791664731735114432, 91762733368297476344, 168923174867580925248]]
[39, [1, 78, 2964, 73112, 1316094, 18430152, 209027208, 1974024000, 15842203572, 109753614230, 664792507080, 3558747875592, 16998268681368, 73090383442056, 285345150337104, 1019962575303360, 3365941445206782, 10338119052687504, 29777240693878236, 80985628629424584, 209215435001112072, 515986117889137168, 1220155819685626824, 2776855877436803136, 6102142531936618440, 12985433742135985494, 26826945551844218520, 53925194558265313504, 105677341468592172864, 202264658178293594520, 378706598865712166608]]
[40, [1, 80, 3120, 79040, 1462320, 21062496, 245893440, 2392224640, 19792883760, 141474881680, 884717790112, 4892280943680, 24147448985920, 107306430665440, 432855539095680, 1597770789783168, 5439867081224240, 17216214394392480, 51024388607161840, 142581364752948160, 377925692648758176, 955127222570959360, 2311828718036596160, 5379709468315628160, 12076325113647462720, 26228423144185138736, 55258802243177832480, 113192359015710870400, 225894020902792394880, 440008785650521651680, 837922349252103601536]]
[41, [1, 82, 3280, 85280, 1620402, 23987296, 288024672, 2884169600, 24580257680, 181102774194, 1168159340512, 6666500979424, 33971596798880, 155884281325280, 649237878131776, 2473266921648768, 8683708343211698, 28310601003939520, 86322811423907760, 247827452982576480, 673977940881914976, 1745459331597357504, 4324346553745956320, 10289395349757357440, 23594791016741569248, 52302207833734194738, 112373740165845667616, 234571441000474008960, 476716600185913087360, 945009739742638490784, 1830368645195764804928]]
[42, [1, 84, 3444, 91840, 1790964, 27228264, 336005824, 3460389504, 30351837684, 230311264148, 1530940938408, 9008588006208, 47353759443648, 224189683712232, 963342807437952, 3785076255920512, 13698191148446196, 45989835413529000, 144242851393605300, 425421945992541120, 1187013596538690984, 3150104358610638848, 7988222608927186752, 19435041844739025792, 45526484181023926976, 103000076309304020028, 225683472479132529960, 480070370987529840000, 993544787069503165056, 2004395623432262776296, 3948627822151732074880]]
[43, [1, 86, 3612, 98728, 1974646, 30810360, 390469240, 4132584832, 37276198620, 291069396046, 1992235478520, 12077390668920, 65431639315112, 319357828709752, 1414784111195760, 5729779718820480, 21363058099953526, 73834657781521392, 238149668458074388, 721480863173653240, 2065271888000259960, 5616205930088422640, 14577365408975111160, 36264257647114136448, 86778165276794876920, 200380650231492572366, 447752053048303878504, 970595903355236181408, 2045589436006114852224, 4199859825762325534824, 8415088149377413297520]]
[44, [1, 88, 3784, 105952, 2172104, 34759824, 452097184, 4913720768, 45545317576, 365683414008, 2575155209264, 16070126802848, 89660973247648, 450803250081360, 2057484301193024, 8583503503488320, 32953489081394376, 117199564191245360, 388649134382308008, 1209243743998597472, 3550983885332760624, 9894549884992236288, 26286715322506463200, 66864779767899226432, 163448683981013707936, 385212119343597870632, 877815757629273245552, 1939104848237769705152, 4161780665859803103040, 8695931180729202272720, 17721547148427132981696]]
[45, [1, 90, 3960, 113520, 2384010, 39104208, 521624400, 5818127040, 55377103320, 456843568810, 3307426231824, 21230264670480, 121892317700400, 630856567748880, 2964241181293920, 12730613263674432, 50299827862307850, 184008239944832160, 627163962734020360, 2003714170080820560, 6035410491750694224, 17231096106056263200, 46854014968659908880, 121860812879339175360, 304297378385575293840, 731964494785139375850, 1701047831240174822640, 3829243253441132878400, 8369306397107313831360, 17797019620513174248240, 36888834239882740396512]]
[46, [1, 92, 4140, 121440, 2611052, 43872408, 599840736, 6861602880, 67018125420, 567675983868, 4222156618424, 27856753396128, 164463601475040, 875554895055320, 4232569247463744, 18701557198852032, 76004850661311596, 285869719559152440, 1001109838673418060, 3283509936928900832, 10143480948171060024, 29670177354160925184, 82571796820419222560, 219582199650819476160, 560115286465036588512, 1375122044337814243252, 3259052873842515520248, 7476314912066158264000, 16640395332885527444800, 36011633486994722316888, 75919437264083991860928]]
[47, [1, 94, 4324, 129720, 2853934, 49094696, 687593832, 8061527232, 80746553284, 701799979526, 5358708267816, 36314789847016, 220311144761016, 1205617455195240, 5992123438556048, 27222410400253248, 113736905985171502, 439630664708137296, 1581315551638626444, 5323141172986920744, 16862566236863499240, 50529207616912045008, 143916122317077701160, 391301278317733856192, 1019604050911451615784, 2554844982812883861574, 6175012304042413993784, 14435587334443681893472, 32719823078748978144448, 72062956954447543145784, 154520158805605372057872]]
[48, [1, 96, 4512, 138368, 3113376, 54802752, 785791872, 9436974336, 96875315616, 863391275488, 6763683414720, 47048329445760, 293102217821056, 1647643350384192, 8414075863671552, 39279288232247040, 168622365198254496, 669515873081977536, 2472562531531980832, 8540227814481475200, 27736395024393085632, 85134042042443029504, 248139579890464622208, 689791789560863266560, 1835986185002939939712, 4695338975085181485216, 11573413786349169929664, 27571377202896834548992, 63640852572427508785920, 142646020621279910254656, 311097167722066085728512]]