コラッツ予想というのをご存知だろうか??
この内容というのは
任意の0でない自然数Nをとり、
○Nが偶数の場合、Nを2で割る○Nが奇数の場合、Nに3をかけて1を足すこの操作を繰り返すと、有限回で1に到達する。

この問題は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未満の数値」になった時点で、すでに実験済みの結果になってしまうからである
まず、初期値を奇数値

とおく。
これは奇数値なので

となる。
この値は、常に偶数値であるため、

である。
もしこの値が偶数値なら

となり

なので、不適。
よって

コラッツ予想を否定する数列があるとすれば、第4項までは自動的に数が決定される。
ここからは、じっくり腰を落ちつけて考察していかねばならない。
しかし、とりあえず、腰を落ち着けての考察は、また今度にしよう。
ある数学者は、こんな事を言った。
「数学はまだこの種の問題に対する用意ができていない」この言葉が、正しいのかどうかはわからないが、フェルマーの定理が証明に至るまで、360年もかかった。
数学の未解決問題は非常に、解決に時間がかかる。
この、コラッツ予想も証明まで何百年かかるかはわからないが、この証明に至る過程で、「数の性質」について、ものすごい発見があるのだろうと期待してしまう。
最後に、このコラッツ操作のプログラムを紹介しているページがあるので、是非、試していただきたい
コラッツプログラムのページへ
そんなに難しくないと思いました(多分中学生・高校生でも解けます)
以下の問題です(いいのかな転載して)。
自然数nに対して、次のように定めた操作 f を行う。
操作 f : 「 nが偶数ならばnを2で割る。
nが奇数ならばnを3倍して1を加える。」
上の操作を10回行う。10回目ではじめて1となる自然数をすべて求めなさい。
問題全体は京都府教育委員会のHPにあります。解答は2月下旬にHPに掲載となっていましたが、まだのようです。
試行数が10回程度だと、全然、苦もなく手で書き出せるのでかわいい問題ですね。
答えは、「1024、170、168、160、26、24」 ・・・かな?
もちろん、10回の部分をn回という風にされると、恐らく、未解決問題なだけに解けないと思いますが、せめて、20回、30回という風にすれば、もっと、嫌ぁ~な問題になるでしょうね。
a1≡3(mod4)
a3≡3(mod4)
a5≡3(mod4)
…
a∞≡3(mod4)
をすべて満たす場合は無限に大きくなりますね。
(2進法で考えると、奇数項の末尾2桁が必ず11になる数字)
そうですね。
奇数を3倍して1を足した数は必ず偶数になるので、次は必ず、「2で割る」という作業になりますね。
「3倍して、1を足した数を2で割る」という作業を、「試行」と名づけると、ある数を試行すると奇数、その奇数を試行するとまた奇数・・・
という風になっていくと、無限に大きくなっていきます。
しかし、そんな数が今のところ、見つかってはいないんです。
(恐らく、存在しない)
a(1n)≡3(mod4)
…
a(mn)≡3(mod4)
を満たすとき、
a(mn+1)-a(mn)=4×3^m
となりますよね。
a(mn)は発散してしまうので、数字が見つかるわけはないと思うんですが、この試行を繰り返す以外に、1に収束せずに発散する可能性はあるんでしょうか・・・もしくは、別ループ?
確かに、無限に発散する数はないというのは直感的には理解できますね。
しかし、その理解も厳密な証明がなければ、単なる直感にしか過ぎないというのがつらいところです。
1に収束しない場合としてありうるのは
①無限に発散する
②「1→4→2→1」以外のループが存在する。
③無限に発散もしないし、ループにもならずに、試行を繰り返す。
という場合が考えられますが、③はありえません
発散も収束もしない場合、コラッツ数列を{An}とすれば
x<{An}<y となる整数x、yが存在するという事になります。
x以上、y以下の整数は有限個なので、この範囲内で{An}が無限に異なる値を取り続ける事はできません。
従って、この場合は必ずループが存在することになります。
よって、①②を否定できればいいということですね。
ここでは、角谷(コラッツ)予想が肯定的に
証明されるための"必要条件"として、
「系列は、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に)収束しないで無限大に発散してしまう
反例があるかどうかは未解決です。
非常に興味のある回答です。
ただ、仮定で存在するはずの奇数Aの定義の式において、分数の部分がとてもわかりにくいので、なんかLatexかなんかで見たいですね・・・
やはり、数式をテキストで書くと限界があるのでしょうか・・・
それにしても興味深いです。
> 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
となるのではないでしょうか。
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に収束する整数値を求める方法があります。