・条件の微妙な違い                       GAI 氏

 p、qを2以上の互いに素な自然数とする。(p<qとする。)このとき、どんな自然数nでも整
数a、bを用いて、n=ap+bq の式で表せる。

 ところで、a、bの条件を非負の整数に制限すると、ある値のn以上のすべてのものしか、
n=ap+bq では表せなくなる。このときのnの最小値は何か?

 また、同様に、2以上の互いに素なp、q、rの自然数に対して、(p<q<rとする。)ある値
以上のすべての自然数nが、n=ap+bq+cr (a、b、cは非負の整数) とできることにな
るnの最小値は何か?

#上記の前半は式で構成できると思うんですが、後半のものについては式が構成できるの
だろうか?


(コメント) 「3a+5b(ただし、a、bは非負整数)の形で表せない正の整数の最大値を求め
      よ。」という問題が、当HPの「線形結合の問題」でも話題になりましたね!


 なおさんからのコメントです。(平成27年11月18日付け)

 この問題は、Frobeniusの硬貨交換問題として有名な問題ですね。ここに書かれているn−1
の値はFrobenius数と呼ばれています。3個以上の場合は専門家の間でも、現時点でも完全
には未解決だと思われます。
(3個の場合は特に詳しく研究されており、Morales-Denhamの定理と呼ばれる定理で、
Frobenius数の計算がかなり早くできる事が知られています。)

 この周辺の話題は1冊の本になってしまうくらいまとめられています。詳しくは、

 ベック・ロビンス著、岡本吉央訳 「離散堆積計算による組み合わせ数学入門」(丸善出版)

を見ると良いかもしれません(入門とありますが、内容としてはかなり難易度は高かったです)


 GAI さんからのコメントです。(平成27年11月18日付け)

 ヒントを参考にネットで探し回ったら、下記の式が存在することを見つけました。

P[a_,b_,c_,n_]:=n^2/(2a b c)+n/2(1/(a b)+1/(a c)+1/(b c))+1/12(3/a+3/b+3/c+a/(b c)+b/(a c)+c/(a b))
        +1/a*Sum[1/((1-E^(k b(2Pi I/a)))(1-E^(k c(2Pi I/a)))(E^(k n(2 Pi I/a)))),{k,1,a-1}]
        +1/b*Sum[1/((1-E^(k c(2Pi I/b)))(1-E^(k a(2Pi I/b)))(E^(k n(2 Pi I/b)))),{k,1,b-1}]
        +1/c*Sum[1/((1-E^(k a(2Pi I/c)))(1-E^(k b(2Pi I/c)))(E^(k n(2 Pi I/c)))),{k,1,c-1}]
(ただし、Eは自然対数の底;Iは虚数単位)

 互いに素な2以上の自然数a、b、cに対し、ap+bq+cr=n を満たす非負整数(p,q,r)
が何組存在するかを計算できる。(→ 計算結果


 at さんからのコメントです。(平成27年11月19日付け)

 ap+bq+cr=n を満たす非負整数(p,q,r)の組の個数を F(a,b,c,n) とします。

F(a,b,c,n) を a、b、c、n を用いて表す方法には様々なものがあると思われます。例えば、

次のように表すことができます。

F(a,b,c,n)=floor(((n+1+a)(n+1+b)(n+1+c))2n+2a+2b+2c/((((n+1+a)(n+1+b)(n+1+c))2a-1
     (((n+1+a)(n+1+b)(n+1+c))2b-1(((n+1+a)(n+1+b)(n+1+c))2c-1)-((n+1+a)(n+1+b)(n+1+c))2*
     floor(((n+1+a)(n+1+b)(n+1+c))2n+2a+2b+2c-2/((((n+1+a)(n+1+b)(n+1+c))2a-1
     (((n+1+a)(n+1+b)(n+1+c))2b-1(((n+1+a)(n+1+b)(n+1+c))2c-1)))

 F(a,b,c,n)=[xn](1/((1-xa)(1-xb)(1-xc)))=[x0](1/((xn)(1-xa)(1-xb)(1-xc)))

 つまり、F(a,b,c,n)はローラン級数 1/((xn)(1-xa)(1-xb)(1-xc)) の定数項ですから、この定数
項だけをうまく取り出せばF(a,b,c,n)が求まります。


 Seiichi Manyamaさんからのコメントです。(平成27年12月17日付け)

 面白そうなので確かめようとしたのですが、「フロベニウス数:8」の部分は、5, 6, 7を使って
も表せない最大の数は8ということでしょうか?それならば、9も表せないと思うのですが、私が
何か勘違いしているのでしょうか?


 GAI さんからのコメントです。(平成27年12月18日付け)

 私のタイプミスでした!n=9の時点で計算量が1.11022*10^-16となってしまうので、このフロ
ベニウス数は9です。小さな字が見えに難くなっており、失礼いたしました。



                         投稿一覧に戻る