コラッツの問題

出典: フリー百科事典『ウィキペディア(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→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で収束)することを証明した。

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

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

類似の問題[編集]

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

変数nが奇数の時の乗数の奇数自然数一般への拡張による類似問題[編集]

例えば「任意の 0 でない自然数 n に対して

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

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

変数nが奇数の時の加算数の奇数自然数一般への拡張による類似問題[編集]

また、もう一つの類似として、「任意の 0 でない自然数 n に対して

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

という操作を繰り返すと、有限回で 1 に到達する」という命題を考える。 ここで、l = 1 のときが上述のコラッツの問題である。しかし、l≥2の場合、(1を含まない、もしくは含むが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という数列のサイクルが得られる、このl = 2の場合、n=1, 2などを与えた場合有限回で1に到達するが、そのあとは、6, 3, 12, 6, 3と、3を繰り返すサイクルになる。このl = 2の場合、コラッツの予想を応用し、 「任意の 0 でない自然数 n に対して、上記の操作を行えば、有限回で3に到達する」という命題を代わりに立てれば、これが成り立つと予想される。

しかし、これも、たとえば、この二つの予想を一般化して、「任意の 0 でない自然数 n に対して

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

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

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

変数nが奇数の時の乗数と加算数双方の、奇数自然数への拡張による類似問題[編集]

以上の事から、一般化は困難ではあるが、個別事例として個々に考えるなら、更に進んで、「任意の 0 でない自然数 n に対して

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

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

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

参考文献[編集]

  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)


関連文献[編集]

  • 『数学100の問題』 日本評論社 ISBN 978-4535606142  「角谷の問題」として取り上げられている。

関連項目[編集]

外部リンク[編集]