コラコスキ配列

数学において、コラコスキー列（コラコスキーれん）は、オルデンブルガー・コラコスキー列とも呼ばれ、^{[1] は、}連続長符号化における連続長の列である記号の無限列{1,2}である。^{[2]これは、1965 年にこれを説明した}趣味数学者ウィリアム・コラコスキー(1944–97)にちなんで名付けられたが、^[3] 1939 年にルーファス・オルデンブルガーによって以前に議論されていた。^{[1] [4]}

コラコスキー数列の最初の項は次のとおりです。

1,2,2,1,1,2,1,2,2,1,2,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,... ( OEISのシーケンスA000002 )

各記号は、1 つまたは 2 つの連続する項の「連続」(等しい要素のシーケンス) 内に出現し、これらの連続の長さを書き出すと、まったく同じシーケンスが得られます。

1、2、2、1、1、2、1、2、2、1、2、2、1、1、2、1、1、2、2、1、2、1、1、2、1 、​​​​​​​​​​​​​​​ 2,2、1,1、2、1,1、2,1、2,2、1、2,2、1,1、2,1 、​​​​​​​​​​ 2、2、...

1、2、2、1、1、2、1、2、2、1、2、2、1、1、2、1、1、2、2、1、2、1、1、2、1、 2、2、1、1、2、...

したがって、コラコスキシーケンスの説明は可逆です。Kが「コラコスキシーケンス」を表す場合、説明 #1 は論理的に説明 #2 を意味します (逆も同様です)。

1. Kの項はKの連続（つまり、連続長さ）によって生成される。

2. KのランはKの項によって生成される。

したがって、コラコスキー シーケンスの各項は、1 つまたは 2 つの将来の項の連続を生成すると言えます。シーケンスの最初の 1 は、「1」の連続、つまりそれ自体を生成します。最初の 2 は、「22」の連続を生成し、これにはそれ自体が含まれます。2 番目の 2 は、「11」の連続を生成します。以下同様です。シーケンス内の各数字は、次に生成される連続の長さであり、生成される 要素は1 と 2 の間で交互になります。

1,2 (シーケンスの長さl = 2; 項の合計s = 3)

1,2,2 ( l = 3, s = 5)

1,2,2,1,1 ( l = 5, s = 7)

1,2,2,1,1,2,1 ( l = 7, s = 10)

1,2,2,1,1,2,1,2,2,1 ( l = 10, s = 15)

1,2,2,1,1,2,1,2,1,2,2,1,2,1,2 ( l = 15, s = 23)

ご覧のとおり、各ステージでのシーケンスの長さは、前のステージの項の合計に等しくなります。このアニメーションは、このプロセスを示しています。

これらの自己生成特性は、数列を最初の 1 なしで書いた場合でも維持され、コラコスキー数列がフラクタル、つまり他のスケールで自身の表現をエンコードする数学的オブジェクトとして記述できることを意味します。^[1]ベルトラン・スタインスキーは、数列のi番目の項の再帰式を作成しましたが^{[5]、数列は非}周期的であると推測されています。^[6]つまり、その項には一般的な繰り返しパターンがありません ( πや√ 2などの無理数を参照)。

コラコスキ{1,2}列の1s密度は1/2である可能性が高いと思われますが、この予想は未証明のままです。^[6] Václav Chvátalは1sの上限密度が0.50084未満であることを証明しました。^[7] Nilssonははるかに高い計算能力で同じ方法を使用し、上限0.500080を得ました。^[8]

数列の最初の3×108^{の値の計算では密度が1/2とわずかに異なる値に収束しているように見えたが、 [5]}数列を最初の1013^の値まで拡張したその後の計算では、限界密度が実際に1/2である場合に予想されるように、1/2の密度からの偏差が小さくなっていることが示された。^[9]

コラコスキーシーケンスは、単純な巡回タグシステムの結果としても説明できます。ただし、このシステムは1タグシステムではなく2タグシステムであるため（つまり、一度に1つのシンボルを操作するのではなく、シンボルのペアを他のシンボルシーケンスに置き換えます）、タグシステムがチューリング完全であるパラメータの領域にあり、この表現を使用してシーケンスについて推論することは困難です。^[10]

