151219(2)

Ruby

Frobeniusの硬貨交換問題(2)

連続する素数でFrobenius数を求めてみた。
オンライン整数列大辞典の
A037165（http://oeis.org/A037165/list）、
A138989（http://oeis.org/A138989/list）、

A138990（http://oeis.org/A138990/list）、

A138991（http://oeis.org/A138991/list）、

A138992（http://oeis.org/A138992/list）、

A138993（http://oeis.org/A138993/list）、

A138994（http://oeis.org/A138994/list）
と比較し、答え合わせしてみる。

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

p_ary = Prime.each(10 ** 3).to_a
ary = A037165(p_ary, 41)
# OEIS A037165のデータ
ary0 =
[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]
# 一致の確認
p ary == ary0

ary = A138989(p_ary, 46)
# OEIS A138989のデータ
ary0 =
[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]
# 一致の確認
p ary == ary0

ary = A138990(p_ary, 48)
# OEIS A138990のデータ
ary0 =
[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]
# 一致の確認
p ary == ary0

ary = A138991(p_ary, 48)
# OEIS A138991のデータ
ary0 =
[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]
# 一致の確認
p ary == ary0

ary = A138992(p_ary, 49)
# OEIS A138992のデータ
ary0 =
[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]
# 一致の確認
p ary == ary0

ary = A138993(p_ary, 50)
# OEIS A138993のデータ
ary0 =
[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]
# 一致の確認
p ary == ary0

ary = A138994(p_ary, 50)
# OEIS A138994のデータ
ary0 =
[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]
# 一致の確認
p ary == ary0

出力結果
true
true
true
true
true
true
true