fc2ブログ

数学史、整数論、数学オリンピック、未解決問題・・・をわかりやすく証明を通して解説していきます。

コラッツ予想

コラッツ予想というのをご存知だろうか??

この内容というのは


任意の0でない自然数Nをとり、

○Nが偶数の場合、Nを2で割る

○Nが奇数の場合、Nに3をかけて1を足す

この操作を繰り返すと、有限回で1に到達する。

08022201.jpg


この問題は1937年に、問題提起されてから、未だ解決していない。
いわゆる、未解決問題である。


数学には、まだまだたくさんの未解決問題があるが、その中でも、問題そのものが非常に単純明快なものとして、非常に有名である。


この問題が、今現在、どの辺りまで証明が進んでいるのかはわからない。


ただ、「27,021,597,764,222,976」以下の自然数で、このコラッツ予想が正しいとわかっている。


ほんの少し触ってみよう。


どういう風に考えればよいだろうか?

まず、初期値に関しては奇数値だけを考えればよい。
初期値が偶数値なら、奇数値になるまで2で割り続けることになるからだ。


証明は恐らく、背理法によるものがスマートになるのではないか。

要するに、コラッツ予想が否定されれば

○この操作を繰り返すと、Nが無限に大きくなっていく。

○「1→4→2→1」以外のループを繰り返す。

こんな数が存在しているはずなのである。


「27,021,597,764,222,976」まで成立しているからといって、コラッツ予想が正しいと言えるはずもないのは言うまでもない。

また、確率的な解釈から数値の変化を見ることもできるが、もちろん、予想の範囲から抜け出せるものではない。



試行実験してみよう。

・初期値を1から順番に、コラッツ操作を繰り返していく。
・そして、最終的に「1→4→2→1」のループになったのを確認する。
・確認したら、初期値を2にする。

これを延々と繰り返すと、ある数値Xでコラッツ予想が否定されたとしよう。


このXという数値は、コラッツ操作し続けても、決して「X未満の数値」にはならない。
なぜなら「X未満の数値」になった時点で、すでに実験済みの結果になってしまうからである


まず、初期値を奇数値

08022202.jpg
とおく。

これは奇数値なので
08022203.jpg
となる。

この値は、常に偶数値であるため、
08022204.jpg
である。


もしこの値が偶数値なら
08022205.jpg
となり
08022206.jpg
なので、不適。

よって
08022207.jpg


コラッツ予想を否定する数列があるとすれば、第4項までは自動的に数が決定される。
ここからは、じっくり腰を落ちつけて考察していかねばならない。


しかし、とりあえず、腰を落ち着けての考察は、また今度にしよう。



ある数学者は、こんな事を言った。

「数学はまだこの種の問題に対する用意ができていない」


この言葉が、正しいのかどうかはわからないが、フェルマーの定理が証明に至るまで、360年もかかった。

数学の未解決問題は非常に、解決に時間がかかる。

この、コラッツ予想も証明まで何百年かかるかはわからないが、この証明に至る過程で、「数の性質」について、ものすごい発見があるのだろうと期待してしまう。


最後に、このコラッツ操作のプログラムを紹介しているページがあるので、是非、試していただきたい

コラッツプログラムのページへ




よろしければ、クリックお願いします⇒ 「数学ブログ」
ついでに、こちらも参加しております⇒ 「人気ブログランキング」
2008年02月23日 | 未解決問題 | トラックバック(1)件 | コメント(15)件



コメント
第一回京都府高校生数学コンテスト問題とコラッツ予想
はじめまして、通りすがりのものです。コラッツ予想の設定を用いた問題が第一回の京都府高校生数学コンテストに出題されていました。
そんなに難しくないと思いました(多分中学生・高校生でも解けます)

以下の問題です(いいのかな転載して)。

 自然数nに対して、次のように定めた操作 f を行う。

 操作 f : 「 nが偶数ならばnを2で割る。
          nが奇数ならばnを3倍して1を加える。」
      
     上の操作を10回行う。10回目ではじめて1となる自然数をすべて求めなさい。

  問題全体は京都府教育委員会のHPにあります。解答は2月下旬にHPに掲載となっていましたが、まだのようです。
2008/02/23(土) 14:34 | URL | 数学好きの通りすがり #-[ 編集]
数学好きの通りすがり>

試行数が10回程度だと、全然、苦もなく手で書き出せるのでかわいい問題ですね。

答えは、「1024、170、168、160、26、24」 ・・・かな?


もちろん、10回の部分をn回という風にされると、恐らく、未解決問題なだけに解けないと思いますが、せめて、20回、30回という風にすれば、もっと、嫌ぁ~な問題になるでしょうね。
2008/02/23(土) 18:57 | URL | オイラー #-[ 編集]
a1=2n+1として、
a1≡3(mod4)
a3≡3(mod4)
a5≡3(mod4)

