コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

コラッツの問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』

これはこのページの過去の版です。Caserio (会話 | 投稿記録) による 2020年7月21日 (火) 01:20個人設定で未設定ならUTC)時点の版 (Modular restrictions)であり、現在の版とは大きく異なる場合があります。

コラッツの問題(コラッツのもんだい、Collatz problem)は、数論の未解決問題のひとつである。1937年にローター・コラッツが問題を提示した。問題の結論の予想を指してコラッツの予想と言う。固有名詞に依拠しない表現としては3n+1問題とも言われ、初期にこの問題に取り組んだ研究者の名を冠して、角谷(かくたに)の問題米田の予想ウラムの予想、他にはSyracuse問題などとも呼ばれる。数学者ポール・エルデシュは「数学はまだこの種の問題に対する用意ができていない」と述べ、解決した人に500ドルを提供すると申し出た。

コンピュータを用いた計算により、268 までには反例がないことが確かめられている[1]。 また、2011年度大学入試センター試験数学IIB第6問に題材として取り上げられた[2]

問題の概要

1から9999までの数に対して、1にいたるまでのステップ数をグラフにしたもの。
1から108までの、1に至るまでのステップ数のヒストグラム。x軸がステップ数で、頻度がy軸である。
2から107までの、1にいたるまでのステップ数をグラフにしたもの。

コラッツの問題は、「任意の正の整数 n をとり、

  • n偶数の場合、n を 2 で割る
  • n奇数の場合、n に 3 をかけて 1 を足す

という操作を繰り返すと、どうなるか」というものである。「どんな初期値から始めても、有限回の操作のうちに必ず 1 に到達する(そして 1→4→2→1 というループに入る)」という主張が、コラッツの予想である。

以下、もう少し詳しく定義する。

関数 f を次のように定義する。

ここで任意の正の整数から開始し、上記の演算を繰り返し実行することにより数列を作る。各ステップでの結果は次ステップの関数 f(n) の変数 n に代入される。数式で表現すると、以下のようになる:

このとき「初期値のとり方にかかわりなく、この操作を繰り返すと最終的に 1 に到達する」という主張が、コラッツの予想である。形式的に書くと、以下のようになる。

もしこの予想が誤りであるなら、1 を含まない数列を生成する初期値が存在するということになる。そのような数列は、1 を含まない繰り返し数列に突入するか、もしくは際限なく増大していくかのいずれかである。そのような数列はいまだ見つかっていない。

例として、初期値を 6 にすると、6, 3, 10, 5, 16, 8, 4, 2, 1 という、1に到達する数列を得る。このような数列をコラッツ数列と呼ぶ。

初期値を 11 とすると、11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 となり、1 に到達するまでにより長くかかる。

初期値として 27 を選ぶと、以下のように数列は111ステップにまで及び、その値は最終的に 1 に到達する前に 9232 にまで増大する。

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

コラッツの予想を証明するにあたっては、 初期値を奇数に限定してもかまわない。なぜなら初期値が偶数の場合でも、コラッツの漸化式に従えば因数の 2 は最終的にすべて除去され、奇数になるからである。

ビジュアル化


コラッツの数列を計算するプログラミング例

以下は擬似コードによるプログラミング例である。与えられた初期値に対するコラッツ数列を計算できる。

def collatz(n)
  show n
  if n.odd? and n > 1
    collatz(3n + 1)
  else if n.even?
    collatz(n / 2)

このプログラムは 1, 4, 2, 1 の無限サイクルを省くために 1 に到達すると停止するようになっている。もしコラッツ予想が正しければ、いかなる正の整数の初期値を与えても停止する。

この問題を、初期のコンピュータで計算することで研究したのがスタニスワフ・ウラムであった。

サイクル

このパートではショートカット形式で考える。

サイクルはすべて異なる整数による数列で、とする。ここで、, , ..., and である。既知のサイクルは長さ2ので、自明なサイクルと呼ばれる。

サイクルの長さ

自明ではないサイクルの長さは少なくとも である[3]。実際、 Eliahou (1993) は、サイクルの周期の長さが、

であることを示した。ここで かつ である。この結果は、連分数展開に基づく。最新の検証では、までコラッツ予想が正しいと判明しているので、同様の論法によりサイクルの長さの下限は (“ショートカット”無しなら )であると言える。

k-サイクル

