151219(5)

Ruby

Frobeniusの硬貨交換問題(5)

ary.size が2のときは簡単な式を利用するようにし、
さらに調べてみた。

require 'prime'

def f(ary)
  # ary = [a, b], (a, b) = 1のとき
  return ary[0] * ary[1] - ary[0] - ary[1] if ary.size == 2
  m = ary.max
  s0 = (1 << m) - 1
  s = 1 << m - 1
  a = 0
  while s != s0
    f_max = a if s >> m - 1 == 0
    a += 1
    s += 1 << m if ary.any?{|i| (s >> m - i) & 1 == 1}
    s >>= 1
  end
  f_max
end

def A037165(ary, n)
  ary[0..n].each_cons(2).map{|a| f(a)}
end

def A138989(ary, n)
  ary[0..n + 1].each_cons(3).map{|a| f(a)}
end

def A138990(ary, n)
  ary[0..n + 2].each_cons(4).map{|a| f(a)}
end

def A138991(ary, n)
  ary[0..n + 3].each_cons(5).map{|a| f(a)}
end

def A138992(ary, n)
  ary[0..n + 4].each_cons(6).map{|a| f(a)}
end

def A138993(ary, n)
  ary[0..n + 5].each_cons(7).map{|a| f(a)}
end

def A138994(ary, n)
  ary[0..n + 6].each_cons(8).map{|a| f(a)}
end

N = 500
p_ary = Prime.each(10 ** 4).to_a
p A037165(p_ary, N)
p A138989(p_ary, N)
p A138990(p_ary, N)
p A138991(p_ary, N)
p A138992(p_ary, N)
p A138993(p_ary, N)
p A138994(p_ary, N)