a∞≡3(mod4)
をすべて満たす場合は無限に大きくなりますね。
(2進法で考えると、奇数項の末尾2桁が必ず11になる数字)
2008/02/27(水) 04:31 | URL | 通りすがりですが・・・ #-[ 編集]
通りすがりですが・・・>

そうですね。

奇数を3倍して1を足した数は必ず偶数になるので、次は必ず、「2で割る」という作業になりますね。

「3倍して、1を足した数を2で割る」という作業を、「試行」と名づけると、ある数を試行すると奇数、その奇数を試行するとまた奇数・・・

という風になっていくと、無限に大きくなっていきます。

しかし、そんな数が今のところ、見つかってはいないんです。
(恐らく、存在しない)
2008/02/27(水) 16:56 | URL | オイラー #-[ 編集]
試作回数=mとし、n番目の項をa(mn)と置くとすると、
a(1n)≡3(mod4)

a(mn)≡3(mod4)
を満たすとき、
a(mn+1)-a(mn)=4×3^m
となりますよね。
a(mn)は発散してしまうので、数字が見つかるわけはないと思うんですが、この試行を繰り返す以外に、1に収束せずに発散する可能性はあるんでしょうか・・・もしくは、別ループ?
2008/02/28(木) 03:58 | URL | 通りすがりですが・・・ #-[ 編集]
通りすがりですが・・・>

確かに、無限に発散する数はないというのは直感的には理解できますね。
しかし、その理解も厳密な証明がなければ、単なる直感にしか過ぎないというのがつらいところです。

1に収束しない場合としてありうるのは

①無限に発散する
②「1→4→2→1」以外のループが存在する。
③無限に発散もしないし、ループにもならずに、試行を繰り返す。

という場合が考えられますが、③はありえません

発散も収束もしない場合、コラッツ数列を{An}とすれば
x<{An}<y となる整数x、yが存在するという事になります。

x以上、y以下の整数は有限個なので、この範囲内で{An}が無限に異なる値を取り続ける事はできません。
従って、この場合は必ずループが存在することになります。

よって、①②を否定できればいいということですね。
2008/02/28(木) 10:30 | URL | オイラー #-[ 編集]
ループは1→4→2→1に限定される
こんにちは、通りがかりました。

ここでは、角谷(コラッツ)予想が肯定的に
証明されるための"必要条件"として、

「系列は、1→4→2→1以外の箇所でループしない」ことを示そうと思います。

[証明]
※以下、a^bは、aのb乗のこととする。c・dは、cとdの積のこととします。
下記、...は、式を書ききれないので省略した部分です。

ループすると仮定します。

次のように表せる(正の)奇数Aが存在するはずです。

(3・(...(3・((3A+1)/2^m[1])+1)/2^m[2])+1)...)+1)/2^m[k]=A

(m[1],...,m[k]は自然数,k≧1)

分数表現でないように整式に変形すると、

3・(...(3・(3・(3・A+1)+2^m[1]) ) + 2^(m[1]+m[2]) )
+2^(m[1]+m[2]+m[3]) ) +...)+
2^(m[1]+m[2]+...+m[k-2]))
=2^(m[1]+m[2]+...+m[k-1])(2^m[k]・A-1)...[001]

3と2^(m[1]+m[2]+...+m[k-1])は、互いに素だから、

3=2^m[k]・A-1
2^m[k]・A=4

Aは奇数だから、A=1,m[k]=2

[001]式の両辺を3で割って、一部移項すると、

3・(...(3・(3・(3・A+1)+2^m[1]) ) + 2^(m[1]+m[2]) )
+2^(m[1]+2^m[2]+2^m[3]) ) +...)
+2^(m[1]+m[2]+...+m[k-3]) )
=2^(m[1]+m[2]+...+m[k-2])(2^m[k-1]-1)...[002]

3と2^(m[1]+m[2]+...+m[k-2])は、互いに素だから、

3=2^m[k-1]-1
2^m[k-1]=4

m[k-1]=2

同様にして、

...
m[k-2]=m[k-3]=...=m[4]=2
...
3・(3・(3A+1)+2^m[1])=2^(m[1]+m[2])(2^m[3]-1)

3と2^(m[1]+m[2])は、互いに素だから、

3=2^m[3]-1
2^m[3]=4

m[3]=2


3・(3A+1)=2^m[1](2^m[2]-1)

3と2^m[1]は、互いに素だから、
3=2^m[2]-1
2^m[2]=4
m[2]=2

2^m[1]=3A+1=3・1+1=4
m[1]=2

よって、ループを満たすのは、

A=1,m[1]=m[2]=...=m[k]=2の時、かつ、その時のみです。

「系列は、1→4→2→1以外の箇所でループしない」が証明されました(?)。
Q.E.D.

※これで合っていると思いますがどうでしょうか?