k-サイクルとは、2k個に分割できるサイクルである:奇数からなる単調増加数列k個と、偶数からなる単調減少数列k個からなる。例えばサイクルが、奇数による単調増加数列1個と、偶数による単調減少数列1個で構成されたなら、1-cycleと呼ぶ[4]。Steiner (1977)は、1-cycleが、自明なサイクル(1;2)のみであることを証明した[5]。Simons (2004) は、Steinerの方法を使って、2-cycleが存在しないことを証明した[6]。Simons & de Weger (2005)はこの証明を68-cyclesまで拡張しました:k = 68まで、k-cycleは存在しない[4]。68を超えたところでは、この方法はサイクルの要素の上限を与える:例えば、75-cycleが存在したとすると、その中の要素の少なくとも1つは2385×250より小さいといえる[4]。そのため、コンピュータによる検証が進んでいくと、より大きなサイクルが除外されていく。より直観的にいうと、多くとも68以下の数列(各数列は単調増加数列と単調減少数列の連結)をつなげて作ったサイクルを探す必要はない。

この予想を支持する論拠

コラッツの予想は未解決だが、この問題を研究した多くの数学者は正しいだろうと考えている。そう予想される理由を以下に挙げる。

経験的証拠

この予想は、初期値が 5 × 260 =  5,764,607,523,034,234,880までは成り立つことがコンピュータで確認されている。この数値は、コンピュータのスピードアップとテスト技術の向上に伴って更新され続けている。

ヒューリスティクス

厳密な議論ではないヒューリスティクスであるが、ステップを経るごとに数の大きさがどのようになるかを考察しよう。今、n が偶数ならば、次のステップで大きさは半分になる。また、n が奇数ならば、次のステップで 3n + 1 になるが、これは必ず偶数であるから、その次に (3n + 1)/2 になることまでは確定している。ここまでを一つのステップと解釈すれば、このステップで大きさは約 3/2 倍になる。1回のステップを経た後に偶数になるか、奇数になるかが半々であると考えると、1/2 の確率で数の大きさは 1/2 倍になり、残る 1/2 の確率で数の大きさは 3/2 倍になる。よって、1回のステップで、数の大きさは (1/2)1/2 × (3/2)1/2 倍になると期待される。これは 1 より小さな値であるから、ステップを経るごとに「確率的に」小さくなると考えられる。この意味で、いつかは 1 に到達するとの予想は確からしい。

確率論の言葉を用いるとこれは無限のステップ数を取る極限で1に平均収束するということであり、厳密には予想の確からしさとは無関係である。ストレンマイヤーは1957年にマルティンゲールの理論を用いて上記の議論を精密化し、任意のコロモゴルフ測度の下で有限ステップ内に数の大きさが1に概収束(確率1で収束)することを証明した。

コラッツ予想の他の形式

パリティシーケンス

本節では、コラッツ関数を少し変形したものを考える:

nが奇数の場合には3n + 1が必ず偶数になるので上記のようにできる。

P(…)をパリティ数とする。P(2n) = 0 で、P(2n + 1) = 1 である。整数nのパリティシーケンス(もしくは、パリティベクトル)を、pi = P(ai), ただしa0 = n, and ai+1 = f(ai) と定義する。 (3n + 1)/2 または n/2、どちらの操作が適用されるかは、パリティに依存する。パリティシーケンスは操作のシーケンスに等しい。 f(n)に対してこの形式を適用すると、2つの整数mnのパリティシーケンスは、mnが2kを法として合同の場合のみ、最初のk項で一致するこが示される。これは、すべての整数がパリティシーケンスにより一意に識別されること意味し、さらに複数のコラッツ数列がある場合、対応するパリティシーケンスが異なる必要があることを意味します[7][8]

n=a·2k + b に関数 fk 回適用すると、a·3c + dとなる。ここでdbに関数fk回適用した結果で、cはその過程で3倍の演算を行った(増加した)回数である。(例えば、a·25 + 1 では、1が2,1,2,1と変化し最後に2になるので、3回の増加がある。よって結果はa·33+2 である。a·22 + 1 では、1が2に増加しその後1になるので、結果はa·3 + 1 となる。) bが2k - 1の場合には、 k回の増加があり、結果は2·a·3k - 1となる。aに掛かる係数は、aには無関係で、bにのみ依存する。これにより、特定の形式の数値が特定の反復回数の後、常により小さい数値になることを予測できます。例えば、4a + 1 は、2回のf操作により3a + 1となり、16a + 3は4回のf操作により9·a + 2となる。これらの小さくなった数が1へとつながるかどうかは、 aの値に依存する。

