コラッツの問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動: 案内、 検索
これは30以下の整数（27のみ除く）の操作を表にしたもの。どの数も最終的に1となる。

コラッツの問題（コラッツのもんだい、Collatz problem）とは、コラッツの予想あるいは角谷の予想ともいい、数論の未解決問題のひとつである。1937年にローター・コラッツが問題を提示して以来、コラッツの問題と呼ばれるが、「3n+1問題」「Syracuse予想」などの異名もある。数学者ポール・エルデシュは「数学はまだこの種の問題に対する用意ができていない」と述べ、解決した人に500ドルを提供すると申し出た。

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

目次

問題の概要 [編集]

問題の概要は、「任意の0でない自然数 n をとり、

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

という操作を繰り返すと、有限回で 1 に到達する」という主張である（1 に到達すると、1→4→2→1 を繰り返す）。

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

f(n) = \begin{cases} n/2 &\mbox{if } n \equiv 0 \\ 3n+1 & \mbox{if } n\equiv 1 \end{cases} \pmod{2}

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

a_i = \begin{cases}n & \mbox{for } i = 0 \\ f(a_{i-1}) & \mbox{for } i > 0\end{cases}

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

\forall n \isin \mathbb{N} > 0 \ \exists i \isin \mathbb{N}: (a_0 = n \Rightarrow a_i = 1)

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

例 [編集]

例として、nの初期値を 6 にする。すると、6, 3, 10, 5, 16, 8, 4, 2, 1 という数列を得る（初期値にかかわりなく「いつでも」1 に到達する、というのがコラッツの問題の主張である）。このような数列をコラッツ数列と呼ぶ。

n の初期値を 11 とすると、11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 となり、この数列は 1 に到達するまでにもっと長くなる事がわかる。

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

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

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

ある特定のコラッツ数列を簡単に計算できる。以下は擬似コードによるプログラミング例である：

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

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

この予想を支持する論拠 [編集]

この予想は未解決だが、この問題を調査した多くの数学者は直感的に正しいと考えている。そう予想される理由を以下に挙げる。

経験的証拠 [編集]

この予想は 3 × 253 = 27,021,597,764,222,976 までチェックされている。この記録は、コンピュータのスピードアップとテスト技術の向上に伴って伸ばされ続けている。

ヒューリスティクス [編集]

厳密な議論ではないヒューリスティクスであるが、ステップを経るごとに数の大きさがどのようになるかを考察しよう。今、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で収束)することを証明した。

類似の問題 [編集]

関数 f の定義を少し変えることにより、コラッツの問題の類似を考えることができる。例えば「任意の 0 でない自然数 n に対して

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

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

参考文献 [編集]

  1. ^ T. Oliveira e Silva, "Maximum Excursion and Stopping Time Record-Holders for the 3x+1 Problem: Computational Results", Mathematics of Computation, 68, 371-384, 1999.
  2. ^ http://www.47news.jp/47topics/pdf/23sugaku2b_q.pdf (PDF)

関連項目 [編集]

外部リンク [編集]

「http://ja.wikipedia.org/w/index.php?title=コラッツの問題&oldid=46968148」から取得