「高橋の数」を求めるアルゴリズム（２） 　　　　　　　　　　　　　　　　　　　　　　　　　　　　2000.08.20 　 「高橋の数」の一般式を求めるアルゴリズムです。 　これを実装して、高橋謙一郎さんの分類（type A〜type D）との関係を明ら 　かにすることがねらいです。 （補足）構成要素として０を認めた場合、ｔｙｐｅＥが存在することが 　　　　高橋謙一郎さんによって発見された。(2000.08.05) 　　　　 　　　　しかし、以下のアルゴリズムには何ら変更はなく、スペクトルの 　　　　構成要素として０を追加するのみです。 　　　　 　このアルゴリズム本質は、「高橋の数」の性質２ ”「高橋の数」のスペク 　トルは、Ｔ変換に不変”にあります。これを平たく言えば、 　　変換前のＡ1Ａ2．．．Ａｎに１の数が３個ふくまれていたとすると、 　　　変換後のＢ1Ｂ2．．．Ｂｎにも１が３個ふくまれている。 　　　この数は多くてもすくなくてもいけない。 　この性質を利用して「高橋の数」となるための条件式を作成し、それを解く 　ことによって「高橋の数」の一般式を求めることができます。 １．概要 　まず、具体的なイメージを理解していただく為に、以下の例でアルゴリズム 　の全体を概観します。 　４，５，９の数字を使用した「高橋の数」は、type A 以外に存在するで 　しょうか？ 　ｅｘ． Ｎ＝444999444の場合 　max(N)：999 555 444 min(N)：444 555 999 T(n)=max(N)-min(N)：554 999 445 　　　　　　 ＾ ＾ ^：注目点 　９、５、４の個数をそれぞれａ，ｂ，ｃとすると max(N) = 9(a), 5(b), 4(c) min(N) = 4(c), 5(b), 4(c) 　　　　　 ただし、９（ａ）は９が ａ個ならんだものをあらわす 　となります。 　ａ，ｂ，ｃの大小関係（値そのものではなく）に着目すると、突き合わせ 　パターンとして以下の７種類が生成できます。(対応関係のみ表示） max(N) 9,5,4,4,4 9,5,5,4,4 9,5,4,4 9,9,5,5,4 min(N) 4,4,4,5,9 4,4,5,5,9 4,4,5,9 4,5,5,9,9 続き 9,9,9,5,4 9,9,5,4 9,5,4 4,5,9,9,9 4,5,9,9 4,5,9 　ａ+ｂ<ｃのときが最初のパターンで、ａ＝ｃのときが最後のパターンです。 【ａ＋ｂ＜ｃの場合】 　c ＝ a + b + c'（c' >= 1) として書き換えると max(N) 9(a) 5(b) 4(c') 4(b) 4(a) min(N) 4(a) 4(b) 4(c') 5(b) 9(a) 減算をするために、a = 1 + A, b = 1 + B (A,B>=0) として書き換えると max(N) 9(1+A) 5(B) 5 4(c') 4(1+B) 4(A) 4 min(N) 4(1+A) 4(B) 4 4(c') 5(1+B) 9(A) 9 　　----------------------------------------------　 T(N) 5(1+A) 1(B) 0 9(c') 8(1+B) 4(A) 5 変換後には、変換前に存在しない０，８などの数が出現しているので、 　このパターンは「高橋の数」とはなりえないことは明らかです。 【ａ＝ｃの場合】 　減算をするために、ａ＝１＋Ａ（Ａ＞＝０）として書き換えると max(N) 9(a) 5(b) 4(a) ＝＝＞ 9(A) 9 5(b) 4(A) 4 min(N) 4(a) 5(b) 9(a) 4(A) 4 5(b) 9(A) 9 　　　 ------------------------------------------------------　 T(N) 5(A) 4 9(b) 4(A) 5 「高橋の数」は、変換の前後で、９、５、４の個数は等しくなる筈。 ９の個数： Ａ＋１ ＝ ｂ ５の個数： ｂ ＝ Ａ＋１ ４の個数： Ａ＋１ ＝ Ａ＋１ これを整理すると、ｂ＝Ａ＋１すなわち、ｂ＝ａとなる。これを最初の 　仮定ａ＝ｃとあわせると、ａ＝ｂ＝ｃ（ａ＞＝１）が「高橋の数」となる 　条件式である。 つまり、type A : ４５９ｘｎ（ｎ＞＝１）を求めたことになる。 ほかの５パターンも同様に調べると、解が存在しないことがわかるので、 ４、５、９の３つの数字で構成される「高橋の数」は、４５９ｘｎのパ ターンのみという事が言える。 この方式をすべてのパターンについて調べると、ｔｙｐｅＡ〜Ｄを導くこと 　ができます。（しかも、それ以外のパターンは存在しないこともわかる） ２．アルゴリズム詳細 　スペクトルを構成するｃ個の数字をｆ1，ｆ2，．．．ｆcとする。 　Ｔ変換を行うためには、ｍａｘ（Ｎ）、ｍｉｎ（Ｎ）の各桁の対応関係を 　とる必要がある。これをつきあわせ処理と呼ぶことにし、その対応関係を 　ｐａｉｒ（ｘ，ｙ）でｆxとｆyの組を表すことにする。 □つき合わせ処理：Ｔ変換のための準備 　 　以下の再帰関数 pairing(m,i,j) を m=1,i=1,j=c で呼び出すことにより、 　ｃ個の数字で構成されるスペクトルのすべてのつき合わせパターンを生成 　することができる。 　 ｐａｉｒｉｎｇ（ｍ、ｉ、ｊ） : 　　ｍ：ｍ番目のペアを生成する 　　ｉ：ｍａｘ（Ｎ）側の処理の対象がｆiであることを表す 　　ｊ：ｍｉｎ（Ｎ）側の処理の対象がｆjであることを表す 　再帰的に以下の処理を行う。 　１）ｍ番目のペアとして、ｐａｉｒ（ｉ、ｊ）を生成する。 　２）ｉ＜ｊのとき 　　　ｆiの個数とｆjの個数との大小関係を考慮して、以下の３つの可能性 　　　を順次よびだす。ただし、＃（ｆk）はｆkの個数とする。 　　　　pairing(m+1,i,j+1) : #(fi) > #(fj)の場合を想定 　　　　pairing(m+1,i+1,j) : #(fi) < #(fj)の場合を想定 　　　　pairing(m+1,i+1,j+1) : #(fi) = #(fj)の場合を想定 　　　　リターン 　３)　ｉ＞＝ｊのとき 　 　　まず、Ｌ，Ｓ，Ｕを定義する。（この変数はあとで使用する） 　　　　　Ｌ ： ｍ−１ 　　　　　Ｓ ： ｉ＝ｊのとき ｍ　そうでないときは ｍ−１ 　　　　　Ｕ ： Ｌ＋Ｓ 　　　　　　　 　　　対象性に着目すると、後半は今まで生成したペアを逆順に生成すれば よい。 　（Ｓ＋ｋ）番目のペア　＝　（Ｌ−ｋ＋１）番目のペアに着目して、 　　　（Ｓ＋１）〜Ｕ番目のペアを作成する。 　　　 　　　これで、１つのつき合わせパターンが生成できたことになる。 　　　残りのパターンを生成するためにリターンする。 　(補足）ｃ＝３の場合は、概要のところで触れたように７パターンとなる。　　　　 □ｐａｉｒテーブルの作成：Ｔ変換 　 　Ｔ変換を行うため以下のテーブルを使用する。 　　pair[].lower : （lower,upper）でペアを格納する 　　pair[].upper : 　　pair[].var :　ペア（lower,upper）の個数。一般にこの数は１以上 　　　　　　　　　　の変数なので１＋α（α＞＝０）という表現となる 　　pair[].val :　１０進減算の結果の数字を格納する 　Ｔ変換前のスペクトルは、pair[].lowerとpair[].varで表現し、 　Ｔ変換後のスペクトルは、pair[].val　とpair[].varで表現される。 　１）つき合わせの結果のパターン（の１つ）をpair[].lower,pair[].upper 　　　に格納する。あわせて、Ｌ，Ｓ，Ｕも設定する。 　２）Ｌ行、Ｕ行をコピーして、Ｕ＋１行，Ｕ＋２行を作成する。 　３）ｐａｉｒ［ｍ］．ｖａｒに以下の値を設定する。 　　　ｍ＜Ｌ　　　　　：１＋Ｘｍ 　　　ｍ＝Ｌ　　　　　：１ 　　　ｍ＝Ｓ（Ｓ≠Ｌ）：１＋Ｘｍ 　　　Ｓ＜ｍ＜Ｕ　　　：１＋Ｘu-m+1 　　　ｍ＝Ｕ　　　　　：１ 　　　ｍ＝Ｕ＋１　　　：ＸL 　　　ｍ＝Ｕ＋２　　　：Ｘ1 　　　ただし、Ｘｍ（０＜ｍ＜＝S)は変数であり、Ｘｍ＞＝０とする。 　４）ｐａｉｒ［ｍ］．ｖａｌに以下の値を設定する。 　　　ｍ＜Ｌ　　　　　： pair[m].lower - pair[m].upper 　　　ｍ＝Ｌ　　　　　： pair[m].lower - pair[m].upper - １ 　　　ｍ＝Ｓ（Ｓ≠Ｌ）： ９ 　　　Ｓ＜ｍ＜Ｕ　　　： ９ ＋ pair[m].lower - pair[m].upper 　　　ｍ＝Ｕ　　　　　：１０＋ pair[m].lower - pair[m].upper 　　　ｍ＝Ｕ＋１　　　： pair[m].lower - pair[m].upper 　　　ｍ＝Ｕ＋２　　　： ９ ＋ pair[m].lower - pair[m].upper 　 以上の処理で、Ｔ変換後の結果が pair[].valとpair[].varに得られている。 　［例］概要の５番目のパターンの場合、ｐａｉｒテーブルは以下のようになる。　 　　　　　　９，９，９，５，４ 　　　　　　４，５，９，９，９ 　　　　 　　　　　　lower　　upper　　var　 　val 　　　@　　　９　　　４　　　1 + a ５ 　　　A　　　９　　　５ 1　　　　３　 　　　B　　　９　　　９ 1 + c　　９ 　　　C　　　５　　　９ 1 + b　　５ 　　　D　　　４　　　９ 1　　　　５ 　　　E　　　９　　　５ b　　　　４ 　　　F　　　４　　　９ a　　　　４　 　　　また、Ｌ＝２，Ｓ＝３，Ｕ＝５となる。 　　　　　　EはAのコピー、FはDのコピーである。 　　　見やすくする為、Ｘ1　＝　ａ，Ｘ２　＝　ｂ，Ｘ３　＝　ｃと表記した。 □Ｔ変換不変の連立方程式：「高橋の数」の条件式 　「高橋の数」となるための条件をｐａｉｒテーブルを使用することにより 　連立方程式として表現する。その解を求めることで、一般的な「高橋の数」 　の表現式を得る。 　１）「Ｔ変換の前後でスペクトルが不変」ということは、以下の連立方程式 　　　として表現できる。 　　　変換前のスペクトルを構成する数字ｆ1，ｆ2，．．．ｆc について 　 　 　　　　変換前の個数　−　変換後の個数　＝　０ 　　　が成立しなければならない。 　２）上記の連立方程式を解く（通常の掃出し法を使えばよい） 　３）「解の存在」の制約 　　　当然のことながら、「高橋の数」として実際に存在するためには、変数 　　　Ｘｍは、０以上の整数でなければならない。 　　　従って、２）で得られた解が、Ｘｍ＞＝０となる条件を満たしていない 　　　場合は不適合として破棄しなければならない。 　　　以下の簡単なテスト法に該当したものはとして破棄する。 　　　［ｒｕｌｅ１］ 　　　　　@変数の係数はすべて０、ｎｏｎｚｅｒｏの定数が残った場合 ex. ２　＝　０　(要するに通常の不能解のケース） 　　　　　A変数の係数はすべて同じ符号であり、定数も同じ符号の場合 　　　　　　ex.　X1　＋　X3　＋　１　＝　０ 　　　　　　　　-X1　−　X2　−　３　＝　０ 　　　［ｒｕｌｅ２］ 　　　　　連立式を変形することによってｒｕｌｅ１に還元できる場合 　　　　　例えば、ｉ行＋ｊ行をつくるとAになるようなとき 　 　　　上記のテストにパスしたものは「高橋の数」の候補として出力する。 　　　最終的には、人による「解の存在」の確認を行う。 　［例］上で作成したｐａｉｒテーブルについて連立方程式を作成する 　　　 　　　　９　：　(1+a) + 1 + (1+c) + b - { (1+c) } = 0 　　　　５　：　(1+b) - { (1+a) + (1+b) + 1 } = 0 　　　　４　：　1 + a - { b + a } = 0 　　 　式を整理すると　 　　 　　　　 ａ＋ｂ＋２＝０　　．．．式１ 　 　　−ａ −２＝０　　．．．式２ 　　　　 −ｂ＋１＝０　　．．．式３ 式１、式２はｒｕｌｅ１のAに該当するので、破棄しなければならない。 　　（この場合はｐａｉｒテーブルのAを見ると、変換に３が現れているので 　　　連立方程式を立てるまでもないパターンであるが）