151219(3)

Ruby

Frobeniusの硬貨交換問題(3)

もう少し調べてみた。

require 'prime'

def f(ary)
  s_ary = Array.new(ary.max, 0)
  s_ary[-1] = 1
  a = 0
  b = s_ary.inject(:*)
  while b == 0
    f_max = a if s_ary[-1] == 0
    a += 1
    s_ary << ary.inject(0){|s, i| s += s_ary[-i]}
    s_ary.shift
    b = s_ary.inject(:*)
  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 = 10 ** 2
p_ary = Prime.each(10 ** 3).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]
[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]
[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]
[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]
[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]
[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]
[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]