ホフスタッター配列

数学において、ホフスタッター数列は、非線形再帰関係によって定義される関連する整数数列の族のメンバーです。

最初のホフスタッターシーケンスは、ダグラス・リチャード・ホフスタッターの著書「ゲーデル、エッシャー、バッハ」で説明されました。図と背景に関する第 III 章 (図-図シーケンス) および第 V 章の再帰的構造とプロセス (残りのシーケンス) での説明の順序で、これらのシーケンスは次のとおりです。

ホフスタッター図形列（RとS）は、次のように定義される補完的な整数列のペアである。^{[1] [2]}

${\displaystyle {\begin{aligned}R(1)&=1,\ S(1)=2;\\R(n)&=R(n-1)+S(n-1),\quad n>1,\end{aligned}}}$

は、に存在しない正の整数の厳密に増加する系列として定義されます。これらの数列の最初の数項は、 ${\displaystyle S(n)}$${\displaystyle R(n)}$

R : 1、3、7、12、18、26、35、45、56、69、83、98、114、131、150、170、191、213、236、260、... ( OEISのシーケンスA005228 )

S : 2、4、5、6、8、9、10、11、13、14、15、16、17、19、20、21、22、23、24、25、... ( OEISのシーケンスA030124 )

ホフスタッターG配列は次のように定義される: ^{[3] [4]}

${\displaystyle {\begin{aligned}G(0)&=0,\\G(n)&=nG{\big (}G(n-1){\big )},\quad n>0.\end{aligned}}}$

この数列の最初の数項は

0、1、1、2、3、3、4、4、5、6、6、7、8、8、9、9、10、11、11、12、12、...（OEISのシーケンスA005206）

ホフスタッターH配列は次のように定義される: ^{[3] [5]}

${\displaystyle {\begin{aligned}H(0)&=0,\\H(n)&=nH{\Big (}H{\big (}H(n-1){\big )}{\Big )},\quad n>0.\end{aligned}}}$

この数列の最初の数項は

0、1、1、2、3、4、4、5、5、6、7、7、8、9、10、10、11、12、13、13、14、...（OEISのシーケンスA005374）

ホフスタッターの女性（F）配列と男性（M）配列は以下のように定義される：^{[3] [6]}

${\displaystyle {\begin{aligned}F(0)&=1,\ M(0)=0;\\F(n)&=nM{\big (}F(n-1){\big )},\quad n>0,\\M(n)&=nF{\big (}M(n-1){\big )},\quad n>0.\end{aligned}}}$

これらの数列の最初の数項は

F : 1、1、2、2、3、3、4、5、5、6、6、7、8、8、9、9、10、11、11、12、13、... ( OEISのシーケンスA005378 )

M : 0、0、1、2、2、3、4、4、5、6、6、7、7、8、9、9、10、11、11、12、12、... ( OEISのシーケンスA005379 )

ホフスタッターQ系列は次のように定義される: ^{[3] [7]}

${\displaystyle {\begin{aligned}Q(1)&=Q(2)=1,\\Q(n)&=Q{\big (}nQ(n-1){\big )}+Q{\big (}nQ(n-2){\big )},\quad n>2.\end{aligned}}}$

数列の最初の数項は

1、1、2、3、3、4、5、5、6、6、6、8、8、8、10、9、10、11、11、12、...（OEISのシーケンスA005185）

ホフスタッターは数列の項を「Q数」と名付けた。^[3]したがって、6のQ数は4である。ホフスタッターの本におけるQ数列の提示は、実際には文献におけるメタフィボナッチ数列の最初の言及である。^[8]

フィボナッチ数列の項は前の 2 つの項を合計することで決定されますが、Q 数の前の 2 つの項は、合計する 2 つの項を見つけるために Q 数列をどれだけ遡るかを決定します。したがって、合計項のインデックスは Q 数列自体に依存します。

数列の最初の要素であるQ (1)は、後の要素を生成するために加算される2つの項の1つには決してならず、 Q (3)の計算におけるインデックス内でのみ関与する。^[9]

Q 数列の項は無秩序に流れているように見えますが^{[3] [10] [11] [12]、}多くのメタフィボナッチ数列と同様に、その項は連続する世代のブロックにグループ化できます。^{[13] [14]} Q 数列の場合、k番目の世代には 2 ^{k の}メンバーがあります。^[15]さらに、g はQ 数が属する世代であり、Q 数を計算するために合計される 2 つの項 (親と呼ばれます) は、ほとんどが世代g − 1 に存在し、世代g − 2 にはごくわずかしか存在せず 、それより古い世代に存在することはありません。^[16]

これらの発見のほとんどは経験的な観察であり、Qシーケンスについてはこれまで事実上何も証明されていない。 ^{[17] [18] [19]シーケンスがすべての}nに対して明確に定義されているかどうか、つまり、シーケンスの生成規則が概念的に最初の項Q (1)の左側にある項を参照しようとするため、シーケンスがある時点で「死ぬ」かどうかは不明である。^{[12] [17] [19]}

ホフスタッターがQシーケンスを初めて説明してから20年後、彼とグレッグ・フーバーはQシーケンスのシーケンスファミリーへの一般化にQという文字を使用し、彼の本の元のQシーケンスをUシーケンスに改名しました。^[19]

元のQシーケンスは、 n  − 1とn  − 2をそれぞれn  −  rとn  −  sに置き換えることによって一般化されます。^[19]

これは、シーケンスファミリーにつながる

