ホフスタッター系列

ホフスタッター図形-図形（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項は、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 )

• Balamohan, B.; Kuznetsov, A.; Tanny, Stephan M. (2007-06-27)、「ホフスタッターのQ数列の変種の挙動について」（PDF）、Journal of Integer Sequences、10（7）、ウォータールー、オンタリオ州（カナダ）：ウォータールー大学：71、Bibcode：2007JIntS..10...71B、ISSN 1530-7638 。
• エマーソン、ナサニエル D. (2006年3月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。
• Pinn, Klaus (2000)、「コンウェイの再帰的数列の混沌とし​​た従兄弟」、Experimental Mathematics、9 (1): 55–66、arXiv : cond-mat/9808031、Bibcode : 1998cond.mat..8031P、doi : 10.1080/10586458.2000.10504635、S2CID 13519614 。