2005年4月20日（水）

「ホフスタッター数列群」仮稿

（数学に興味のない方は、この記事は読み飛ばして、下記の4月19日付の「LAN奮闘記、もしくは日本橋紀行」からお読みください）
　アクセス解析を調べてみると、「ホフスタッター数列」というキーワードでご訪問の閲覧者様がけっこう多くいらっしゃるようです。「ホフスタッター」とか、＋αのキーワードで検索すると当サイトが意外にも上位に表示されるというのはありがたいことではあります。しかし、内容の乏しいページで閲覧者様を失望させつづけているこの状況は、けして私の望むところではありません。
　「ホフスタッター数列群」に関する研究内容は『REMWIN研究所』内の『数学のはしっこ』に早々に掲載するべきなのですが、現在『REMWIN研究所』では『点字研究室』の「点形別国際点字辞典」を充実させることに力を傾けているようです。このままでは研究成果を皆様にお見せする見込みが立ちませんので、当日記コーナーにてその一端だけでも暫定的に公開してみることにいたします。
　始めに断っておきますが、「ホフスタッター数列群」は公然の数学用語ではなく、当コンソーシアム独自の用語です。また、「数列の群」ではなく、単に「一群の数列」程度の意味で使用しています。この記事ではその他にも、勝手に命名したり、気軽に用語を作ったりしていますので、もしかして引用などなさるようなことがある場合にはあらかじめご注意ください。
　「ホフスタッター数列群（Hofstadter sequences）」とは「ホフスタッター型高階再帰数列（Hofstadter-type high-order recursive sequences）」の略称で、ホフスタッター（Douglas R. Hofstadter）が著書『ゲーデル,エッシャー,バッハ―あるいは不思議の環』で発表した数列、およびそれに触発されて後の数学者が研究した類似の数列の総称です。ただ、これでは数学的定義としてはあまりにも粗雑に過ぎますので、もう少し正確には、「ホフスタッターG数列（Hofstadter G-sequence）」「ホフスタッターQ数列（Hofstadter Q-sequence）」「ホフスタッター・コンウェイの10,000ドル数列（Hofstadter-Conway 10,000-dollar sequence）」、および、これらの数列に類似の方法で生成され、類似の性質を示す数列の総称と定義しておきたいと思います。これとて厳密な定義とは言いがたいのですが、そもそもこれらは「娯楽数学」的な感興に基づく非実用的な概念ですので、それほど厳密に定義しておく必要はないのではないかと考えています。
（なお、この記事では、数列の日本語名からは『The On-Line Encyclopedia of Integer Sequences』、数列の英語名とその他の数学用語からは『MathWorld』の各項目にリンクしています）
　さらに正確には、「引数と1とを有限回加算・減算し、その数を引数とする項を算出し、その項と引数と1と、さらにはそれ以前に算出されたすべての項とを有限回加算・減算することを有限回繰り返して得られたひとつの数式を再帰式とし、有限の個数の値を初期値として得られる無限数列で、すべての自然数の引数で自然数の値をとり、基本的に増加傾向を示し、グラフで表現したときに一次直線など、単純な多項式で表される曲線によっておおむね近似されるもの」と定義することも可能ではあります（ここで、「項を算出」とは単に「a[n]」というような形式で書き出すことであり、数値として求めるということではありません）。しかし、「基本的に増加傾向」とか「曲線によっておおむね近似」とかいうのは「性質」であり、「定義」の一部とするべき必要条件であるかということには疑念がないわけではありません。また、正確に定義しすぎると、「ホフスタッター数列群」に加えておきたい面白い性質を持つ数列が排除されてしまう可能性もないとは限りません。
　たとえば、ホフスタッターG数列もホフスタッターQ数列もホフスタッター・コンウェイの10,000ドル数列も直線によって近似されますので、当初この定義は「直線によっておおむね近似」としていました。しかし、1を1個、2を2個、3を3個…というようにnをn個ずつ順に配列した数列もホフスタッター的に生成することができますが、この数列をグラフにすると、直線ではなく当然放物線になります。このように、新たな数列の発見によって正確な定義は更新される可能性がありますので、上の定義は一応提示しておくのみとします。
　それでは、個々の数列について概観していきましょう。
　ホフスタッターG数列は G[1]=1, G[n]=n-G[G[n-1]]（n≧2）で定義される数列で、1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, ... と続きます。類似の数列の一例としてはホフスタッターH数列（Hofstadter H-sequence）があり、H[1]=1, H[n]=n-H[H[H[n-1]]]（n≧2）で定義され、1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, ... と続きます。さらにこの再帰の入れ子を深くしていくことも可能です。これらの数列は共通して、すべての自然数が順に1〜2回ずつ出現し、固定の引数について再帰が深くなるごとに項の値がおおむね大きくなるという性質を持っています。
　ホフスタッターQ数列は Q[1]=Q[2]=1, Q[n]=Q[n-Q[n-1]]+Q[n-Q[n-2]]（n≧3）で定義される数列で、1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, ... と続きます。この数列は基本的には Q[n]≒n/2 のあたりを推移しますが、上下に激しく振動したり、時折収束したりと、カオスを垣間見るかのような感慨を惹き起こす複雑な振る舞いを見せます。
　類似の再帰式によって生成される数列はいろいろと研究され、その多くがQ数列と同様に複雑な振る舞いを見せます。ただし、アレンビー（R. Allenby）によって研究された数列「アレンビー数列（Allenby sequence）」は、A[1]=A[2]=1, A[n]=A[n-A[n-1]]+A[n-1-A[n-2]]（n≧3）で定義されますが、始めの1が2回出現するのを除いて、すべての自然数がその順に、n=(2^t)r（rは奇数）とすると t+1 回連続して出現するなど、後述のホフスタッター・コンウェイの10,000ドル数列のような整然とした振る舞いが見られます。やはり、A[n-1] を n から引くのならば、A[n-2] は n-1 から引くのが順当というものなのでしょう。
　ホフスタッター・コンウェイの10,000ドル数列は a[1]=a[2]=1, a[n]=a[a[n-1]]+a[n-a[n-1]]（n≧3）で定義される数列で、1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, ... と続きます。この数列は
(1) すべての項はその前項に等しい、もしくは1大きい（すべての自然数がその順に出現する）
(2) a[2^t] は 2^(t-1) に等しく、それ以外の n でも、a[n] は n/2 から n の範囲内にある
(3) a[2n] は 2a[n] より小さいか等しい
(4) n→∞のとき、a[n]/n は 1/2 に収束する
(5) A[n]=2a[n]-n とすると、0≦r≦2^t について、A[2^t+r] と A[2^(t+1)-r] は等しい
などという性質を持っていますが、わけても素晴らしいのが、A[n] のグラフを描くと、ブラマンジェ関数（もしくは高木フラクタル関数）に類似した曲線が、次第に大きくなりながら連続して出現するということでしょう。
　当コンソーシアムで特に重点的に研究しているのが、この10,000ドル数列と、その類似の数列です。プレオープンサイトでも10,000ドル数列について取り上げ、上記の性質(1)を証明したりもしました。ここでは、10,000ドル数列を一般化した数列を考察していきたいと思います。
　まずは初期値を一般化してみます。10,000ドル数列では初期値として1を2個配列していましたが、ここは何個でも可能です。そこで、a[1]=a[2]=a[3]=1, a[n]=a[a[n-1]]+a[n-a[n-1]]（n≧4）とすると、この数列は 1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6, 7, 7, 8, ... となります。当コンソーシアムではこの数列を、10,000ドル数列に関する賞金10,000ドルの懸賞問題を出して当時の数学界を騒然とさせたベテラン数学者コンウェイ（J. Conway）の名に因み、「コンウェイ数列（Conway sequence）」と呼ぶことにしましょう。
　次に、再帰式の中の引数を一般化してみます。10,000ドル数列では n-1 を引数としていましたが、n から1より大きい数を引くことも可能です。ただし、大きすぎる数を引いて引数が0以下になってしまうと計算ができなくなりますので、その分初期値の個数を増やす必要があります。a[1]=a[2]=a[3]=1, a[n]=a[a[n-2]]+a[n-a[n-2]]（n≧4）とすると、この数列は 1, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 7, 7, 8, ... となります。当コンソーシアムではこの数列を、10,000ドルの賞金を掴みそこねた（？）数学者マローズ（C. L. Mallows）の名に因み、「マローズ数列（Mallows sequence）」と呼ぶことにしましょう。
　最後に、G数列とH数列のように、再帰式の再帰の深さを一般化してみます。再帰式の第1項 a[a[n-1]] と、第2項 a[n-a[n-1]] の中の a[n-1] には、それぞれ同数ずつ a[…] を被せることが可能です。そこで、a[1]=a[2]=1, a[n]=a[a[a[n-1]]]+a[n-a[a[n-1]]]（n≧3）とすると、この数列は 1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9, 10, 11, 12, ... となります。当コンソーシアムではこの数列を、昨年2004年にこの数列を含む同様の数列を研究する論文を発表したポーランドの新進の数学者グリッチュク（J. Grytczuk）の名に因み、「グリッチュク数列（Grytczuk sequence）」と呼ぶことにしましょう。
　これら3種類の一般化は、単独のみならず、同時に適用することも可能です。そこで、自然数の値をとる4変数 c, m, g, n について、
・H{c,m,g}[n]=1（1≦n≦c+m）
・H{c,m,g}[n]=H{c,m,g}[H^(g){c,m,g}[n-m]]+H{c,m,g}[n-H^(g){c,m,g}[n-m]]（n≧c+m+1）
（ただし、H^(0){c,m,g}[n]=n, H^(t){c,m,g}[n]=H{c,m,g}[H^(t-1){c,m,g}[n]] とする）
という再帰式によって生成される数列群を考えることにします。c=m=g=1 とすると、この数列 H{1,1,1}[n] は10,000ドル数列になります。また、コンウェイ数列は c=2, m=g=1、マローズ数列は m=2, c=g=1、グリッチュク数列は g=2, c=m=1 の場合の例です。変数 c・m・g をそれぞれ「コンウェイ成分（Conway factor）」「マローズ成分（Mallows factor）」「グリッチュク成分（Grytczuk factor）」と呼ぶことにします。
　当コンソーシアムではこの数列群を「ホフスタッターのドローブリッジ数列（Hofstadter's drawbridge sequences）」と呼んでいます。「ドローブリッジ」とは「跳ね橋」という意味です。数列の先頭から第1項が指し示す項を結ぶ直線と、数列の末尾から第2項が指し示す項を結ぶ直線とが、n が増加するたびに接触したり分離したりする様子からこのように名付けてみました（ただし、10,000ドル数列以外では、ほとんどの場合くっ付きっぱなしだったり離れっぱなしだったりしますが）。
　この命名法に従うと、さしづめ上記「性質(5)」の A[n] は「ホフスタッターのブラマンジェ数列」と名付けることも可能でしょう。ただし、A[n] の再帰式を導出することは可能（A[n]=A[((n-1)+A[n-1])/2]+A[((n+1)-A[n-1])/2]）ですが、A[n] は0になることがありますので、「ホフスタッター数列群」には含まれません（再帰式も条件を満たしていません）。「ホフスタッターのブラマンジェ数列」については、後に正確に定義します。
　ホフスタッターのドローブリッジ数列は、すべての c, m, g について10,000ドル数列の性質(1)を満たします。このことは、10,000ドル数列と同様の方法で簡単に証明することができます。また、これによってドローブリッジ数列は「ホフスタッター数列群」に含まれるための必要条件の一部を満たすことになります。
　ドローブリッジ数列 H{c,m,g}[n] は一般に、固定の n について、c や m が増加するとおおむね小さくなり、g が増加するとおおむね大きくなる傾向があります。上記の性質(2)・(3)・(4)のような性質は、c, m, g の値によって様々です。性質(5)のような対称性は、c=m=g=1 以外の場合には成り立ちません。
　ここで、上の性質を厳密に考察するために、別の数列群をひとつ定義しておきます。F[1]=F[2]=1, F[n]=F[n-1]+F[n-2]（n≧3）で定義される数列は有名なフィボナッチ数列（Fibonacci sequence。正確にはフィボナッチ数からなる数列）ですが、この再帰式の第2項を一般化し、L[t,n]=1（1≦n≦t）, L[t,n]=L[t,n-1]+L[t,n-t]（n≧t+1）で定義される数列を「一般化フィボナッチ数列」と言います。t=1 のときは L[1,n]=2^(n-1) 、t=2 のときはフィボナッチ数列、t=3 のときは 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, ... と続きます。
　ドローブリッジ数列は m=1 のとき、一般化フィボナッチ数列 L[cg,n] のすべての項について H{c,1,g}[L[cg,n]]=L[cg,n-c] という性質が成り立ちます。ここから、項を引数で割った値の極限 lim[n→∞] H{c,m,g}[n]/n を H[c,m,g] とすると、H[c,1,g] は方程式 x=(1-x^g)^c の解（0＜x＜1）となると予想されます（大学時代、数学の授業を少々なめてかかっていたせいか、私はどうも数列の収束の評価がちょっと苦手です）。10,000ドル数列 H{1,1,1}[n] についての極限 H[1,1,1] は、x=1-x の解 1/2 になります。
　一方、m≧2 の場合は、上のようなわかりやすい性質は成り立ちません。これは、m=1 のときは H{c,1,g}[n] の状況が H{c,1,g}[n+1] にダイレクトに反映されるのに対して、m≧2 の場合は反映されるのが遅れるため、数列全体に統制が取れないことが要因であると考えられます。m≧2 の場合でも極限 H[c,m,g] は存在すると思われますが、H{c,m+1,g}[n] は H{c,m,g}[n] よりおおむね小さいのに、H[c,m+1,g] は H[c,m,g] より小さくなるとは限りません。マローズ数列 H{1,2,1}[n] は、n=(2^t)r とすると、1.25＜r＜1.75 のあたりでおおむね H{1,2,1}[n]/n＞1/2 、1.75＜r＜2.5 のあたりでおおむね H{1,2,1}[n]/n＜1/2 になりますので、H[1,2,1] は H[1,1,1] と同じく 1/2 になると予想されます。
　「ホフスタッターのブラマンジェ数列（Hofstadter's blancmanger sequences）」は、この極限値 H[c,m,g] を利用して、B{c,m,g}[n]=H{c,m,g}[n]-nH[c,m,g] と定義します。上記の A[n] は 2B{1,1,1}[n] ということになります。ブラマンジェ数列は一般に自然数どころか整数にもなりませんので、「ホフスタッター数列群」には含まれませんが、グラフを描くと0のあたりを推移することになりますので、「ホフスタッター数列群」の性質の考察が容易になるのではと予想されます。B{1,1,1}[n] のグラフはブラマンジェ関数に類似した曲線を描きますが、一般の c, m, g の場合もそれぞれに独特の美麗な曲線が描かれることと思います。
　「ホフスタッター数列群」研究の究極の目標は、特定の引数 n について項を直接求める方法を発見することです。n=1 の場合から順に計算していくよりも速く求められるアルゴリズムを発見できれば、研究は成功と言えます。
　G数列 G[n] は、p=(-1+√5)/2（黄金比の逆数）とすると、G[n]=floor[p(n+1)]（floor[x] は x を超えない最大の整数）と表すことができます。ただし、G[n] を求めるために無理数である√5の小数部分を十分正確に求めるアルゴリズムが、G[n] を n=1 から順に求めていくよりも本当に速いものなのかどうかということについては、検討の余地があります。また、H数列などもおおむね floor[q(n+1)] という形式で表すことができますが、n の値によって若干の調整が必要になります。
　一方、Q数列については、状況は絶望的です。小さい n について観察し、一般にも成り立つと予想された性質（たとえば、0≦t≦8 について Q[3*2^t]=2^(t+1)）も、n が大きくなるとほとんど成り立たなくなります。Q数列の性質を解明できれば数学のノーベル賞と言われるフィールズ賞を獲れるとも囁かれるほど、世界中の数学者を悩ませつづけた難解な問題なのです。
　10,000ドル数列については、a[2^t]=2^(t-1) という性質があり、数列中に特定の値が何回出現するのかを求める方法も知られていますので、アレンビー数列ほど単純明快ではありませんが、a[2^t] を足掛かりにすればかなり速く求められることになります。一般のドローブリッジ数列については、m=1 の場合は10,000ドル数列と同様の方法をとることもできますが、m≧2 の場合はいまだ研究途上です。
　「ホフスタッター数列群」は「娯楽数学」の範疇ですので、実用性などというものは本来考慮されていないのですが、あえて考えるとすれば、これらの数列はフラクタルの整数による近似と考えることもできますので、描画ソフトなどへの応用が考えられます。フラクタルとは、従来の幾何学が単純な図形ばかりを研究してきたということへの反省として考察されている、至る所で滑らかではない、部分を取り出しても全体よりも単純にならない図形の性質のことです。一部の描画ソフトでは、フラクタルを応用して自然な質感を備えたグラフィックを描き出しています。しかし、フラクタルは厳密に求めようとすると、小数部分を何度も計算しなければならず、コンピューターに多大な負担がかかります。もし描きたいフラクタルに似た振る舞いをする整数の再帰数列を見つけることができれば、計算量が格段に少なくなり、描画も素早くなることが予想されるのです。ただし、現在ではそのような研究をする端緒にも就いていないというのが現状です。
　「ホフスタッター数列群」について長々と述べてきましたが、皆様に誇れるほど研究が進んでいるというわけではありません。皆様も興味を持たれましたならば、ご自身で研究され、私などよりも早く世に出されてみてはいかがでしょうか。「ホフスタッター数列群」を考察する有効な手段として、引数の値と項の値を結ぶ樹形図を描くなどという方法があります（ホフスタッターはこの樹形図を、G数列の考察に使用したことから「G図」と呼んでいます）。また、ブラウザ上で簡単にインタラクティブなプログラムを作れるJavaScriptなどで、数列を計算するプログラムを組んでみるというのもいいでしょう。
　今後このような学術関連の記事は学術サイト『REMWIN研究所』の本文として掲載することになると思いますが、準備が整わなければ、また当日記コーナーで掲載することになるかもしれません。日記形式では十分な論述ができず、皆様に不満を残すことになるかもしれませんが、当コンソーシアムの成長を温かく見守っていただければ幸いです。