フロベニウスの硬貨問題

互いに素な2つの整数 a(1),a(2) が与えられ、これらを組み合わせて表現できる数、また表現できない数やその場合の上限値はいくらであるかを問う問題。
即ち、非負整数 m(1),m(2) が存在して
m(1)a(1) + m(2)a(2) = n
が成り立つことは、硬貨の言葉に置き換えると a(1) 円玉と a(2) 円玉を用いて n 円が支払えることを意味する。
この時、どの額が支払えるか、支払えない最高額はいくらかを求める問題をいう。

例えば 5 円切手と 8 円切手を組み合わせて支払える金額を考察すると、
27 よりも小さい 14 の数に対しては実現可能（0,5,8,10,13,15,16,18,20,21,23,24,25,26）であるが、
一方 14 の数に対しては実現不可能（1,2,3,4,6,7,9,11,12,14,17,19,22,27）である。
また、27 よりも大きければ恒に実現可能である。
なぜならば 5 つの連続した数 28,29,30,31,32 が一旦生じてしまえば、5 の倍数を加えることで 32 より大きな数は全て表すことができるからである。

a(1) と a(2) を組み合わせて表現できない（支払えない）上限値（最高額）をフロベニウス数と呼び、g(a(1),a(2)) で表される。
フロベニウス数は
g(a(1),a(2)) = a(1)a(2) - a(1) - a(2) = (a(1)-1)(a(2)-1) - 1
で与えられ（シルヴェスター、1884年）、1 と (a(1)-1)(a(2)-1) の間にある整数のちょうど半数が表現可能である。

a(1) と a(2) が互いに素ならば、a(1)a(2) よりも小さい実現不可能な数の個数は
(a(1)-1)(a(2)-1)/2
で示される（シルヴェスターの定理）。

例えば、a(1) = 5 、a(2) = 8 の場合フロベニウス数は g(a(1),a(2)) = 27 で、表現不可能な整数の数は (a(1)-1)(a(2)-1)/2 = 14 となる。
また、a(1) = 4 、a(2) = 7 の場合フロベニウス数は g(a(1),a(2)) = 17 で、表現不可能な整数の数は (a(1)-1)(a(2)-1)/2 = 9 となる。

ttp://www.geocities.jp/ikuro_kotaro/koramu/1367_s2.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/2143_o2.htm
ttp://mathworld.wolfram.com/FrobeniusNumber.html
ttp://en.wikipedia.org/wiki/Coin_problem

参照（過去の日記）：
正方形・立方体分割
ttp://mixi.jp/view_diary.pl?id=696919535&owner_id=14882521
互いに素
ttp://mixi.jp/view_diary.pl?id=1637313521&owner_id=14882521