整数、有理数、複素数一般への変数nの拡張による問題の拡張

コラッツの問題は、その代入される変数nを、自然数から、0や負の数を含む整数、有理数、複素数へと拡張することが可能である。

検証計算の最適化

時間と空間のトレードオフ

上記の パリティシーケンス により、コラッツ数列の計算の高速化が可能である。

(パリティシーケンス節のf関数を使ったとして)kステップ先にジャンプする方法ために、まず現在の数値を2つに分割します:b(2進数表記で下位kビット)と、a(残りの上位ビット)。kステップをジャンプした結果は以下になる:

f k(a 2k + b) = a 3c(b) + d(b).

c(もしくは3c)とd配列は、kビットの数すべてについて事前計算しておく。d(b)はbf関数をk回行った数で、c(b)はその間に登場した奇数の数である[9]。例えばk=5なら5ステップのジャンプが可能で、そのために下位5ビットを分割して、下記配列を使う:

c(0..31) = {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) = {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}

これは、2k個の事前計算とストレージが要求される。これにより計算速度がk倍高速化出来るが、時間と空間のトレードオフである。

Modular restrictions

コラッツ予想の反例を探すにあたって、上記の事前計算を使うと加速させることができる。Tomás Oliveira e Silvaは、コラッツ予想の検証に用いた。

もし、与えられた bk で、不等式

f k(a 2k + b) = a 3c(b) + d(b) < a 2k + b

が成り立ったとすると、すべての a についても成立する。そうすると、最初の反例(存在するとして)は、 2kを法としてbと合同ではないと言える[10]

例えば、最初の反例は必ず奇数である。なぜならばf(2n) = nで、2nよりも小さいから。同様に、最初の反例はmod 4で3と合同である。なぜならば、f2(4n + 1) = 3n + 1 で、4n + 1 より小さいからである。コラッツ予想の反例でないすべての a には、上記不等式が成立するkが存在する。なので、ある数のコラッツ予想の検証するとき、合同なクラスを検証するとよい。k が増加したときの検証は、より小さい k で除外されなかった b についてのみ検証すればよい。指数関数的に小さい割合だけが残ることになる[11]。例えば mod 32では、b=7, 15, 27, 31だけが残る。

類似の問題

関数 f の定義を少し変えることにより、コラッツの問題の類似を考えることができる。

変数nが奇数の時の乗数の奇数一般への拡張による類似問題

例えば「任意の正の整数 n に対して

  • n が偶数の場合、n を 2 で割る
  • n が奇数の場合、n に 2m – 1 (m ≥ 1)をかけて 1 を足す

という操作を繰り返すと、有限回で 1 に到達する」という命題を考える。m = 1 のとき(nが奇数なら単に1を足す)は、この命題が正しいことを簡単に証明できる。m = 2 の場合が上述のコラッツの問題である。m ≥ 3 の場合は、mの値とnの初期値によっては、1を含まない繰り返し数列、もしくは際限なく増大していく数列が得られるため、この命題は一般に成り立たない。たとえば m = 3 の場合、nの初期値を13に設定すると、13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13 という1を含まない数列のサイクルが得られる。これは上記のヒューリスティクスの観点からして、mが大きくなるほど1に到達する可能性は低くなると予想されることとも符合する。

変数nが奇数の時の加算数の奇数一般への拡張による類似問題

また、もう一つの類似として、「任意の正の整数 n に対して

  • n が偶数の場合、n を 2 で割る
  • n が奇数の場合、n に 3をかけて 2l - 1 (l ≥ 1) を足す

という操作を繰り返すと、有限回で 1 に到達する」という命題を考える。 ここで、l = 1 のときが上述のコラッツの問題である。しかし、l ≥ 2の場合、1を含まない繰り返し数列が得られる場合があるので、この命題は一般に成り立たない。

たとえば、l = 2として、初期値n = 43を与えた場合、43, 132, 66, 33, 102, 51, 156, 78, 39, 120, 60, 30, 15, 48, 24, 12, 6, 3, 12, 6, 3という数列が得られ、この命題は成り立たない。初期値nが1, 2などなら有限回で1に到達するが、他の初期値に対しては3, 12, 6, 3と、3を繰り返すサイクルになると思われる。そこでl = 2に対してコラッツの予想を応用し、「任意の正の整数 n に対して、上記の操作を行えば、有限回で1または3に到達する」という命題を代わりに立てれば、これが成り立つと予想される。