コラコスキー シーケンスは、 i番目の反復で、シーケンスのi番目の値としてすでに出力されている値x _iを読み取る (または、そのような値がまだ出力されていない場合は、 x _i  =  iに設定する) アルゴリズムによって生成できます。次に、iが奇数の場合は、数 1 のx _i個のコピーを出力し、 iが偶数の場合は、数 2 のx _{i 個}のコピーを出力します。したがって、アルゴリズムの最初の数ステップは次のようになります。

1. 最初の値はまだ出力されていないので、x ₁  = 1に設定し、数値1のコピーを1つ出力します。
2. 2番目の値はまだ出力されていないので、x ₂  = 2に設定し、数値2を2回出力します。
3. 3 番目の値x ₃は 2 番目のステップで 2 として出力されたため、数値 1 を 2 つ出力します。
4. 4 番目の値x _{4 は}3 番目のステップで 1 として出力されたため、数値 2 のコピーを 1 つ出力します。

このアルゴリズムは線形時間がかかりますが、シーケンスの前の位置を参照する必要があるため、シーケンス全体を保存する必要があり、線形スペースを消費します。シーケンスの複数のコピーを異なる速度で生成し、シーケンスの各コピーが前のコピーの出力を使用して各ステップで何を行うかを決定する代替アルゴリズムを使用すると、線形時間と対数スペースのみでシーケンスを生成できます。^[9]

• ゴロムシーケンス— ランレングスに基づくもう一つの自己生成シーケンス
• ギスウィイトのシーケンス
• 見て言うシーケンス

• アルーシュ、ジャン=ポール、シャリット、ジェフリー(2003)。自動シーケンス: 理論、アプリケーション、一般化。ケンブリッジ大学出版局。p. 337。ISBN 978-0-521-82332-6.ZBL1086.11015  。​
• Dekking, FM (1997)。「コラコスキ系列の長距離秩序とは何か?」Moody, RV (編)。NATO高度研究機関議事録、ウォータールー、オンタリオ州、1995 年 8 月 21 日～9 月 1 日。ドルドレヒト、オランダ: Kluwer。pp. 115～125。
• Fedou, JM; Fici, G. (2010). 「微分可能シーケンスと再帰性に関するいくつかのコメント」(PDF) . Journal of Integer Sequences . 13 (3). 記事 10.3.2.
• Keane, MS (1991)。「エルゴード理論と有限型のサブシフト」。Bedford, T.、Keane, M. (編)。エルゴード理論、記号力学、双曲空間。オックスフォード、イギリス: オックスフォード大学出版局。pp. 35–70。
• ラガリアス、JC (1992)。「数論と動的システム」。バー、SA (編)。数論の不合理な有効性。プロビデンス、ロードアイランド州：アメリカ数学会。pp. 35–72。ISBN 9780821855010。
• パウン、ゲオルゲ。サロマー、アルト(1996)。 「セルフリーディングシーケンス」。アメリカ数学月刊誌。103 (2): 166–168。土井：10.2307/2975113。JSTOR  2975113。Zbl 0854.68082  。
• Shallit, Jeffrey (1999)。「数論と形式言語」。Hejhal , Dennis A.、Friedman, Joel、Gutzwiller, Martin C.、Odlyzko, Andrew M. (編)。数論の新たな応用。1996 年 7 月 15 日から 26 日まで米国ミネソタ州ミネアポリスで開催された IMA サマー プログラムの議事録に基づく。数学とその応用に関する IMA 巻。第 109 巻。Springer -Verlag。pp . 547–570。ISBN 0-387-98824-6.ZBL0919.00047  。​

• Weisstein, Eric W.「コラコスキー数列」。MathWorld。
• 1998年4月にオリヴィエ・ジェラールが計算した25000桁までのコラコスキ定数
• Bellos, Alex (2017年7月24日). 「The Kolakoski Sequence」（ビデオ） . Brady Haran . 2021年12月21日時点のオリジナルよりアーカイブ。 2017年7月24日閲覧。