${\displaystyle Q_{r,s}(n)={\begin{cases}1,\quad 1\leq n\leq s,\\Q_{r,s}(n-Q_{r,s}(nr))+Q_{r,s}(n-Q_{r,s}(ns)),\quad n>s,\end{cases}}}$

ここでs  ≥ 2かつr  <  sです。

( r , s ) = (1,2)の場合、元のQシーケンスはこのファミリーのメンバーです。これまでのところ、ファミリーQ _{r , s}のシーケンスは 3 つしか知られていません。つまり、 ( r , s ) = (1,2)のUシーケンス(これは元のQシーケンスです)、^{[19] 、(} r , s ) = (1,4)の V シーケンス、^{[20] 、および (} r , s ) = (2,4)の W シーケンスです。 ^[19]他のシーケンスほどカオス的に動作しない V シーケンスのみが「死なない」ことが証明されています。[ ^19]元のQシーケンスと同様に、W シーケンスについてはこれまで実質的に何も厳密に証明されていません。^[19]

V系列の最初の数項は

1、1、1、1、2、3、4、5、5、6、6、7、8、8、9、9、10、11、11、11、...（OEISの配列A063882）

Wシーケンスの最初の数項は

1、1、1、1、2、4、6、7、7、5、3、8、9、11、12、9、9、13、11、9、...（OEISの配列A087777）

他の値（r、s）については、シーケンスは遅かれ早かれ「死ぬ」、すなわち、n  −  Q _r、s（n  −  r）<1であるためQ _r、s（n）が定義されないnが存在する。 ^[19]

1998年、ミュンスター大学（ドイツ）の科学者でホフスタッターと密接な関係にあったクラウス・ピンは、ホフスタッターのQシーケンスの別の一般化を提案し、ピンはそれをFシーケンスと呼んだ。^[21]

Pinn F _{i , j}シーケンスのファミリは次のように定義されます。

${\displaystyle F_{i,j}(n)={\begin{cases}1,\quad n=1,2,\\F_{i,j}(ni-F_{i,j}(n-1))+F_{i,j}(nj-F_{i,j}(n-2)),\quad n>2.\end{cases}}}$

そこでピンは、和の項のインデックスを概念的に左（つまり、数列の始めに近づく）にシフトする追加の定数iとjを導入した。 ^[21]

（i、j）＝（0、0）、（0、1）、（1、0）、および（1、1）であるFシーケンスのみが明確に定義されているようであり、最初のシーケンスは元のQシーケンスを表す。 ^[21] Q （1）とは異なり、Pinn F _i、j（n ）シーケンスの最初の要素は、追加の定数のいずれかが1である場合にシーケンスの後の要素を計算する際の合計の項です。

Pinn F _0,1シーケンス の最初の数項は

1、1、2、2、3、4、4、4、5、6、6、7、8、8、8、8、9、10、10、11、...（OEISの配列A046699）

ホフスタッター・コンウェイの1万ドル数列は次のように定義される^[22] $${\displaystyle {\begin{aligned}a(1)&=a(2)=1,\\a(n)&=a{\big (}a(n-1){\big )}+a{\big (}na(n-1){\big )},\quad n>2.\end{aligned}}}$$

この数列の最初の数項は

1、1、2、2、3、4、4、4、5、6、7、7、8、8、8、8、9、10、11、12、...（OEISのシーケンスA004001）

値は1/2に収束し、ジョン・ホートン・コンウェイがこの収束率を決定できる者に1万ドルの賞金を出すと発表したことから、この数列はこう名付けられた。その後1,000ドルに減額されたこの賞金は、コリン・マローズが獲得し、次のことを証明した。^{[23] [24]} ホフスタッターは後に、クラウス・ピンとの私信の中で、コンウェイが挑戦状をたたきつける10～15年前に、この数列とその構造を発見していたと主張した。^[10]${\displaystyle a(n)/n}$ $${\displaystyle \left|{\frac {a(n)}{n}}-{\frac {1}{2}}\right|=O\!\left({\frac {1}{\sqrt {\log n}}}\right).}$$

• Balamohan, B.; Kuznetsov, A.; Tanny, Stephan M. (2007-06-27)、「Hofstadter の Q シーケンスの変形の動作について」(PDF)、Journal of Integer Sequences、10 (7)、ウォータールー、オンタリオ (カナダ): ウォータールー大学: 71、Bibcode :2007JIntS..10...71B、ISSN  1530-7638。
• エマーソン、ナサニエル D. (2006-03-17)、「可変順序再帰によって定義されるメタフィボナッチ数列のファミリー」(PDF)、Journal of Integer Sequences、9 (1)、ウォータールー、オンタリオ州 (カナダ): ウォータールー大学、ISSN  1530-7638。
• ホフスタッター、ダグラス（1980年）『ゲーデル、エッシャー、バッハ：永遠の黄金の編み紐』ペンギンブックス、ISBN 0-14-005579-7。
• Pinn, Klaus (1999)、「ホフスタッターの Q(n) シーケンスにおける秩序とカオス」、Complexity、4 (3): 41–46、arXiv : chao-dyn/9803012v2、Bibcode :1999Cmplx...4c..41P、doi :10.1002/(SICI)1099-0526(199901/02)4:3<41::AID-CPLX8>3.0.CO;2-3。
• ピン、クラウス (2000)、「コンウェイの再帰的シーケンスのカオス的ないとこ」、実験数学、9 (1): 55–66、arXiv : cond-mat/9808031、Bibcode :1998cond.mat..8031P、doi :10.1080/10586458.2000.10504635、S2CID  13519614。