数列が、(1に)収束しないで無限大に発散してしまう
反例があるかどうかは未解決です。
2009/02/23(月) 15:34 | URL | CEGIPO #4ARdecsc[ 編集]
No title
CEGIPO>

非常に興味のある回答です。

ただ、仮定で存在するはずの奇数Aの定義の式において、分数の部分がとてもわかりにくいので、なんかLatexかなんかで見たいですね・・・

やはり、数式をテキストで書くと限界があるのでしょうか・・・

それにしても興味深いです。
2009/02/23(月) 23:44 | URL | オイラー #-[ 編集]
No title
通りすがりですが・・・>
> 3と2^(m[1]+m[2]+...+m[k-1])は、互いに素だから、
>
> 3=2^m[k]・A-1
この部分が間違っていると思うのですが、いかがでしょうか。
3と2^(m[1]+m[2]+...+m[k-1])は、互いに素だから、
Lを整数として、
3L=2^m[k]・A-1
となるのではないでしょうか。
2009/08/13(木) 13:44 | URL | ライプニッツ #-[ 編集]
横から失礼します
たまたまお見かけしましたので、少しお邪魔します。

CEGIPOさんの証明は、ライプニッツさんのご指摘どおり、不備があります。
(2^m[k]・A-1)が3の倍数である事しか言えませんので、3と等しいとするのは誤りです。この事は、証明中で、Aが正である条件が使われていない事からも示唆されます。実際、コラッツ予想を整数一般に拡張すると、少なくとも以下のようなループが存在します:
・1→4→2→1
・0→0
・-1→-2→-1
・-5→-14→-7→-20→-10→-5
・-17→-50→-25→-74→-37→-110→-55→-164→-82→-41→-122→-61→-182→-91→-272→-136→-68→-34→-17
ちなみに、コラッツ予想は分母を3のベキとする正の有理数に拡張する事ができ(この場合は分子の偶奇のみ考えます)、やはり1のループに入ると予想できます。

さて、コラッツ予想におけるステップでは、奇数の手順のあとに必ず偶数の手順が来ますので、これらは一つにまとめた方が好都合であると、すぐに気付きます:すなわち、
・xが偶数であるなら、f(x)=x/2
・xが奇数であるなら、f(x)=(3x+1)/2
とします。この時、x_0 = x, x_{n+1} = f(x_n)とするとき、各x_nを2で割った余りでできる二進列をパリティベクトルと呼びます。
こうすると、おどろくほど素直な対象性が導かれます。例えば、
・xを2^kで割った余りと、パリティベクトルの最初のk個は、1対1に対応する。
・x=x_0からn回手順を繰り返してy=x_nとなる時、(x+2^n)からn回手順を繰り返すと(y+3^m)となる。ここでmはパリティベクトルの最初のn個に含まれる"1"の数である。
・(2^k-1)は、k回の手順で(3^k-1)になる。
・パリティベクトルのある場所から同じ長さのパターンが無限に繰り返されている場合、そこは必ずループになっている。別の言い方をすると、仮に発散する値があったとすると、それは決して同じパターンを無限に繰り返す事はしない。
・テキストでは書きにくいの割愛しますが、実は任意長のパリティベクトルから、その手順を踏む両端の整数値を求める方法が存在します。簡単に求められ、しかも数学的に興味深い形になるので、お試しください。
・上の式から、任意の有限長のパリティベクトルを冒頭部分に持ち、しかもかならず1に収束する整数値を求める方法があります。
2010/06/23(水) 23:57 | URL | くろ #WV4V227M[ 編集]
承認待ちコメント
このコメントは管理者の承認待ちです
2011/02/11(金) 23:20 | | #[ 編集]
管理人のみ閲覧できます
このコメントは管理人のみ閲覧できます
2011/05/19(木) 19:30 | | #[ 編集]
承認待ちコメント
このコメントは管理者の承認待ちです
2011/06/08(水) 12:34 | | #[ 編集]
承認待ちコメント
このコメントは管理者の承認待ちです
2012/07/22(日) 16:37 | | #[ 編集]
承認待ちコメント
このコメントは管理者の承認待ちです
2012/07/22(日) 22:47 | | #[ 編集]
コメントの投稿
管理者にだけ表示を許可する
トラックバック


この記事にトラックバックする(FC2ブログユーザー)

xkcd - Collatz Conjecture : 誘いがこなくなる問題

©xkcd.com Creative Commons Attribution-NonCommercial 2.5 License...
プロフィール

オイラー

Author:オイラー
・得意分野
 整数論、解析学、幾何学
 複素数、数列 etc
・苦手分野
 行列、群論

質問、相互リンク等連絡があれば、kick_back_endless_shock◎yahoo.co.jpまでお願いします。

ブログ内検索
カテゴリー
月別アーカイブ
最近の記事
最近のコメント
最近のトラックバック
数学リンク
オススメ
広告
マイクロアドBTパートナーでおこづかいゲット!