問題提起 1から9999までの数字と、それに対応する合計停止時間 1から10 までの数字の合計停止時間のヒストグラム。x軸は合計停止時間、 y軸は頻度です 。1から109 までの数字の合計停止時間のヒストグラム。x軸は合計停止時間、 y軸は頻度です 。入力が2から10の場合の反復時間7 。 250、1000、4000、20000、100000、500000までの数字の合計停止時間 任意の正の整数 に対する以下の演算を考えてみましょう。
偶数の場合は、2で割ります。 数字が奇数の場合は、3倍して1を足します。 モジュラー算術 表記において、関数 f を次のように定義する。 f （ n ） = { n / 2 もし n ≡ 0 （ モジュール 2 ） 、 3 n + 1 もし n ≡ 1 （ モジュール 2 ） 。 {\displaystyle f(n)={\begin{cases}n/2&{\text{if }}n\equiv 0{\pmod {2}},\\3n+1&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}}
次に、任意の正の整数から始めて、この操作を繰り返し実行し、各ステップの結果を次のステップの入力として使用して、数列を作成します。
表記法： 1 私 = { n のために 私 = 0 、 f （ 1 私 − 1 ） のために 私 > 0 {\displaystyle a_{i}={\begin{cases}n&{\text{for }}i=0,\\f(a_{i-1})&{\text{for }}i>0\end{cases}}} a iは 、 nに f を i 回再帰的に適用した値です。a i = f i ( n ) ）。
コラッツ予想とは、最初にどの正の整数を選んでも、この過程は最終的に1に到達するというものである。つまり、どの正の整数を最初に選んでも、 n {\displaystyle n} 私 {\displaystyle i} 1 私 = 1 {\displaystyle a_{i}=1}
この予想が誤りであるとすれば、それは1を含まない数列を生み出すような開始数が存在するからに他ならない。そのような数列は、1を含まない循環小数に入るか、あるいは際限なく増加するかのどちらかである。しかし、そのような数列は発見されていない。
a i < a 0 iを n の停止時間 と呼びます。同様に、 a k = 1 となる最小のk を n の全停止時間 と呼びます。[ 2 ] i またはk のいずれかが存在しない場合、それぞれ停止時間または全停止時間は無限大であると言います。
コラッツ予想は、すべてのn について、全停止時間は有限であると主張する。これは、すべてのn ≥ 2
n が奇数の場合、 3n + 1は 偶数となるため、代わりにコラッツ関数の「ショートカット」形式を使用することができます。 f （ n ） = { n 2 もし n ≡ 0 （ モジュール 2 ） 、 3 n + 1 2 もし n ≡ 1 （ モジュール 2 ） 。 {\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0{\pmod {2}},\\{\frac {3n+1}{2}}&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}}
実証データ 例えば、n = 12f を適用すると、 12、6、3、10、5、16、8、4、2、1 という 数列が得られます。
n = 19 の19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 。
n = 27
27、82、41、124、62、31、94、47、142、71、214、107、322、161、484、242、121、364、182、91、274、137、412、206、103、310、155、466、233、700、350、175、526、263、790、395、1186、593、1780、890、445、1336、668、334、167、502 251、754、377、1132、566、283、850、425、1276、638、319、958、479、1438、719、2158、1079、3238、1619、4858、2429、7288、3644、1822、911、2734、1367、4102、2051、6154、3077、9232、4616、2308、1154、577、1732、866、433、1300、650 325、976、488、244、122、61、184、92、46、23、70、35、106、53、160、80、40、20、10、5、16、8、4、2、1 （ OEIS における配列番号 A008884 ）
合計停止時間がどのより小さい開始値よりも長い数値は、次の数列を形成します。
1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, ... ( OEIS の シーケンス A006877 ) 。 最大 軌跡点がそれより小さいどの初期値よりも大きい初期値は以下のとおりです。
1、2、3、7、15、27、255、447、639、703、1819、4255、4591、9663、20895、26623、31911、60975、77671、113383、138367、159487、270271、665215、704511、... （ OEIS の シーケンス A006884 ） n が1に到達するまでのステップ数は
0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24, ... ( OEIS の シーケンス A006577 ) 最も長い総停止時間を持つ開始値
10未満は9で、19ステップあります。 100未満は97で、118ステップあります。 1000未満は871で、178ステップあります。 10⁴ 未満は6171で、261ステップあります。10未満5 は031 10 6 未満は799、524 10 7 未満は400 511、685 10 8 未満は728 127、949 10 9 未満は617 279、986 10未満10 は780 657 630 [ 10 ] 10未満11 は128 138 247 10未満12 は345 275 647 [ 11 ] ( OEIS の 配列 A284668 ) これらの数値は、指定された歩数で最小値ですが、必ずしも指定された制限を下回る唯一の数値ではありません。例として、780 657 631 780 657 630
桁数（2進数）に対する停止時間の合計が最も短い開始値は2のべき乗 です。なぜなら、2ⁿは n 回半分にされて1になり、決して増加しないからです。
視覚化 最初の1000個の数の軌道を示す有向グラフ。
x軸は開始番号を表し、y 軸は1までの連鎖中に到達した最高番号を表します。この グラフはy 軸が制限されていることを示しています。xの 値によっては、中間値として最大で × 10⁷x = 9663の
前のグラフと同じ内容ですが、対数スケールで表示しているため、すべてのy 値が表示されます。グラフの中央付近にある最初の太線は、27の先端に対応しており、9232で最大値に達します。
20ステップ未満のすべての数値を表す木。
最初の1億個の数値について、1に到達するまでに必要な反復回数。
コラッツ予想による、100万未満のランダムな開始点5000個に対する経路。
支持論拠 この予想はまだ証明されていないものの、この問題に取り組んだほとんどの数学者は、実験的証拠と経験的な議論がそれを裏付けていることから、この予想は正しいと考えている。
実験的証拠 この予想は、2 71 ≈までのすべての初期値についてコンピュータによって検証されました。× 10 21 [ 12 ]
このコンピュータによる証拠は、この予想がすべての初期値に対して真であるという厳密な証明にはならず、反例が見つかる可能性がある。これは、反証された ポリア予想 やメルテンス予想 の場合と同様である。
しかし、このような検証には他の意味合いもある。非自明なサイクルの長さの下限 など、特定の制約はサイクルの最小項の値に基づいて証明できる。したがって、最小項が小さいサイクルを除外するためのコンピュータ検索は、これらの制約を強化することができる。[ 13 ] [ 14 ] [ 15 ]
確率的ヒューリスティック コラッツ過程によって生成される数列の奇数 のみを考慮すると、各奇数は平均して前の奇数の 3/4 に [ 16 ] （より 。 ） このことから、すべての ヘイルストーン数列 は長期的には減少するはずだという経験的な議論が得られますが、これは他のサイクルに対する証拠ではなく、発散に対する証拠にすぎませ ん 2 進拡張では、 ほぼすべての 2 進の初期値に対して、乗算ステップごとに 2 つの除算ステップがあることを厳密に確立しています。）
下限値 コンピュータ支援による証明 において、KrasikovとLagariasは、区間[1, x ] 内の整数のうち最終的に1に到達するものの数は、十分大きなすべてのx に対して少なくともx 0.84 [ 19 ]
サイクル この部分では、コラッツ関数の簡略形について考察する。 f （ n ） = { n 2 もし n ≡ 0 （ モジュール 2 ） 、 3 n + 1 2 もし n ≡ 1 （ モジュール 2 ） 。 {\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0{\pmod {2}},\\{\frac {3n+1}{2}}&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}}} とは、f(a0) = a1、f(a1 ) = a2 、 ... 、 f aq ) = a0 と なる よう な 、 異なる 正 の 整数 の 列 , a1 , ... , aq ) のこと で ある
唯一知られているサイクルは、周期2の（1,2） であり、自明サイクルと呼ばれている。
サイクル長 2025年現在、サイクル長の最もよく知られている上限は976 794 617 504 839 929 [ 12 ] pが次の形式であることを証明した。 p = 301994 1 + 17087915 b + 85137581 c {\displaystyle p=301994a+17087915b+85137581c} a 、b 、c は非負の整数であり、b ≥ 1ac = 0である。この結果は、 ln 3 / ln 2 の な連分数 展開に基づいている。[ 14 ]
k サイクルkサイクルとは、 k個 は 増加する奇数列とそれに続く減少する偶数列から構成される。[ 15 ] 1サイクル と呼ばれる。
シュタイナー（1977）は、自明な（1; 2） 以外の 1 サイクルは存在しないことを証明した。[ 20 ] [ 21 ] k = 68 までのk サイクルは存在しないことを証明した。[ 15 ] ヘルヒャーはこの方法をさらに拡張し、 k ≤ 91の k サイクルは存在しないことを証明した。[ 22 ] k の
逆 コラッツグラフ の最初の21レベルは、ボトムアップ方式で生成されました。このグラフには、軌道長が21以下のすべての数値が含まれています。この予想を証明する別のアプローチとして、いわゆるコラッツグラフ （逆関係 式で定義されるグラフ）をボトムアップ方式で成長させる方法がある。 R （ n ） = { { 2 n } もし n ≡ 0 、 1 、 2 、 3 、 5 { 2 n 、 n − 1 3 } もし n ≡ 4 （ モジュール 6 ） 。 {\displaystyle R(n)={\begin{cases}\{2n\}&{\text{if }}n\equiv 0,1,2,3,5\\\left\{2n,{\frac {n-1}{3}}\right\}&{\text{if }}n\equiv 4\end{cases}}{\pmod {6}}.}
そこで、すべての正の整数が最終的に 1 に帰着することを証明する代わりに、1 がすべての正の整数に逆向きに帰着することを証明してみましょう。任意の整数n に対して、n ≡ 1 (mod 2) は3 n + 1 ≡ 4 (mod 6) の場合に限り成り立ちます 。同様に、n − 1 / 3 ≡ 1 (mod 2) は n ≡ 4 (mod 6) の場合に限り成り立ちます。推測では、この逆関係は、 1–2–4 ループ (この記事の「問題の説明」セクションで定義された変更されていない関数 f の 4–2–1 ループの逆) を除いて、正の整数に対してツリー を 形成します 。
関数f の関係3 n + 1 を一般的な代替「ショートカット」関係 3 n + 1 / 2 R （ n ） = { { 2 n } もし n ≡ 0 、 1 { 2 n 、 2 n − 1 3 } もし n ≡ 2 （ モジュール 3 ） 。 {\displaystyle R(n)={\begin{cases}\{2n\}&{\text{if }}n\equiv 0,1\\\left\{2n,{\frac {2n-1}{3}}\right\}&{\text{if }}n\equiv 2\end{cases}}{\pmod {3}}.}
任意の整数n に対して、n ≡ 1 (mod 2) と3 n + 1 / 2 ≡ 2 (mod 3) の場合のみです。同様に、2 n − 1 / 3 ≡ 1 (mod 2) となるのは、n ≡ 2 (mod 3) の場合のみです。 推測 で は、この逆関係は、1–2 ループ (上記のように修正された関数 f(n) の 1–2 ループの逆) を除いて、正の整数に対してツリーを形成します。
あるいは、3 n + 1を n ′ / H ( n ′ ) 。 n ′ = 3 n + 1 であり、H ( n ′ )は n ′ 余りなし) 2 の 最大のべき乗です。結果として得られる関数f は 奇数 から奇数にマッピングします。ここで、ある奇数n に対して、この操作をk 回適用すると数 1 が得られる (つまり、f k ( n ) = 1 ) とします。すると、バイナリ では、数nは 文字列 w k w k −1 ... w 1 w hは 1 / 3 h [ 23 ] n の表現は 1 / 3 h 繰り返し を保持し、各繰り返しはオプションで回転され、有限ビット数まで複製されます。これはバイナリでのみ発生します。[ 24 ] s は、 この形式の表現で到達できます ( s の先頭の '0' を追加または削除できます)。
2進数で計算する抽象機械 コラッツ関数の繰り返し適用は、ビット列を処理する抽象機械として表現できます。この 機械 は、任意の奇数に対して、1が 1 つだけ残るまで、次の3つのステップを実行します。
2進数で表した数値の（右）末尾に1を 付加する（ 2 n + 1 となる）。 これを元の数に二進数加算で加えます（2n + 1 + n = 3n + 1 ） 。 末尾のゼロ をすべて削除します（つまり、結果が奇数になるまで繰り返し2で割ります）。
例 開始数7は2進数で 111 と表されます。結果として得られるコラッツ数列は次のとおりです。
111 111 1 1011 0 1011 1 10001 0 10001 1 1101 00 1101 1 101 000 101 1 1 0000
パリティシーケンスとして このセクションでは、コラッツ関数の簡略形について考察します。 f （ n ） = { n 2 もし n ≡ 0 3 n + 1 2 もし n ≡ 1 （ モジュール 2 ） 。 {\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0\\{\frac {3n+1}{2}}&{\text{if }}n\equiv 1\end{cases}}{\pmod {2}}.}
P(...) が数のパリティ、つまりP(2 n ) = 0 およびP(2 n + 1) = 1 で ある場合、数nのコラッツパリティ列 (またはパリティベクトル) を p i = P( a i )a 0 = n a i +1f ( a i
3n + 1/2 n / 2 の どちらの 、パリティによって 決まります。パリティ の順序 は
f ( n )m とn のパリティ シーケンスが最初のk項で一致するのは、 m とnが 2 k を法として等しい場合に限ることが示されます。これは、すべての数がパリティ シーケンスによって一意に識別されることを意味し、さらに、複数の Hailstone サイクルが存在する場合は、対応するパリティ サイクルは異なっていなければならないことを意味します。[ 2 ] [ 17 ]
n = 2 k a + b f 関数をk 回適用すると、結果は3 c a + d d は b にf 関数をk 回適用した結果であり、c はそのシーケンス中に発生した増加の回数です。たとえば、2 5 a + 1 の場合、1 が 2、1、2、1 に繰り返し、最後に 2 に戻るため、増加は 3 回あり、結果は3 3 a + 2になります。2 2 a + 1 の 場合、1 が 2 に上昇し、1 に戻るため、増加は 1 回のみであり、結果は3 a + 1 になります。b が 2 k − 1 の場合、 増加 は k 回あり 、結果は3 k a + 3 k − 1になります。a に 3 を掛けた値はa の値とは無関係で、 b の挙動のみに依存します。これにより、特定の形式の数値は、一定回数の反復後に必ずより小さな数値になることを予測できます。たとえば、4 a + 1 は f を 2 回適用すると3 a + 1 になり、16 a + 3は f を 4 回適用すると9 a + 2 になります。ただし、これらのより小さな数値が 1 にまで続くかどうかは、 a の値に依存します。
タグシステムとして ショートカット形式のコラッツ関数
f （ n ） = { n 2 もし n ≡ 0 3 n + 1 2 もし n ≡ 1. （ モジュール 2 ） {\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0\\{\frac {3n+1}{2}}&{\text{if }}n\equiv 1.\end{cases}}{\pmod {2}}}
雹のシーケンスは、生成規則を持つ2タグシステムによって計算できます。
a → bc b → a c → aaa このシステムでは、正の整数nは n個の a のコピーからなる文字列で表され、タグ操作の反復処理は長さが 2 未満の単語で停止します。 （De Mol より改変）
コラッツ予想は、任意の有限文字列を最初の単語とするこのタグシステムが最終的に停止するという主張と同等である（ 具体的な例については「タグシステム」を参照）。
より大きなドメインへの拡張
すべての整数を反復処理する コラッツ予想の拡張として、正の整数だけでなく、すべての整数を含めることが挙げられます。外部から進入できないサイクル 0 → 0 を除くと、fの反復によってすべての非ゼロ整数が最終的に収束すると思われる既知のサイクルは全部で 4 つあります。これらのサイクルは、正の n に対するよく知られたサイクルから始めて、以下に列挙します。
奇数値は太字で表記されています。各サイクルは、絶対値が最小の要素（常に奇数）が最初に記載されています。
一般化されたコラッツ予想とは、 f による反復処理において、すべての整数は最終的に上記の 4 つのサイクルのいずれか、またはサイクル 0 → 0 に収束するという主張である。
奇数分母を持つ有理数を繰り返し処理する コラッツ写像は、既約分数で表したときに分母が奇数となる（正または負の）有理数に拡張できます。数は、分子が奇数か偶数かに応じて「奇数」または「偶数」とみなされます。すると、写像の式は定義域が整数の場合とまったく同じになります。つまり、偶数の有理数は2で割られ、奇数の有理数は3を掛けてから1が加えられます。これと密接に関連する事実として、コラッツ写像は2進整数 環にも拡張され、その環には分母が奇数の有理数の環が部分環として含まれています。
コラッツ写像の「ショートカット」定義を用いると、任意の周期パリティ列は ちょうど１つの有理数によって生成されることが知られている。[ 25 ] [ 2 ]
パリティサイクルの長さがn であり、インデックスk 0 < ⋯ < k m −1 m 回含まれる場合、このパリティサイクルを即座に周期的に生成する唯一の有理数は次のとおりである。
例えば、パリティサイクル（1 0 1 1 0 0 1） は長さが7で、インデックス0、2、3、6に4つの奇数項があります。これは分数によって繰り返し生成されます。 3 3 2 0 + 3 2 2 2 + 3 1 2 3 + 3 0 2 6 2 7 − 3 4 = 151 47 {\displaystyle {\frac {3^{3}2^{0}+3^{2}2^{2}+3^{1}2^{3}+3^{0}2^{6}}{2^{7}-3^{4}}}={\frac {151}{47}}} 151 47 → 250 47 → 125 47 → 211 47 → 340 47 → 170 47 → 85 47 → 151 47 。 \displaystyle {\frac {151}{47}}\rightarrow {\frac {250}{47}}\rightarrow {\frac {125}{47}}\rightarrow {\frac {211}{47}}\rightarrow {\frac {340}{47}}\rightarrow {\frac {170}{47}}\rightarrow {\frac {85}{47}}\rightarrow {\frac {151}{47}}.}
(1 0 1 1 0 0 1) の任意の巡回置換は、上記のいずれかの分数に対応します。例えば、巡回(0 1 1 0 0 1 1) は、分数によって生成されます。 3 3 2 1 + 3 2 2 2 + 3 1 2 5 + 3 0 2 6 2 7 − 3 4 = 250 47 。 {\displaystyle {\frac {3^{3}2^{1}+3^{2}2^{2}+3^{1}2^{5}+3^{0}2^{6}}{2^{7}-3^{4}}}={\frac {250}{47}}.}
一対一対応の場合、パリティサイクルは既約でなければ なりません。つまり、同一のサブサイクルに分割できない必要があります。この例として、パリティサイクル（1 1 0 0 1 1 0 0） とそのサブサイクル（1 1 0 0） は、既約分数にすると同じ分数 5 / 7
この文脈では、コラッツ予想の妥当性を仮定すると、（1 0） と（0 1） は正の整数（それぞれ1と2）によって生成される唯一のパリティサイクルであることを意味します。
有理数の奇数分母d が 3 の倍数でない場合、すべての反復計算で同じ分母が得られ、分子の列はコラッツ関数の 「 3 n + d 」一般化[ 26 ]を適用することで得られます。 T d （ x ） = { x 2 もし x ≡ 0 （ モジュール 2 ） 、 3 x + d 2 もし x ≡ 1 （ モジュール 2 ） 。 {\displaystyle T_{d}(x)={\begin{cases}{\frac {x}{2}}&{\text{if }}x\equiv 0{\pmod {2}},\\{\frac {3x+d}{2}}&{\text{if }}x\equiv 1{\pmod {2}}.\end{cases}}}
2進拡張 機能 T （ x ） = { x 2 もし x ≡ 0 （ モジュール 2 ） 3 x + 1 2 もし x ≡ 1 （ モジュール 2 ） {\displaystyle T(x)={\begin{cases}{\frac {x}{2}}&{\text{if }}x\equiv 0{\pmod {2}}\\{\frac {3x+1}{2}}&{\text{if }}x\equiv 1{\pmod {2}}\end{cases}}} Z 2 {\displaystyle \mathbb {Z} _{2}} 2進整数の関数 であり、 2進測度に関して連続かつ測度保存性を持つ。さらに、そのダイナミクスは エルゴード的で あることが知られている。[ 2 ]
パリティベクトル 関数Q が作用すると定義するZ 2 {\displaystyle \mathbb {Z} _{2}} Q （ x ） = ∑ k = 0 ∞ （ T k （ x ） モジュール 2 ） 2 k 。 {\displaystyle Q(x)=\sum _{k=0}^{\infty }\left(T^{k}(x){\bmod {2}}\right)2^{k}.}
関数Q は 2 進等長写像 である。[ 27 ] ほとんどすべての 軌跡は非巡回的である。Z 2 {\displaystyle \mathbb {Z} _{2}}
コラッツ予想の同等の定式化は次のとおりである。 Q （ Z + ） ⊂ 1 3 Z 。 {\displaystyle Q\left(\mathbb {Z} ^{+}\right)\subset {\tfrac {1}{3}}\mathbb {Z} .}
実数または複素数を反復処理する クモの巣図。 コラッツ写像は、以下の式を満たす任意の関数を選択することで実数直線に拡張できます。 x / 2 {\displaystyle x/2} x {\displaystyle x} 3 x + 1 {\displaystyle 3x+1} （ 3 x + 1 ） / 2 {\displaystyle (3x+1)/2} x {\displaystyle x} 補間 関数と呼ばれます。これを行う簡単な方法は、2つの関数を選択することです。g 1 {\displaystyle g_{1}} g 2 {\displaystyle g_{2}}
g 1 （ n ） = { 1 、 n そうです、 0 、 n 奇妙だ、 {\displaystyle g_{1}(n)={\begin{cases}1,&n{\text{は偶数です,}}\\0,&n{\text{は奇数です,}}\end{cases}}} g 2 （ n ） = { 0 、 n そうです、 1 、 n 奇妙だ、 {\displaystyle g_{2}(n)={\begin{cases}0,&n{\text{は偶数です,}}\\1,&n{\text{は奇数です,}}\end{cases}}} そして、それらを目的の値への切り替えスイッチとして使用します。
f （ x ） = x 2 ⋅ g 1 （ x ） + 3 x + 1 2 ⋅ g 2 （ x ） {\displaystyle f(x)={\frac {x}{2}}\cdot g_{1}(x)\,+\,{\frac {3x+1}{2}}\cdot g_{2}(x)} そのような選択肢の一つはg 1 （ x ） = コス 2 （ π 2 x ） {\displaystyle g_{1}(x)=\cos ^{2}\left({\tfrac {\pi }{2}}x\right)} g 2 （ x ） = 罪 2 （ π 2 x ） {\displaystyle g_{2}(x)=\sin ^{2}\left({\tfrac {\pi }{2}}x\right)} [ 28 ] 彼 は、 固定点が 無限に存在すること、および軌道が 単調に無限に 脱出することから、この予想は正の実数に対しては成り立たないことを示した。f {\displaystyle f} 魅力的なサイクルがあります 2 {\displaystyle 2} （ 1 ; 2 ） {\displaystyle (1;\,2)} （ 1.1925... ; 2.1386... ） {\displaystyle (1.1925...;\,2.1386...)} 測度であると推測されている。 0 {\displaystyle 0}
レザマン、シュライヒャー、ウッドは研究を複素平面 に拡張した。[ 29 ] 彼らは複素正弦と余弦に チャンバーランドの関数を用い、追加項を加えた。1 π （ 1 2 − コス （ π z ） ） 罪 （ π z ） + {\displaystyle {\tfrac {1}{\pi }}\left({\tfrac {1}{2}}-\cos(\pi z)\right)\sin(\pi z)\,+} h （ z ） 罪 2 （ π z ） {\displaystyle h(z)\sin ^{2}(\pi z)} h （ z ） {\displaystyle h(z)} は任意の整関数 です。この式は実数整数に対してゼロに評価されるため、拡張関数
f （ z ） = z 2 コス 2 （ π 2 z ） + 3 z + 1 2 罪 2 （ π 2 z ） + 1 π （ 1 2 − コス （ π z ） ） 罪 （ π z ） + h （ z ） 罪 2 （ π z ） {\displaystyle {\begin{aligned}f(z)=\;&{\frac {z}{2}}\cos ^{2}\left({\frac {\pi }{2}}z\right)+{\frac {3z+1}{2}}\sin ^{2}\left({\frac {\pi }{2}}z\right)\,+\\&{\frac {1}{\pi }}\left({\frac {1}{2}}-\cos(\pi z)\right)\sin(\pi z)+h(z)\sin ^{2}(\pi z)\end{aligned}}} これは複素平面へのコラッツ写像の補間です。追加項を加える理由は、すべての整数を臨界点 にするためです。f {\displaystyle f} ベイカー領域 には含まれないことが示され、これはどの整数も最終的に周期的であるか、または放浪領域 に属するかのどちらかであることを意味する。彼らは後者は当てはまらないと推測し、そうであればすべての整数軌道は有限になるだろうとした。
原点を中心とするコラッツフラクタルで、実部は-5から5までの範囲を持つ。 ほとんどの点の軌道は無限遠に発散します。これらの点を発散の速さに基づいて色分けすると、左の画像が得られます。h （ z ） = 0 {\displaystyle h(z)=0} ファトゥ成分 であり、それらの境界はジュリア集合 である。f {\displaystyle f} フラクタル パターンを形成し、時には「コラッツフラクタル」と呼ばれる。
指数補間のジュリア集合。 複素補間関数を定義する方法は他にもたくさんあり、例えば、正弦関数や余弦関数の代わりに複素指数関数を用いる方法などがあります。
f （ z ） = z 2 + 1 4 （ 2 z + 1 ） （ 1 − e 私 π z ） {\displaystyle f(z)={\frac {z}{2}}+{\frac {1}{4}}(2z+1)\left(1-e^{i\pi z}\right)} 異なるダイナミクスを示す。この場合、例えば、私は （ z ） ≫ 1 {\displaystyle \operatorname {Im} (z)\gg 1} f （ z ） ≈ z + 1 4 {\displaystyle f(z)\approx z+{\tfrac {1}{4}}} ヘア または光線 と呼ばれる無数の曲線から構成されています。
最適化
上記の「パリティシーケンスとして」の kステップ先に進むには (そのセクションの f 関数を使用)、現在の数値をb (最下位k ビット、整数として解釈) とa (残りのビット、整数として解釈) の 2 つの部分に分割します。k ステップ 先に進む結果は次のようになります。
f k k a + b ) = 3 c ( b , k ) a + d ( b , k )c (または3c )とd の値は、考え られるすべてのk ビット数b に対して事前に計算できます。ここで、d ( b , k )はb にf 関数をk 回適用した結果であり、c ( b , k ) は途中で遭遇する奇数の数です。[ 30 ] k =5 の場合、数の最下位5ビットを分離して、各反復で5ステップ先に進むことができます。
c (0...31, 5) = { 0, 3, 2, 2, 2, 2, 2, 4, 1, 4, 1, 3, 2, 2, 3, 4, 1, 2, 3, 3, 1, 1, 3, 3, 2, 3, 2, 4, 3, 3, 4, 5 },d (0...31, 5) = { 0, 2, 1, 1, 2, 2, 2, 20, 1, 26, 1, 10, 4, 4, 13, 40, 2, 5, 17, 17, 2, 2, 20, 20, 8, 22, 8, 71, 26, 26, 80, 242 }.これは、結果として得られる計算をk倍高速化するために 2kの 事前計算 とストレージを必要とし、空間と時間のトレードオフと なります。
モジュール制限 コラッツ予想の反例を探すという特別な目的のために、この事前計算は、トマス・オリベイラ・エ・シルバがコラッツ予想の計算による検証でn の大きな値まで使用した、さらに重要な加速につながります。ある与えられたb とk に対して、不等式が
f k k a + b ) = 3 c ( b ) a + d ( b ) < 2 k a + b すべてのa に対して成り立つならば、最初の反例が存在する場合、それは2 k b にはなり得ない。[ 13 ] f (2 n ) = n であり、 2 n f 2 (4 n + 1) = 3 n + 1であり、 4 n + 1 より小さいので、3 mod 4 でなければならない。コラッツ予想の反例ではない各開始値a に対して、そのような不等式が成り立つkが存在するため、1 つの開始値に対するコラッツ予想のチェックは、合同クラス全体のチェックと同じくらい良い。k が 増加するにつれて、検索では、より低いk の値によって排除されない剰余b をチェックするだけでよい。指数関数的に小さい割合の剰余だけが残る。[ 31 ]
3で割り切れる整数はサイクルを形成できないため、これらの整数を反例としてチェックする必要はありません。[ 32 ]
シラキュースの機能 k が奇数の場合、 3 k + 1 は 偶数となるので、3 k + 1 = 2 a k ′となり、 k ′ a ≥ 1 ですシラキュース関数 は、正の奇数の集合I から自身への関数f であり、 f ( k ) = k ′ となります( OEIS のシーケンス A075677 ) 。
シラキュース関数の特性には以下のようなものがあります。
すべてのk ∈ I f (4 k + 1) = f ( k )、3(4 k + 1) + 1 = 12 k + 4 = 4(3 k + 1) だからである。）より一般的には、すべてのp ≥ 1h に対して、f p − 1p h − 1) = 2 × 3 p − 1 h − 1f p − 1は関数反復表記 です。） すべての奇数h に対して、f (2 h − 1) ≤ 3 h − 1 / 2 が成り立つ 。 コラッツ予想は、 I のすべてのkに対して、 f n ( k ) = 1 となる整数n ≥ 1 が存在するという主張と同等である。
決定不能な一般化 1972年、ジョン・ホートン・コンウェイは、 コラッツ問題の自然な一般化がアルゴリズム的に決定不可能である ことを証明した。[ 33 ]
具体的には、彼は次の形式の関数を検討した。 g （ n ） = 1 私 n + b 私 いつ n ≡ 私 （ モジュール P ） 、 {\displaystyle {g(n)=a_{i}n+b_{i}}{\text{ when }}{n\equiv i{\pmod {P}}},} 、a 0 、b 0 、...、a P − 1b P − 1は、 g ( n )P = 2a 0 = 1 / 2 、 b 0 = 0a 1 = 3b 1 = 1で与えられます。コンウェイは、
g とn が与えられたとき、反復列g k ( n )は1に 到達しますか？停止問題を このように表現すると、決定不能となる。
コラッツ問題に近いものとして、次のような全称量化 問題がある。
g が与えられたとき、反復列g k ( n )は、すべてのn > 0 に対して1 に 到達しますか?このように条件を変更すると、問題の解決が難しくなったり簡単になったりする可能性があります（直感的には、肯定的な答えを正当化するのは難しいですが、否定的な答えを正当化する方が簡単かもしれません）。Kurtz と Simon [ 34 ] 算術階層ではさらに上位であることを証明しました。具体的には、 Π 0 2 完全です。この困難性の結果は、モジュラスP を 6480 に固定して関数g のクラスを制限した場合でも成り立ちます。[ 35 ]
この形式の簡略化されたバージョンのg の反復、すべてのb 私 {\displaystyle b_{i}} FRACTRAN と呼ばれる難解なプログラミング言語 で形式化されます。
計算複雑性において コラッツ予想および関連する予想は、計算複雑性を研究する際によく使用されます。[ 36 ] [ 37 ] ビジービーバー 関数を介して確立されます。ここで、BB(n) は、停止する任意のn 状態チューリングマシンが実行する最大ステップ数です。 ポール・エルデシュ による次の予想 (コラッツ予想と密接に関連) が偽である場合に限り、停止する 15 状態チューリングマシンが存在します。すべての n > 8 に対して、2 n [ 38 ] [ 39 ]
2024年に、停止するかどうかを判定するにはアンチヒドラ問題と呼ばれるコラッツ問題に似た問題を解く必要がある6状態マシンが発見されました。この種の単純な予想の証明さえも現在知られていないため、BB(6)を計算するのは非常に難しいことが示唆されます。[ 40 ] [ 41 ]
参考文献 ↑ マドックス、クレボーン D.、ジョンソン、D. ラモント (1997)。『ロゴ：回顧展 』ニューヨーク：ホーワース・プレス。160 ページ。ISBN 0-7890-0374-0 この問題は、ウラム予想、ヘイルストーン問題、シラキュース問題、カクタニ問題、ハッセのアルゴリズム、コラッツ問題など、他にもいくつかの名前で知られています 。 1 2 3 4 5 6 7 Lagarias, Jeffrey C. (1985). "The 3 x + 1 problem and its generalizations". The American Mathematical Monthly . 92 (1): 3– 23. doi : 10.1080/00029890.1985.11971528 . JSTOR 2322189 . ↑ラガリアス（1985） [ 2 ] p.4 によると、「シラキュース問題」という名称は、ハッセが1950年代にシラキュース大学 を訪れた際に提案された。 ↑ オコナー、ジョン・J.、 ロバートソン、エドモンド・F. 、 「ロタール・コラッツ」 、 マックチューター数学史アーカイブ 、 セント・アンドリュース大学 ↑ ピッコーバー、クリフォード A. (2001). 『数 の 不思議 』 オックスフォード：オックスフォード大学出版局。116-118 頁 。ISBN 0-19-513342-0 。↑ ホフスタッター、ダグラス・R. (1979). ゲーデル、エッシャー、バッハ . ニューヨーク：ベーシックブックス. pp. 400–2 . ISBN 0-465-02685-0 。↑ ガイ、リチャード K. (2004) 。 論における未解決問題 （第3版 ）。シュプリンガー・フェルラーク 。pp. 330–6。ISBN 0-387-20860-7 . Zbl 1058.11001 . 1 2 ラガリアス、ジェフリー C. 編 (2010). 究極の挑戦：3x + 1 問題 . アメリカ数学会 . ISBN 978-0-8218-4940-8 . Zbl 1253.11003 . 1 2 Tao, Terence (2022). "コラッツ写像のほぼすべての軌道はほぼ有界値に達する" . Forum of Mathematics, Pi . 10 e12. arXiv : 1909.03562 . doi : 10.1017/fmp.2022.8 . ISSN 2050-5086 . ↑ Leavens, Gary T.; Vermeulen, Mike (1992 年 12 月). "3 x + 1 探索プログラム". Computers & Mathematics with Applications . 24 (11): 79– 99. doi : 10.1016/0898-1221(92)90034-F . ↑ ローゼンダール、エリック。 「3x+1 遅延レコード」 。 2020 年 3 月 14 日 に取得 。 1 2 Barina, David (2025). 「コラッツ予想の収束に対する検証限界の改善」 (PDF) . The Journal of Supercomputing . 81 (7) 810. doi : 10.1007/s11227-025-07337-0 . S2CID 220294340 . 1 2 Garner, Lynn E. (1981). "On the Collatz 3 n + 1 algorithm" . Proceedings of the American Mathematical Society . 82 (1): 19– 22. doi : 10.1090/S0002-9939-1981-0603593-2 . JSTOR 2044308 . 1 2 Eliahou, Shalom (1993). "The 3 x + 1 problem: new lower bounds on nontrivial cycle lengths" . Discrete Mathematics . 118 (1): 45– 56. doi : 10.1016/0012-365X(93)90052-U . 1 2 3 Simons, J.; de Weger, B. (2005). "Theoretical and computational bounds for m -cycles of the 3 n + 1 problem" (PDF) . Acta Arithmetica . 117 (1): 51– 70. Bibcode : 2005AcAri.117...51S . doi : 10.4064/aa117-1-3 . 2022-03-18 のオリジナルからアーカイブ済み 。2023-03-28 に取得 。 {{cite journal}}: CS1 maint: bot: 元の URL の状態が不明です (リンク)↑ Lagarias (1985)、 [ 2 ] 1 2 Terras, Riho (1976). "正の整数における停止時間問題" (PDF) . Acta Arithmetica . 30 (3): 241– 252. doi : 10.4064/aa-30-3-241-252 . MR 0568274 . ↑ ハートネット、ケビン（2019年12月11日）。 「数学者が『危険な』問題で大きな成果を証明」 。 クアンタマガジン 。 ↑ クラシコフ、イリア。 ラガリアス、ジェフリー C. (2003)。 「 差分不等式を使用した 3 x + 1 問題の境界」 。 アクタ算術 。 109 (3): 237–258 . arXiv : math/0205002 。 Bibcode : 2003AcAri.109..237K 。 土井 ： 10.4064/aa109-3-4 。 MR 1980260 。 S2CID 18467460 。 ↑ Steiner, RP (1977). "シラキュース問題に関する定理". 第 7 回マニトバ数値数学会議議事録 . pp. 553–9 . MR 0535032 . ↑ Simons, John L. (2005). "3 x + 1 問題 に対する 2-サイクルの非存在について " . Math. Comp . 74 : 1565– 72. Bibcode : 2005MaCom..74.1565S . doi : 10.1090/s0025-5718-04-01728-4 . MR 2137019 . ↑ Hercher, C. (2023). " m <= 91の Collat z m サイクル は存在しない " (PDF) . Journal of Integer Sequences . 26 (3): Article 23.3.5. ↑ Colussi, Livio (2011年9月9日). 「コラッツ関数の収束クラス」 . Theoretical Computer Science . 412 (39): 5409–5419 . doi : 10.1016/j.tcs.2011.05.056 . hdl : 11577/106892 . ↑ Hew, Patrick Chisan (2016年3月7日). 「バイナリで作業すると1/3 h の循環小数部が保護される : Colussiの「コラッツ関数の収束クラス」へのコメント」 理論計算機科学 . 618 : 135–141 . doi : 10.1016/j.tcs.2015.12.033 .↑ ラガリアス、ジェフリー (1990)。 「3x+1 問題の有理サイクルのセット」 。 アクタ算術 。 56 (1): 33–53 . 土井 : 10.4064/aa-56-1-33-53 。 ISSN 0065-1036 。 ↑ Belaga, Edward G.; Mignotte, Maurice (1998). "Embedding the 3x+1 Conjecture in a 3x+d Context" . Experimental Mathematics . 7 (2): 145– 151. doi : 10.1080/10586458.1998.10504364 . S2CID 17925995 . ↑ バーンスタイン、ダニエル・J.ラガリアス、ジェフリー C. (1996)。 「3 x + 1 共役マップ」 。 カナダ数学ジャーナル 。 48 (6): 1154–1169 。 土井 : 10.4153/CJM-1996-060-x 。 ISSN 0008-414X 。 ↑ Chamberland, Marc (1996). "3 x + 1 問題の実数直線への連続拡張". Dynam. Contin. Discrete Impuls Systems . 2 (4): 495– 509. ↑ Letherman, Simon; Schleicher, Dierk; Wood, Reg (1999). "The (3 n + 1)-problem and holomorphic dynamics". Experimental Mathematics . 8 (3): 241–252 . doi : 10.1080/10586458.1999.10504402 . ↑ Scollo, Giuseppe (2007). 「 COMETAグリッドインフラストラクチャを使用して3 x + 1問題におけるクラスレコードを探す」 (PDF) . パレルモ大学のグリッドオープンデー 。 ↑ Lagarias (1985)、 [ 2 ] ↑ クレイ、オリバー・キーティング。 「コラッツ反例の長い探求」 。p. 208。 2024年 7月26日 取得 。 ↑ Conway, John H. (1972). "予測不可能な反復". Proc. 1972 Number Theory Conf., Univ. Colorado, Boulder . pp. 49–52 . ↑ Kurtz, Stuart A.; Simon, Janos (2007). "一般化コラッツ問題の決定不能性" . Cai, J.-Y.; Cooper, SB; Zhu, H. (編). Proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007. pp. 542–553 . doi : 10.1007 /978-3-540-72504-6_49 . ISBN 978-3-540-72503-9 。↑ Ben-Amram, Amir M. (2015). "整数上の反復区分的アフィン関数の死亡率: 決定可能性と複雑性". Computability . 1 (1): 19– 56. doi : 10.3233/COM-150032 . ↑ミシェル、パスカル (1993)。「忙しいビーバー の 競争とコラッツのような問題」。 数 理論理学アーカイブ 。32 (5): 351–367。doi : 10.1007 /BF01409968 。 ↑ 「ビジービーバーの硬度値BB(15)」 。 ↑ Stérin, Tristan; Woods, Damien (2021). "Hardness of busy beaver value BB(15)". arXiv : 2107.12475 [ cs.LO ]. ↑ エルデシュ、ポール (1979)。 「数論におけるいくつかの非従来的な問題」 。Mathematics Magazine。52 (2): 67–70。doi : 10.1080 /0025570X.1979.11976756。JSTOR 2689842。 2022年6 月 13日の オリジナルから アーカイブ 。 2022年7 月 7 日 取得 。 ↑ Brubaker, Ben (2024年7月2日). 「Fifth Busy Beaverで研究者たちは計算の限界に近づく」 . Quanta . 2025年8月24日 閲覧 . ↑ Sloane, N. J. A. (編). "数列 A386792 (Antihydra、BB(6) チューリングマシン (a の値))" .整数列の オンライン 百科事典 . OEIS Foundation.
外部リンク マシューズ、キース。「3 x + 1 ページ」。 エリック・ルーゼンダールによる継続的なボランティアコンピューティングプロジェクトは、より大きな値に対してコラッツ予想を検証している。 トマス・オリベイラ・エ・シルバによる別の進行中のボランティアコンピューティングプロジェクトでは、コラッツ予想の検証が続けられています（エリック・ルーゼンダールのページよりも統計データは少ないものの、さらなる進展が見られています）。 ワイスタイン、エリック W. 「コラッツ問題」。マスワールド PlanetMath の コラッツ問題。 ノチェラ、ジェシー。「コラッツパス」。ウルフラムデモンストレーションプロジェクト Eisenbud, D. (2016年8月8日).解読不可能？コラッツ予想 （ショートビデオ）. Numberphile. 2021年12月11日時点のオリジナルよりアーカイブ- YouTube経由。Eisenbud, D. (2016年8月9日).解読不可能？コラッツ予想 （追加映像）. Numberphile. 2021年12月11日にオリジナルからアーカイブ済み– YouTube経由。アレックス・コントロヴィッチ （出演）（2021年7月30日）。誰も解けない最も単純な数学の問題 （ショートビデオ）。Veritasium – YouTube経由。コンピューターは、この悪名高いほど扱いにくい数学の問題を解決する準備ができているのだろうか？ 
