コラッツのなんか
■ このスレッドは過去ログ倉庫に格納されています
コラッツ問題の操作
ある自然数の初期値について
偶数だったら2で割って奇数だったら3をかけて1足す
これを繰り返すっていう環境において気になる法則を見つけたよ
説明のため自然数を6で割ったあまりで分類しておく。
nは0≦nを満たす整数
表記の簡便のため6n+1,6n+3,6n+5、および6n+2,6n+4,6n+6で表される要素を集めた集合をそれぞれ集合6n+1,集合6n+3,集合6n+5、および集合6n+2,集合6n+4,集合6n+6と呼ぶことにします。
(※)
集合6n+1と集合6n+3と集合6n+5の要素は、すべて偶数に奇数を足した数なので、三つの集合の任意の要素は奇数
同様に集合6n+2と集合6n+4と集合6n+6の要素は、すべて偶数に偶数を足した数ので、三つの集合の任意の要素は偶数
操作が行われるとき
偶数の要素は2で割られるから、集合6n+2,集合6n+4,集合6n+6それぞれに含まれる要素は、集合3n+1,集合3n+2,集合3n+3っていう集合に移る。
例えばn=3のときの6n+2の値は20。これが2で割られるから10。これは3n+1のn=3のときの値。
奇数の要素は3がかけられてそのあと1足されるから、集合6n+1,集合6n+3,集合6n+5それぞれに含まれる要素は、集合18n+4,集合18n+10,集合18n+16っていう集合に移る
例えばn=3のときの6n+1の値は19。これが3をかけられて1を足されるから58。これは18n+4のn=3のときの値。
また、集合18n+4と集合18n+10と集合18n+16の要素はすべて偶数だから、2で割られて集合9n+2,集合9n+5,集合9n+8にそれぞれ移る
例えばn=3のときの18n+4の値は58。これが2で割られて29。これは9n+2のn=3のときの値。
そして、集合9n+2,集合9n+5,集合9n+8の要素はすべて3で割ると2余る数だから、これら三つの集合に含まれるすべての要素は集合3n+2の部分集合。>>2続き ここで集合3n+1,集合3n+2,集合3n+3それぞれに含まれる偶数の要素と奇数の要素について考える。
集合3n+1について
@偶数の要素はnが奇数のときのもの
A奇数の要素はnが偶数のときのもの
ここでf(n)=3n+1という関数を用意する。
@のとき
kを、0≦kを満たす整数とし、n=2k+1とすると、f(k)=6k+4
Aのとき
kを、0≦kを満たす整数とし、n=2kとすると、f(k)=6k+1
例えば16は集合3n+1の要素。これはnが5ときのもの。
nが奇数なので、@のとき5=2k+1を満たすようなkは2。
これをf(k)=6k+4に代入すると16。よって16は集合6k+4の要素。
同様に
集合3n+2について
@偶数の要素はnが偶数のときのもの
A奇数の要素はnが奇数のときのもの
ここでf(n)=3n+2という関数を用意する。
@のとき
kを、0≦kを満たす整数とし、n=2kとすると、f(k)=6k+2
Aのとき
kを、0≦kを満たす整数とし、n=2k+1とすると、f(k)=6k+5
集合3n+3について
@偶数の要素はnが奇数のときのもの
A奇数の要素はnが偶数のときのもの
ここでf(n)=3n+3という関数を用意する。
@のとき
kを、0≦kを満たす整数とし、n=2k+1とすると、f(k)=6k+6
Aのとき
kを、0≦kを満たす整数とし、n=2kとすると、f(k)=6k+3
(※)に戻る
kはnと同じく0以上の整数なので、初期値を6で割ったあまりさえ求まれば、操作中の具体的な値は不明でも、初期値がその後どういう振る舞いをするかのシーケンスはわかる。
そのシーケンスの一部に
集合6n+1「3をかけられて1を足されて」→集合18n+4「2で割られて」→集合9n+2(集合3n+2)「3n+2が偶数のとき」→集合6k+2「2で割られて」→集合3k+1「3k+1が偶数のとき」→集合6l+1
という循環が存在する。
これはn=k=l=0のとき1→4→2→1ループを意味する。
他に循環があるのかはわからないし、コラッツ問題が解けたわけでもないけれど面白いと思ったからスレ立てしてみた。 >>2
コラッツは5パターンのループが存在する
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
どの整数からスタートしても上記の5つのループいずれかに必ず到達する 他にも初めと同じ集合に戻ってくるような循環があるかどうか調べてみてほしい。
例えば集合6n+4「2で割られて」→集合3n+2「3n+2が偶数のとき」→集合6k+2「2で割られて」→集合3k+1「これが偶数のとき」→集合6l+4
っていう循環を考えられるけど、この循環はずっと2で割り続けることから、このループの初期値は2×2×2×…ということがわかる。 >>3この説明のnを整数全体に拡張すれば答えられるよ。
0→0
0は6で割ったあまり0だから集合6n+6の要素(n=-1のとき、6n+6=0)
初期値が集合6n+6に含まれる要素なときの循環の一つ
集合6n+6「2で割られて」→集合3n+3「3n+3が偶数のとき」→集合6k+6
これが0→0のループ
-1→-2→-1
-1は6で割ったあまりが5だから集合6n+5の要素(n=-1のとき、6n+5=-1)
初期値が集合6n+5に含まれる要素なときの循環の一つ
集合6n+5「3をかけられて1を足されて」→集合18n+16「2で割られて」→集合9n+8(3n+2)→集合3n+2「3n+2奇数のとき」→集合6k+5
これが-1→-2→-1のループ
下の二つは長いから自分でやってくれー
文字の数がどんどん増えてくけどまあ足りるやろう なんかこの説明に則ると循環をいくらでも作れてしまうな
コラッツ予想は間違いなのでは?笑 ちなみに>>5は初期値-2にしても結局同じループに入るよ >>4の最後2×2×2×…って書いたけどこれ間違いだ
「初期値は2×2×2×…を因数に持つ整数」が正しい
ごめんね 任意の正の整数な
任意の正の整数 n に対して、以下で定められる操作について考える。
n が偶数の場合、n を 2 で割る
n が奇数の場合、n に 3 をかけて 1 を足す
このとき、「どんな初期値から始めても、有限回の操作のうちに必ず 1 に到達する(そして 1→4→2→1 というループに入る)」という主張が、コラッツの予想である。 任意の正の奇数に3倍して1を足す
nを0以上の整数として
正の奇数を2n+1と表す
これを3倍して6n+3
1を足して6n+4
これは正しい? 整数全体を一括して示すのは難しいからまず任意の奇数について考えるよ 任意の奇数はコラッツ予想の操作で3倍して1足される
そうすると必ず6n+4で表せる形になる。 これは常に偶数だから次に2で割られる
4、10、16、22…ってのは2で割られると2、5、8、11…
ってなるけどこれは3で割ったら2余る数の集まり。
よって3n+2で表せる >>13の図に戻るんだけど奇数は左側、偶数は右側に寄せてる。
奇数かつ3で割った余りが2になる奴らは6n+5で表せるとかそういう感じ 図の左側にいる奴らは必ず6n+4の部分を経由して3n+2の左右いずれかの部分(6n+5か6n+2)に移る
ただこのとき左側に移っても右側に移るまでは同じことの繰り返しになる この経過を数式で表記するのが不可能なんだよね
nが奇数のときで場合分けし続けることになるから。
この無限ループが図のおかげで省略できる んで>>18の続き
左側は説明したから次右側。
右側(6n+2)に移ったときこれ偶数だから2で割られて3n+1の左右(6n+1と6n+4)のいずれかに移る
2、8、14、20…を2で割ると1、4、7、10…
これまた左側の場合は>>18と同様。 まだ出てきてない6n+6について特別に説明して終わり
これ偶数だから2で割られて3n+3
6、12、18、24…が2で割られて3、6、9、12…
結果奇数になったら前述したループに入って、偶数になったら奇数になるまで2で割られ続ける。
3×2の無限積とかだったら2で割り続けるループに入るというのが気がかり。
初期値が任意の正の整数っていうことならそんなんもありになっちゃうけど、これ許すとしたらコラッツ予想は成り立たないよねっていう つーことで任意の偶数は2で割り続けると奇数になるっていう前提が欲しいんだけど認めていいのかな んでそれぞれの移行パターンを網羅した図https://imgur.com/a/hojluvL
この矢印に沿って作れるループのうち実現可能なものが6n+4→6n+2→6n+1→しかないことを示せれば勝ち >>11
全部見た!ありがとう!
やっぱりそういうことだったのか
自分の方にも落としこんでみる
俺はループ否定派なので ループを構成する場合どのように構成したとしても必ず
@6n+4→ 6n+2→ 6n+1→ 6n+4
A6n+4→ 6n+2→ 6n+4
B6n+4→ 6n+5→ 6n+4
これらのいずれかをパーツとして含む
@は結局4で割ったあと3かけて1足してる
A4で割ってる
Bは2で割って3をかけて1足してる
@ABを組み合わせて作るループについて考える >>25
予想が肯定されるか否定されるかは最後にわかることだからどちらかの立場に立って推論するのは危険だと思うけど… @の操作は4よりも大きい値に対して操作を行う前より後の方が値が小さくなる
Aは当然操作を行う前よりも後の方が小さい
Bは前よりも後の方が大きい 任意の整数についてコラッツ予想が成り立つためには、初期値がどんなに大きな整数でも最終的に値は小さくなっていく必要がある
Bの値を大きくする力と、@Aを合わせた値を小さくする力との間に不均衡がなきゃそれは起きない
ここを調べる必要があるね 奇数*2^(偶数)と奇数*2^(奇数)
とに偶数を二分しようか
こうすることでAが繰り返されたあと、2の肩が偶数だったら@、奇数だったらBに分岐させられる あとは奇数の中で3かけて1足すと奇数*2^(偶数)で表されるやつ、奇数*2^(奇数) の形で表されるやつの具体的な式がわかればいいんだが 簡単だった
12n+4で表されるやつらは奇数*2^(偶数)で表されるやつ、12n+10が奇数*2^(奇数) で表されるやつらだな んーいや、奇数に3かけて1足すと絶対6n+4で表せる数になるから、>>33で合ってるのか >>33の二つは偶数になる前奇数だったやつ。
コラッツの逆操作をして値を求める。1引いて3で割ると12n+4は4n+1,12n+10は4n+3 4n+1で表される奇数はコラッツの操作を受けて奇数*2^(偶数)で表される偶数になる
4n+3で表される奇数はコラッツの操作を受けて偶数*2^(奇数)で表される偶数になると 4の倍数でない2の倍数と、4の倍数って分け方の方がわかりやすいかな 集合がぴったり一致するわけではないから、等号で結べないのがな…
⊃でしか評価できん 4n+1で表される奇数はコラッツの操作を受けて12k+4となり、これは(x,y)=(奇数,偶数)としてx*2^yで表される偶数に含まれる
4n+3で表される奇数はコラッツの操作を受けて12k+10となり、これは(x,y)=(奇数,奇数)としてx*2^yで表される偶数に含まれる
うーん
操作の前後の集合は全単射だけど、その次は単射だけど全射じゃないねんな… {n}={0,1,2,…}
こんな感じにして、4n+1なら
{4n}={0,4,8,…}
{4n+1}={1,5,9,…}
というような表記を認めることとしよう {4n+1}で表される奇数はコラッツの操作を受けて
{12n+3}={3,15,27…}
{12n+4}={4,16,28…}となる。
んーあれ。>>43ふつーに間違えてる ひとまず12n+4は4(3n+1)だし、12n+10は2(6n+5)だし、{n}={0,1,2,…} のとき6n+5は常に奇数だから前者は4で割れて後者は4では割れないことは確かか 前者は3n+1が奇数になる場合と4の倍数でない2の倍数になる場合と4の倍数になる場合とで場合わけだなー 3の倍数に1足したとき、4の倍数になるときとならないときとでなんか規則性ないもんかねー
4、7、10、13、16、19、22、25、28、31、34、37、40
三個飛びで4の倍数が現れてんな 4の倍数、奇数、4の倍数でない2の倍数、奇数→最初に戻るっていう循環だなーこれ {6n+5}={5,11,17…}はnの偶奇次第で{4n+1}か{4n+3}に分類されるのかー {4n+3}に入ってる奴らは奇数の操作をされた後一回だけ2で割られて{6n+5}の中に入るわけだなー {4n+3}={3,7,11,15,19,23,27,31,35…}
{6n+5}={5,11,17,23,29,35…}
これ微妙に重なってるなー
重なってない部分は常に個数の比率が上:下=2:1になってるな 図はできたけど論理的に正しいよう書き表すには平面じゃ足りないわ 図が酷いことになった
https://imgur.com/a/mioxBvI
やっぱ値の軌跡を追おうとすると集合がどんどん分割されて行く
そのつど分岐先が増えるから、経路を固定するために分岐点の集合を分割しないといけなくなって無限ループに陥る やっぱnを偶数だったり奇数だったりする量子ビット的な不確定の何かとして計算できなきゃ色々無理だ
nが片方の場合ともう片方の場合とを同時に取り得るってことを認めなきゃこの手法では証明できんね
自分でも何言ってるのかよくわからないけどそんな言葉が導き出されたよ >>58の現象を数学的帰納法ばりに一般化させて、公比1/2の等比級数の面積表現みたいに集合が分割されながら自然数全体を満たしていくような形で書き下せたら勝ちなんだけどなあ ■ このスレッドは過去ログ倉庫に格納されています