出力結果
[1, 7, 23, 59, 119, 191, 287, 395, 615, 839, 1079, 1439, 1679, 1931, 2391, 3015, 3479, 3959, 4619, 5039, 5615, 6395, 7215, 8447, 9599, 10199, 10811, 11447, 12095, 14111, 16379, 17679, 18767, 20423, 22199, 23399, 25271, 26891, 28551, 30615, 32039, 34199, 36479, 37631, 38807, 41579, 46619, 50171, 51527, 52895, 55215, 57119, 59999, 63999, 67071, 70215, 72359, 74519, 77279, 78959, 82343, 89351, 94859, 96719, 98591, 104279, 110879, 116255, 120407, 122495, 126015, 131027, 136151, 140615, 144395, 148215, 153647, 158399, 163199, 170543, 175559, 180599, 185759, 189215, 193595, 198015, 204287, 209759, 212519, 215291, 222747, 232307, 238139, 244019, 249995, 255015, 264159, 271439, 281879, 294839, 303575, 312471, 319215, 323759, 328319, 337535, 346911, 354015, 358799, 363599, 370871, 376991, 380687, 389339, 403199, 410879, 414731, 421191, 429015, 434279, 443519, 454271, 461031, 470579, 482999, 495599, 508343, 521267, 531431, 540215, 547595, 556499, 566999, 574559, 583679, 592895, 606791, 625655, 643167, 654479, 664199, 674039, 678971, 683927, 693863, 713975, 729311, 734447, 739595, 755111, 770879, 776159, 781451, 802715, 824459, 835379, 851903, 868607, 879839, 889239, 900591, 919631, 937019, 946719, 958431, 972179, 986039, 1003967, 1020095, 1030215, 1038359, 1050599, 1062959, 1071215, 1087823, 1100399, 1112999, 1125719, 1134215, 1159847, 1183739, 1190279, 1196831, 1207791, 1221015, 1236527, 1252151, 1265615, 1297199, 1324799, 1338623, 1359539, 1380599, 1399479, 1413711, 1430399, 1454399, 1473791, 1485951, 1500615, 1510439, 1520279, 1542527, 1569983, 1605207, 1630727, 1638395, 1651215, 1661519, 1671839, 1684799, 1692599, 1700411, 1721307, 1739759, 1750319, 1803359, 1857759, 1874151, 1893359, 1929239, 1968383, 2002175, 2027771, 2036327, 2044895, 2059215, 2079347, 2096699, 2105399, 2117015, 2143259, 2175599, 2193359, 2202251, 2211167, 2220095, 2235015, 2261979, 2298219, 2328659, 2359259, 2387015, 2402495, 2418015, 2439827, 2458619, 2477459, 2496395, 2524871, 2553599, 2569599, 2582447, 2592095, 2608215, 2621159, 2634119, 2660135, 2709215, 2752271, 2768891, 2778887, 2822255, 2869631, 2879807, 2900183, 2937759, 2961839, 2982503, 3013679, 3038039, 3058991, 3080015, 3122207, 3164831, 3182651, 3193367, 3218399, 3257999, 3297819, 3334259, 3378179, 3433559, 3470759, 3489419, 3500639, 3511871, 3523127, 3545663, 3587199, 3621399, 3644271, 3690159, 3728759, 3763535, 3798599, 3845399, 3900615, 3928307, 3956111, 3976031, 3988007, 3999995, 4024019, 4052159, 4084415, 4108727, 4133063, 4181975, 4231223, 4264215, 4301439, 4330559, 4343051, 4355567, 4380623, 4426779, 4456319, 4494335, 4532639, 4549679, 4571039, 4583879, 4609583, 4648319, 4704479, 4795955, 4857611, 4879671, 4910639, 4963919, 5004167, 5017595, 5044499, 5098499, 5139287, 5152895, 5180159, 5212079, 5239511, 5262431, 5299167, 5331479, 5386919, 5452215, 5470919, 5489639, 5513099, 5536599, 5583719, 5631119, 5654879, 5669159, 5688215, 5712095, 5736015, 5779179, 5822559, 5851551, 5899991, 5943839, 5968239, 6012267, 6061427, 6095951, 6120671, 6194951, 6305039, 6375599, 6421139, 6451595, 6477015, 6497399, 6517799, 6589367, 6677019, 6713279, 6759935, 6822527, 6853919, 6895839, 6964271, 7027775, 7059647, 7075595, 7107539, 7144919, 7177031, 7203851, 7219967, 7236095, 7263015, 7300787, 7333259, 7349519, 7371215, 7414703, 7447439, 7480199, 7529519, 7562495, 7612031, 7678415, 7739487, 7778519, 7800839, 7828799, 7845599, 7896035, 7980575, 8031551, 8059911, 8099699, 8139599, 8168159, 8231079, 8305907, 8357855, 8404191, 8439015, 8479727, 8532215, 8596587, 8672975, 8726111, 8755671, 8791215, 8814959, 8904059, 8993999, 9029999, 9084179, 9120395, 9174791, 9229439, 9265919, 9326879, 9381959, 9437147, 9486395, 9517215, 9597503, 9690743, 9728159, 9784319, 9916031, 10010891, 10029887, 10074239, 10131479, 10163339, 10214379, 10272015, 10316927, 10355519, 10394159, 10490999, 10568999, 10588511, 10608047, 10653659, 10784459, 10883399, 10909799, 10949471, 10989215, 11022395, 11055615, 11082239, 11128859, 11182331, 11235867, 11282879, 11323199, 11363639, 11424335, 11485319, 11546339, 11621271, 11709983, 11833535, 11916287, 11957759, 11978519, 11999291, 12020087, 12103319, 12208019, 12277979, 12341159, 12397415, 12439727, 12460895, 12496215, 12524519, 12552839, 12609575, 12652247, 12702059, 12780599]
[1, 4, 13, 30, 53, 80, 117, 131, 194, 286, 293, 520, 613, 522, 1310, 858, 1001, 929, 1610, 1418, 1322, 1499, 1421, 2941, 3300, 3533, 3710, 3957, 2065, 2241, 3685, 4595, 3697, 3930, 5956, 12074, 5509, 5874, 14690, 7968, 6084, 6373, 12413, 12740, 6694, 21878, 12047, 16950, 17477, 11219, 14223, 10514, 8730, 32624, 34175, 17894, 18826, 15461, 26040, 14329, 9708, 11521, 31930, 32653, 13160, 12772, 15908, 20595, 40597, 25475, 19784, 20138, 68990, 29102, 29939, 22619, 51741, 53984, 20898, 29895, 31004, 31613, 47408, 38978, 39947, 30128, 68701, 70380, 71453, 55556, 46261, 78081, 80834, 82001, 51395, 87013, 39760, 31777, 71681, 40060, 41079, 157625, 80519, 82501, 44558, 45060, 174920, 89553, 91046, 183299, 75889, 126280, 57994, 39714, 69448, 137813, 84882, 212210, 108408, 65896, 112390, 92880, 68399, 56719, 57415, 59615, 60327, 76967, 267530, 109958, 184742, 82491, 114917, 193784, 195581, 71523, 58105, 63825, 94901, 112449, 113578, 225773, 227150, 117432, 64698, 84833, 243960, 245957, 88483, 88983, 257840, 259893, 135974, 136674, 277534, 97523, 100213, 290781, 178969, 446969, 97575, 107783, 190501, 475784, 141687, 143552, 332964, 253258, 206843, 259338, 177304, 178713, 268058, 139463, 184980, 187769, 189218, 284344, 289130, 114541, 395670, 398213, 242652, 606635, 179811, 181910, 628865, 104483, 118763, 225594, 155697, 157051, 179217, 702689, 207747, 291104, 366325, 298404, 746015, 376694, 380986, 512084, 151012, 123753, 168848, 545277, 331259, 414419, 418921, 336965, 562900, 565933, 429986, 251002, 437906, 110996, 112074, 932279, 273404, 160695, 153479, 177759, 229761, 677350, 680677, 412979, 299519, 695041, 700350, 529613, 711958, 205781, 367788, 733093, 735570, 739037, 448187, 750973, 1139228, 463905, 472142, 790002, 481424, 484835, 352541, 815361, 824234, 827921, 288963, 289783, 515833, 645213, 862957, 522923, 654888, 658931, 338815, 898084, 224483, 555109, 924630, 233372, 410690, 958240, 487037, 278704, 427308, 500809, 342939, 438475, 1523369, 1533860, 780073, 784544, 637957, 1062670, 466401, 305981, 308049, 664665, 1121137, 247347, 356563, 697889, 1165010, 1169373, 1172500, 595007, 336379, 1199521, 1815449, 921075, 382742, 428670, 429236, 337165, 292908, 566261, 568007, 796801, 1327340, 1331997, 1339322, 582891, 518858, 687835, 693232, 361198, 363072, 539983, 1429653, 622827, 1446293, 1449770, 734622, 415769, 640253, 510850, 511456, 1139011, 914213, 1525820, 772899, 525077, 381135, 685103, 695217, 978138, 706244, 1648677, 564244, 1671037, 1679242, 1693457, 580868, 1716117, 1724432, 747851, 2611739, 1054321, 1325346, 767256, 468715, 409305, 1367148, 1372991, 1102625, 1110133, 568976, 575200, 1130981, 1887340, 1423834, 1143848, 1149107, 1921573, 1931201, 2917304, 604284, 671265, 1196569, 1999173, 1211293, 875438, 1226113, 440220, 329917, 475776, 723569, 2143761, 1297427, 1622444, 1631356, 497489, 422223, 964604, 764343, 2261104, 2277661, 1724595, 555770, 605720, 1180600, 2356757, 2366502, 1027952, 3579134, 1442917, 2403970, 2410237, 1454747, 1047599, 2437201, 2447130, 1843478, 935993, 1245340, 1252609, 849403, 2513501, 860443, 660850, 722265, 1116412, 1952296, 1565765, 2612400, 893513, 557991, 904993, 1614816, 1163174, 1168491, 1633637, 768535, 658166, 941463, 1056696, 4209335, 1216379, 957107, 796419, 687963, 978781, 1754088, 4385225, 2201519, 626457, 630214, 1511494, 1023403, 3032081, 1035523, 1036983, 3085584, 1864145, 3116084, 3140574, 2364677, 1905899, 764600, 3209481, 1626045, 1104114, 524606, 699885, 3340130, 1450478, 3365484, 2032673, 2552783, 3411185, 1483011, 3443261, 3461484, 734470, 904338, 3527333, 3532760, 1534041, 1095056, 759234, 2728271, 5463149, 5483000, 2206466, 2213771, 2768069, 1601239, 2788067, 2808116, 1620006, 1894474, 1899003, 1287710, 1288596, 1301364, 1078476, 926696, 1320955, 3954824, 3976701, 3989380, 3997453, 4003230, 1036631, 850183, 2454185, 4100834, 1558910, 2078585, 4151277, 2502059, 3130248, 3139091, 1589935, 2114050, 1828294, 1185233, 2142638]
[1, 4, 9, 23, 42, 67, 83, 101, 125, 199, 262, 335, 367, 393, 492, 593, 704, 807, 873, 990, 817, 950, 1101, 1353, 2039, 2624, 2371, 1494, 1431, 1640, 2927, 2368, 2875, 2667, 3570, 3348, 3625, 3918, 4531, 3816, 4831, 4543, 9357, 4819, 4131, 6611, 5735, 10483, 9078, 9166, 6761, 6929, 6280, 22333, 10302, 10793, 12639, 13022, 10251, 7017, 6828, 9713, 19343, 10879, 9091, 8294, 13266, 15183, 20818, 14660, 13436, 14386, 18009, 18664, 17061, 17634, 31513, 15898, 17273, 16807, 25557, 21076, 31890, 24262, 22830, 23501, 30101, 42503, 25349, 37495, 38322, 47425, 60871, 28500, 24449, 26693, 18346, 22399, 18926, 28699, 30119, 46253, 46739, 37546, 32002, 32913, 51091, 51601, 53309, 46904, 63142, 43519, 33316, 35381, 51129, 69867, 54018, 61487, 45061, 49423, 41685, 52496, 40642, 38294, 37376, 40003, 43990, 54670, 68364, 62319, 62829, 63918, 65351, 145340, 47973, 44616, 37959, 54341, 57442, 94651, 84362, 169124, 86413, 55401, 52263, 73876, 147571, 76269, 69593, 77714, 155231, 63428, 113903, 102041, 78020, 68371, 79987, 98496, 112446, 72503, 77688, 80110, 119906, 98105, 98699, 78644, 93186, 93760, 171536, 117518, 149791, 119483, 120623, 121920, 102899, 158397, 126146, 91244, 85084, 100560, 238055, 200742, 153022, 125092, 124661, 127561, 81579, 87644, 81396, 135814, 100373, 117509, 130005, 144116, 113968, 242191, 135755, 188017, 215431, 216481, 156079, 114533, 82917, 110014, 137301, 274553, 274991, 237365, 279709, 281452, 338519, 192536, 191555, 175168, 91007, 81976, 89243, 190574, 124419, 111267, 100917, 144143, 204349, 408403, 342478, 231500, 233601, 299330, 351623, 216191, 158421, 185391, 273624, 549449, 443419, 371748, 206969, 455359, 289347, 293162, 184321, 218983, 302442, 271081, 273344, 491089, 618961, 196397, 230548, 215346, 428002, 430679, 433888, 434436, 375839, 296275, 155624, 156326, 188369, 462317, 192910, 188369, 195395, 362304, 249447, 246393, 252990, 301171, 253313, 308500, 1018479, 620179, 624062, 228756, 531337, 358379, 271622, 202255, 225203, 373082, 186052, 194172, 290029, 582507, 700127, 877497, 443897, 304062, 261227, 902948, 733774, 286096, 216311, 374612, 197244, 259211, 222540, 394622, 439358, 663672, 799195, 575128, 449789, 342525, 454512, 377217, 324316, 253711, 285524, 310037, 431201, 482111, 1084199, 547831, 373571, 369791, 304389, 447530, 380402, 760049, 762912, 576986, 464593, 272203, 198068, 214097, 292108, 546346, 335468, 385132, 455351, 720310, 727671, 397081, 468254, 741307, 578609, 527362, 656954, 484848, 589315, 307856, 362507, 367547, 781565, 916884, 692950, 467055, 434969, 471450, 943672, 946048, 950015, 717297, 527971, 1442973, 1451401, 460535, 495513, 499196, 548331, 471159, 469878, 678704, 350310, 267078, 242970, 365644, 587427, 718826, 1079081, 928205, 446069, 336776, 375999, 456517, 525971, 972411, 1145347, 468469, 398498, 542458, 881469, 1014970, 795047, 721699, 900153, 1201987, 1446139, 1209148, 812080, 816001, 1047230, 1226273, 824136, 824778, 682507, 753196, 688236, 589337, 549814, 437809, 647516, 780367, 1302459, 1306202, 721622, 501375, 476614, 673799, 900896, 814241, 904094, 593022, 554276, 475116, 702522, 770853, 851752, 711257, 576004, 487187, 582543, 731869, 1098522, 1256747, 503698, 555201, 460667, 908689, 831311, 710610, 836277, 716485, 1551899, 723796, 1875141, 863234, 864936, 649667, 548820, 614849, 702650, 458491, 437058, 633806, 1122859, 1013438, 925398, 932047, 936996, 797796, 1149899, 2069809, 627337, 660387, 758901, 2646312, 1187339, 530885, 518291, 611811, 1563720, 3647599, 1379039, 1378222, 1842051, 1116532, 1238384, 1598900, 1250296, 950606, 1615677, 820100, 1139396, 691575, 965863, 569782, 572416, 1078556, 1699371, 1707273, 2395703, 2997224, 872668, 766199, 593321, 953073, 892307, 1379849, 1554532, 2080928, 2082116, 1791241, 1401436, 1402262, 1067685, 1063541, 1074916, 1174897]
[1, 4, 9, 23, 31, 54, 66, 101, 125, 143, 200, 261, 285, 307, 398, 434, 588, 563, 672, 708, 659, 717, 935, 1078, 1748, 1816, 1135, 1173, 1104, 1277, 1911, 1975, 2188, 2111, 2680, 2593, 2683, 3266, 2861, 3297, 3757, 3996, 4198, 3275, 2953, 3457, 4668, 6688, 7716, 5273, 5136, 5491, 5336, 7062, 7475, 8163, 10758, 7331, 5815, 5899, 6272, 7941, 8598, 8391, 6587, 7012, 10949, 11139, 12835, 11174, 10598, 11514, 13238, 12684, 14029, 12661, 11315, 13913, 12052, 15171, 18434, 17287, 21548, 16889, 18444, 20843, 23358, 20110, 17514, 31943, 29449, 39761, 22907, 17698, 21463, 15627, 15300, 16149, 15229, 22207, 26284, 32885, 28154, 28444, 25150, 29455, 36416, 36776, 40730, 42096, 32792, 28809, 30231, 29766, 37878, 47428, 46945, 34313, 37225, 37561, 31093, 34317, 31158, 28716, 29084, 32993, 35482, 44604, 46548, 46926, 51005, 44600, 53335, 40904, 35036, 31543, 34094, 38601, 51863, 73617, 74626, 76351, 47736, 47137, 48128, 61277, 63118, 62559, 63580, 64755, 54362, 53739, 90058, 40880, 58066, 58332, 63445, 74342, 60911, 62152, 62536, 63891, 80267, 74801, 63527, 66864, 73372, 85784, 95857, 104349, 105974, 77622, 107222, 79567, 93548, 112241, 65188, 77451, 78712, 84489, 150004, 135278, 102738, 96570, 98189, 63231, 72667, 66307, 64427, 92076, 81905, 94231, 94885, 92146, 97350, 99061, 108132, 166187, 152147, 118641, 104463, 71442, 76744, 94976, 109585, 234966, 185461, 186045, 238463, 211738, 156935, 170429, 144647, 69279, 76496, 72729, 73183, 102103, 92978, 81053, 89887, 134350, 169110, 256138, 206911, 188634, 209240, 211551, 179416, 145092, 145350, 157626, 244200, 367286, 278806, 188847, 136984, 123989, 211411, 126990, 158414, 173041, 203690, 221513, 191041, 410021, 169262, 168119, 181599, 197909, 321003, 288190, 371215, 291235, 220991, 144077, 129706, 140056, 173596, 159074, 166296, 176700, 145277, 209930, 224002, 175035, 188024, 232329, 203346, 237431, 515324, 517106, 187633, 212907, 268341, 231792, 184059, 159295, 149541, 139513, 158667, 174019, 267851, 437349, 584373, 392908, 256603, 240250, 216131, 521358, 231980, 181211, 202920, 185364, 168231, 204643, 189365, 329513, 395812, 498751, 444441, 403392, 289869, 312488, 295637, 234010, 235130, 215150, 206003, 285401, 361059, 432443, 484871, 316618, 338092, 225650, 281300, 346202, 325440, 649343, 419821, 386789, 248348, 162910, 178745, 185932, 235420, 293005, 309002, 331994, 335413, 342251, 340354, 340980, 344445, 519141, 435662, 436442, 378672, 441405, 270576, 259619, 337112, 307461, 608923, 612816, 372221, 373179, 373843, 433724, 630700, 710725, 635721, 412273, 415692, 1158206, 314351, 395450, 396422, 336855, 402111, 378401, 406236, 285248, 236826, 217650, 210743, 322993, 461377, 647958, 723621, 368729, 316074, 316374, 263469, 358527, 453423, 684588, 367911, 350696, 374921, 471353, 590299, 712074, 598281, 596538, 801326, 902163, 906856, 728173, 664189, 732518, 736845, 674039, 737390, 534487, 503053, 627666, 426070, 427626, 384874, 410279, 520232, 649848, 1115598, 566577, 441928, 439755, 400887, 504659, 677093, 678065, 460570, 459019, 417136, 403519, 561433, 565886, 570743, 479017, 395628, 434681, 485952, 584901, 974496, 428781, 468164, 427534, 380410, 755744, 513205, 611255, 612871, 492779, 625648, 501795, 558041, 676519, 460068, 489559, 508741, 410943, 369997, 411704, 418332, 461237, 841360, 842418, 602160, 731644, 685223, 692505, 797569, 503859, 582307, 586280, 707215, 1066324, 474910, 485291, 456370, 523470, 1098561, 1000241, 1005354, 1225824, 926007, 927127, 749023, 749525, 805677, 873625, 762487, 759612, 647220, 583607, 532067, 410405, 477020, 986409, 799955, 1327875, 1998148, 809872, 675287, 558179, 516979, 687757, 829325, 1130568, 1136005, 1781133, 1393961, 1049311, 1256343, 849866, 752002, 978173, 765283, 721380]
[1, 4, 9, 16, 31, 41, 64, 63, 102, 143, 169, 216, 203, 264, 304, 381, 470, 502, 538, 562, 592, 638, 769, 989, 1360, 1008, 929, 961, 995, 1051, 1530, 1582, 1777, 1694, 2084, 2140, 2369, 2288, 2527, 2778, 3399, 2721, 2859, 2698, 2756, 3035, 3613, 5800, 4765, 4349, 4204, 4535, 4613, 5807, 6190, 7374, 6721, 4892, 4988, 5337, 5423, 5597, 7063, 6218, 5961, 6378, 8632, 8443, 10061, 9080, 9200, 9711, 10302, 10831, 10239, 9214, 10537, 10737, 10849, 12308, 15499, 13498, 15083, 14303, 16688, 17299, 14823, 15083, 15211, 25461, 26180, 16799, 15602, 16225, 13479, 13112, 12250, 14065, 13660, 20584, 21361, 22302, 22530, 23323, 22866, 23685, 27611, 30253, 36537, 25869, 23681, 25748, 26529, 24195, 30306, 41663, 28941, 29778, 30048, 28335, 23822, 26922, 23711, 23268, 24920, 28068, 31228, 34524, 37103, 39596, 37703, 38656, 33803, 31051, 26665, 29236, 27910, 36240, 44678, 66336, 48674, 44322, 41152, 43829, 43154, 39463, 53735, 57417, 54131, 37125, 47354, 43167, 36245, 34671, 49903, 48311, 52407, 48318, 53415, 51801, 52119, 50549, 64795, 52462, 55705, 56051, 68417, 61856, 86780, 81050, 71328, 71496, 73195, 73369, 74846, 60840, 57831, 72146, 69145, 70584, 109789, 93824, 81981, 77921, 54057, 57694, 58146, 56194, 53123, 75964, 70355, 74460, 69123, 81517, 80738, 83552, 98508, 124945, 96165, 86837, 66362, 66524, 69322, 81237, 103284, 166006, 150928, 166800, 186903, 122659, 142672, 132698, 63861, 61459, 68582, 62161, 54557, 81688, 71106, 72815, 84327, 118961, 135290, 172181, 172663, 172915, 161951, 133845, 127330, 133490, 129367, 145938, 200070, 247321, 161645, 127880, 108703, 94129, 94539, 113371, 132523, 134766, 174367, 162651, 166193, 132557, 148891, 141412, 168967, 170998, 234765, 259372, 261937, 188259, 122592, 123042, 118359, 131861, 103205, 140859, 156324, 135025, 113566, 193004, 164607, 142752, 158967, 189308, 170609, 143843, 442208, 159051, 177115, 153101, 191930, 164038, 148319, 116359, 113511, 123226, 144091, 164844, 232758, 388963, 321126, 237615, 211651, 200837, 144709, 168215, 157841, 169769, 132139, 160267, 145017, 177355, 171764, 303864, 330505, 333830, 334826, 269593, 269879, 228362, 199109, 183585, 200667, 164415, 195808, 252543, 332177, 289682, 293419, 291622, 212872, 213116, 237221, 299760, 304310, 383216, 309009, 224387, 156283, 150062, 159368, 162161, 172229, 273178, 275897, 263391, 222128, 315415, 300052, 271447, 288170, 401253, 372130, 293235, 351300, 235559, 236189, 245825, 284005, 272752, 459611, 348501, 309026, 328586, 350333, 353586, 516892, 518188, 383339, 340783, 344022, 270491, 283164, 330353, 285240, 273839, 336312, 336904, 222699, 204107, 197374, 190447, 195821, 282945, 431125, 498629, 330066, 277181, 298231, 232191, 227657, 324986, 326462, 259390, 292242, 332385, 335570, 373922, 473831, 549993, 510542, 551259, 654421, 655879, 606356, 607258, 607720, 562859, 493935, 614491, 496107, 415115, 443235, 398432, 333208, 320727, 365631, 352438, 459358, 599862, 527111, 379584, 397170, 378133, 336414, 428546, 577938, 391528, 375296, 362091, 362849, 351985, 443394, 427310, 408511, 345479, 360744, 376341, 418631, 546694, 389802, 402174, 373348, 359247, 350680, 482835, 459177, 484793, 443799, 426291, 452531, 447057, 472657, 401029, 371137, 455698, 363834, 268819, 338907, 392992, 337182, 407908, 721160, 566889, 510259, 569413, 602361, 545719, 438827, 474978, 524401, 557291, 507015, 451885, 445663, 429922, 404226, 458050, 913819, 788977, 919372, 738813, 793247, 621411, 695759, 566320, 752189, 545619, 708747, 504176, 549467, 391330, 393120, 362931, 439549, 477922, 703807, 1196813, 712144, 640283, 509057, 488843, 426785, 649356, 731341, 891820, 1037533, 1252081, 896372, 968052, 792728, 637406, 709438, 711398, 544625, 617821]
[1, 4, 9, 16, 27, 41, 49, 63, 102, 114, 169, 187, 203, 221, 304, 328, 409, 441, 465, 495, 525, 559, 769, 811, 867, 907, 826, 854, 886, 938, 1403, 1451, 1505, 1555, 1786, 1838, 1741, 2125, 2193, 2605, 2325, 2005, 2479, 2318, 2362, 2637, 3402, 4012, 3857, 3666, 3722, 3822, 3890, 4803, 5676, 5270, 4571, 4344, 4711, 4775, 4291, 4714, 5528, 5596, 5335, 5730, 6977, 7095, 8324, 7684, 7788, 7565, 8834, 8593, 7965, 8448, 8592, 9546, 9245, 11081, 12568, 10972, 13359, 13437, 14493, 11983, 11684, 13255, 12445, 23146, 12212, 12488, 14141, 11315, 11483, 10597, 10723, 12502, 13137, 17338, 16438, 18403, 19152, 21051, 19440, 20213, 24089, 27881, 23958, 19859, 21866, 23296, 22210, 21100, 27782, 26918, 25716, 24608, 24165, 22400, 19856, 21538, 20326, 20536, 22156, 25266, 25556, 28786, 32741, 31533, 33269, 27511, 26299, 24250, 25143, 24622, 26364, 33092, 41478, 45302, 33265, 38585, 38683, 38867, 30719, 36107, 49476, 50561, 33497, 32824, 38584, 34357, 31830, 31103, 43554, 41934, 37705, 43685, 45915, 45214, 43578, 43878, 47389, 47613, 47895, 53102, 52555, 57868, 69627, 59771, 66233, 54139, 68044, 62006, 47832, 54544, 54678, 63658, 59578, 59902, 81523, 76368, 68865, 48302, 50760, 48808, 49210, 47216, 47478, 65605, 58845, 57015, 63262, 69713, 70055, 77587, 82895, 84916, 74247, 58708, 62677, 61600, 61900, 77484, 86917, 137914, 138138, 139857, 113430, 113622, 114138, 61141, 57346, 56231, 58034, 48951, 47902, 64001, 65632, 70069, 77422, 102173, 108519, 147988, 158395, 138619, 111790, 102187, 118656, 118980, 122102, 129889, 157411, 149579, 114193, 104086, 86350, 83678, 87012, 99772, 109678, 120987, 135798, 144063, 113391, 120077, 126949, 133557, 150019, 144087, 215601, 200135, 175161, 112624, 108081, 111709, 113496, 86305, 95014, 134231, 123064, 106686, 108559, 147289, 134061, 125762, 138459, 160049, 115473, 126511, 137625, 150316, 133290, 124957, 142174, 135510, 110792, 94891, 102715, 114171, 136767, 150196, 217982, 251249, 210973, 200191, 181679, 137015, 135334, 126657, 150237, 116373, 116781, 137099, 129555, 161765, 163946, 264404, 249366, 268259, 237169, 251620, 203912, 166261, 160906, 161398, 158094, 158328, 179496, 238172, 241405, 208991, 272609, 193717, 200350, 188046, 214132, 280761, 228242, 287411, 196060, 145318, 143445, 137214, 142142, 129740, 163503, 246742, 225136, 190362, 211037, 281860, 244077, 235551, 247636, 346849, 263218, 277332, 207581, 208121, 222435, 218261, 258604, 238087, 293968, 292373, 278593, 309810, 296260, 313511, 407826, 339913, 321429, 290740, 243684, 246561, 247179, 250790, 239317, 239917, 299757, 202649, 171324, 174595, 175171, 180555, 178456, 267899, 360527, 273370, 253902, 261939, 221761, 204130, 212315, 255367, 246139, 220479, 279205, 303598, 283150, 323895, 397068, 475601, 475975, 479358, 518200, 484551, 520498, 558894, 486715, 409358, 461547, 435829, 393093, 374420, 315442, 316562, 264941, 307022, 318898, 322155, 431690, 374925, 359779, 343307, 344033, 319310, 299963, 386261, 356964, 329114, 307056, 319326, 320002, 303342, 354145, 329152, 307116, 319346, 320018, 335503, 398130, 296879, 369131, 331206, 320008, 332524, 276405, 434853, 384152, 370375, 386446, 335601, 410021, 392319, 320195, 333669, 355802, 335617, 246686, 253384, 329580, 321247, 305944, 373375, 509235, 484549, 427865, 512155, 490816, 351068, 416412, 436470, 498665, 425214, 310046, 425879, 396868, 384324, 365118, 422033, 732376, 736161, 615128, 652675, 560903, 588181, 535963, 536341, 494774, 518831, 480331, 443670, 374179, 310360, 345674, 339194, 422514, 440359, 662611, 575989, 577321, 487999, 453647, 409098, 412909, 590009, 622872, 828622, 833547, 835897, 836379, 664214, 605163, 605537, 556917, 515757, 480551, 564256]
[1, 4, 9, 16, 27, 35, 49, 63, 102, 114, 138, 150, 162, 221, 257, 275, 352, 368, 398, 424, 452, 559, 686, 633, 772, 705, 723, 747, 777, 938, 1149, 1189, 1231, 1406, 1637, 1536, 1741, 1799, 2193, 1913, 1967, 1824, 2099, 2125, 2165, 2438, 2769, 3347, 3403, 3212, 3272, 3344, 3408, 4552, 4391, 3692, 4033, 4079, 4157, 3651, 3725, 3839, 4914, 4974, 5022, 4793, 5984, 6421, 7285, 6637, 6729, 6847, 7366, 7089, 7586, 7299, 7814, 8355, 8443, 9445, 10052, 9709, 12066, 11705, 10542, 10205, 10780, 10964, 11060, 10691, 9410, 11530, 10245, 9842, 9487, 9591, 10210, 11460, 11568, 14092, 14250, 16175, 17463, 18206, 17156, 17915, 22915, 20172, 18563, 18657, 19438, 19618, 19125, 19846, 20841, 23715, 21868, 20726, 18947, 19105, 17212, 18177, 17624, 18487, 20083, 21060, 22720, 26629, 26925, 28595, 24401, 22310, 21793, 22736, 21338, 23084, 24021, 31518, 31914, 31549, 30021, 36943, 35391, 28943, 28232, 33590, 44358, 31707, 30079, 28509, 31574, 29071, 29181, 28442, 38112, 31913, 34946, 38111, 40293, 37686, 38861, 35301, 42554, 41787, 44964, 42289, 49588, 49880, 53475, 55725, 51963, 52097, 57734, 42379, 43676, 51399, 50474, 55170, 52137, 50281, 67396, 65454, 44815, 45011, 43039, 42168, 42508, 42724, 42964, 55244, 47315, 53526, 55071, 61446, 66494, 68043, 63671, 66721, 53564, 55045, 57761, 55445, 59426, 68731, 79363, 127698, 118953, 93669, 105696, 95548, 55773, 54636, 52134, 48389, 46163, 43667, 41261, 58557, 62904, 65950, 69118, 85385, 97247, 136610, 129855, 101465, 90295, 96431, 107080, 113176, 109025, 110922, 111810, 108111, 94910, 83264, 77434, 77706, 79517, 86173, 100530, 101084, 123448, 103789, 104073, 104487, 120685, 120989, 127913, 136172, 174079, 145701, 107663, 99764, 98403, 106852, 77834, 79797, 90109, 109370, 99776, 101685, 91869, 123581, 118788, 112170, 121373, 111857, 105115, 114396, 132402, 118870, 110501, 102090, 120850, 103412, 91135, 87735, 97312, 110549, 127652, 144703, 168113, 176809, 179226, 172126, 127366, 127634, 107149, 120990, 106514, 104931, 105285, 123582, 121823, 153969, 152240, 209160, 211763, 202688, 223218, 193707, 153929, 138227, 142807, 133150, 149996, 148183, 171322, 186847, 183641, 198646, 185203, 183306, 177393, 173425, 205736, 215320, 190208, 187348, 132136, 134633, 130599, 124356, 116306, 125424, 154787, 207088, 167754, 179297, 195490, 232644, 214970, 208635, 225128, 249368, 249604, 179585, 184787, 196696, 199505, 199885, 226280, 184934, 251974, 264305, 264547, 267564, 268048, 271085, 286905, 289996, 276194, 216861, 224562, 220238, 199199, 214625, 215147, 222956, 187641, 158711, 149295, 157396, 165303, 165717, 173502, 240366, 226914, 220219, 243750, 200907, 196271, 191375, 181631, 203787, 209865, 210107, 258333, 259109, 254307, 284410, 354716, 443717, 420136, 399468, 403347, 428328, 482942, 456788, 368391, 387814, 353587, 354619, 355139, 279465, 261062, 253795, 254017, 274130, 294157, 311143, 301641, 283284, 329100, 304233, 296484, 285698, 277549, 273501, 303137, 275211, 275791, 287965, 277147, 257554, 285043, 259858, 286837, 287419, 288019, 320918, 245926, 285123, 307118, 289802, 299267, 267208, 261550, 365876, 309127, 331232, 310971, 311417, 361429, 279802, 274466, 318382, 276060, 234006, 234348, 247206, 276727, 293182, 287204, 307498, 442822, 408541, 393006, 429443, 328271, 335113, 387585, 420425, 392504, 277016, 297130, 383616, 357832, 348497, 342305, 379510, 686190, 528198, 555596, 487005, 531046, 468553, 509335, 393084, 471377, 384951, 426587, 322674, 300017, 280021, 325342, 329005, 395258, 426707, 415435, 482870, 452861, 436080, 380932, 391769, 385157, 516698, 591381, 691693, 626044, 782992, 603465, 529960, 573316, 492225, 429225, 458849, 448520, 499978]