この二つの予想を一般化して、「任意の正の整数 n に対して

  • n が偶数の場合、n を 2 で割る
  • n が奇数の場合、n に 3をかけて 2l – 1 (l ≥ 1) を足す

という操作を繰り返すと、有限回で1または2l – 1 (l ≥ 1) に到達する」という命題を立てたとしても、l ≥ 3以上の場合には、この命題は一般に成り立たない。たとえばl = 3の場合、任意の自然数nが1または5に到達するという命題になるが、n=13の時、13, 44, 22, 11, 38, 19, 62, 31, 98, 49, 152, 76, 38, 19と、19を繰り返す無限ループになり、1にも5にも到達しない。

ただし、上の、2l – 1 (l ≥ 1) が、0以上の整数aを用いて3a–1 (a ≥ 1) で表されるときには、上記のプロセスを繰り返せば、有限回数で1または3a–1 (a ≥ 1) に到達することは予想される。a = 1の場合がコラッツの問題である。a = 2の場合は、上記でl = 2のケースである。

変数nが奇数の時の乗数と加算数双方の、奇数一般への拡張による類似問題

以上のことから、一般化は困難ではあるが、個別に考えるなら、さらに進んで、「任意の正の整数 n に対して

  • n が偶数の場合、n を 2 で割る
  • n が奇数の場合、n に 2m – 1 (m ≥ 1) をかけて、2l – 1 (l ≥ 1) を足す

という操作を繰り返すとき、nmlの値に応じてどのような数列が展開されるか」

という問題にも拡張できるなど、コラッツの問題の類似問題の幅は広い。

脚注

  1. ^ Barina, D. Convergence verification of the Collatz problem. J Supercomput (2020). https://doi.org/10.1007/s11227-020-03368-x
  2. ^ 数学Ⅱ・数学B(2011年1月24日時点のインターネットアーカイブ) (PDF) - 【センター試験】2011年度大学入試センター試験速報-問題と正解(47NEWS)(2011年1月23日時点のインターネットアーカイブ)
  3. ^ Eliahou, Shalom (1993-08-01). “The 3x+1 problem: new lower bounds on nontrivial cycle lengths”. Discrete Mathematics 118 (1): 45–56. doi:10.1016/0012-365X(93)90052-U. 
  4. ^ a b c Simons, J.; de Weger, B. (2003). “Theoretical and computational bounds for m-cycles of the 3n + 1 problem”. Acta Arithmetica 117 (1): 51–70. Bibcode2005AcAri.117...51S. doi:10.4064/aa117-1-3. http://deweger.xs4all.nl/papers/%5B35%5DSidW-3n+1-ActaArith%5B2005%5D.pdf. 
  5. ^ Steiner, R. P. (1977). “A theorem on the syracuse problem”. Proceedings of the 7th Manitoba Conference on Numerical Mathematics. pp. 553–9. MR535032 
  6. ^ Simons, John L. (2005). “On the nonexistence of 2-cycles for the 3x+1 problem”. Math. Comp. 74: 1565–72. Bibcode2005MaCom..74.1565S. doi:10.1090/s0025-5718-04-01728-4. MR2137019. 
  7. ^ a b Lagarias, Jeffrey C. (1985). “The 3x + 1 problem and its generalizations”. The American Mathematical Monthly 92 (1): 3–23. doi:10.1080/00029890.1985.11971528. JSTOR 2322189. 
  8. ^ Terras, Riho (1976), “A stopping time problem on the positive integers”, Acta Arithmetica 30 (3): 241–252, doi:10.4064/aa-30-3-241-252, MR0568274, http://matwbn.icm.edu.pl/ksiazki/aa/aa30/aa3034.pdf 
  9. ^ Scollo, Giuseppe (2007), “Looking for Class Records in the 3x+1 Problem by means of the COMETA Grid Infrastructure”, Grid Open Days at the University of Palermo, http://www.dmi.unict.it/~scollo/seminars/gridpa2007/CR3x+1paper.pdf 
  10. ^ Garner, Lynn E.. “On The Collatz 3n + 1 Algorithm”. 27 March 2015閲覧。
  11. ^ [7]Theorem D.

関連文献

関連項目

外部リンク

');