コラッツ予想がとけたらいいな その2
■ このスレッドは過去ログ倉庫に格納されています
字下げされているデータは、上からｎ番目にあると第三項もnになる
という法則はありそうなきがする >>581
あ、それはコラッツ展開のビットを1から順番に並べているので、
コラッツ展開と初期値が一致するなら、当然そうなると思われます。 >>573-580
色々とすみませんでした。
プログラムの説明不足でした。 どうでもいいことだけど、いま私のメインマシンが壊れていて
古いノートPC（32bit OS)使ってます。
githubにあげてもらったexeは64bit版ですかね？動きませんでした。
私はソースのほう使ってるのでそれでも大丈夫ですが。 ・コラッツ展開の表記は元のまま。縦の並び順だけを変えている。
・2進数表記は反転させている。
という状態みたいですね。
2進数表記を変えると混乱を招きそうなので
コラッツ展開の方を反転させた方がいいかも？。
つまり
("0000000000","0000000000",1024)
("0000000001","0101010101",341)
("0000000010","1010101010",682)
("0000000011","0011100011",227)
("0000000100","0101010100",340)
：
：
と出力させる感じで。 |
＼ __ ／
＿ （ｍ） ＿ﾋﾟｺｰﾝ
|ミ|
／ ｀´ ＼
('A`)
ノヽノヽ
くく コラッツ展開の一部が、コラッツ値の2進表示下位nビットと一致するなら、
「コラッツ展開の一部を2進数で覆う」と言う事にします。
例を挙げます。
9',14,7',11,17,26',13,20',10,5,8,4',2,1,...
1' 0 1' 1 1 0' 1 0' 0 1 0 0' 0 1
9'
1' 0 （0 1） 2進
7'
1' 1 1 2進
26'
0' 1 （0 1 1） 2進
20'
0' 0 1 0 （1） 2進
4'
0' 0 1 2進
繋げると1' 0 1' 1 1 0' 1 0' 0 1 0 0' 0 1になります。
この後の0,1の繰り返しは2の2進数01で覆えます。 そして、
「コラッツ展開を、下位2ビット以上の2進数の連結で覆い尽くせる」→「コラッツ操作で1に辿り着く」
が言えれば良いと思うのです。 どういう操作をしてるかはなんとなく分かりましたけど、
なんかNGワードがあるとかで書き込めないので画像にて失礼。
https://i.imgur.com/uYeyPKq.png
そこからの>>1さんの主張は私もはっきりとはわかりませんが、
「常に 2 ビット以上覆う」ということを利用してコラッツ予想を証明できないか、みたいな感じでしょうか。 >>590
そうです、こんな感じです。
（確かに26は3ビット覆えますね） 登って下がってというループで山が四つくらいまでのループは無いらしいが、この方面では難しそうだ
Zudilin あたりが書いた 超越数の≪(3/2)^n≫ あたりからなんか言えんかね
ABC が絡むような話もどこかにあったような気がするのは気がふれたみたいだからさようなら ちょっと思い出話でも。
自分がスレを立てる前のコラッツスレに、
「割数列」というものがありました。
コラッツ操作で2で割った回数を並べます。
これを割数列と名付けます。
例えば9の場合は、コラッツ列は
9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
ですから割数列は
[2,1,1,2,3,4]
となります。
初期値が3の倍数の割数列を完全割数列と名付けます。
（コラッツ予想は3の倍数だけ調べれば良いのは周知です）
9[2,1,1,2,3,4]は完全割数列です。
7[1,1,2,3,4]はふつうの割数列です。 star変換というものがありました。
（名前は勝手に僕がつけました）
長さｎの完全割数列→長さｎ＋１の完全割数列
まず、長さｎの完全割数列を、初項に０をつけたｎ＋１型で表す。
長さｎの完全割数列でできる最終値を９で割ったあまりが・・
３ ・・ A:[6,-4]orB:[1,-2]をつける
６ ・・ C:[4,-4]orD:[3,-2]をつける
０ ・・ E:[2,-4]orF:[5,-2]をつける
元の初項が負になる場合はあらかじめG:[+6]をおこなう。
例
21≡3(mod 9) 21[0,6]
このとき、21[6,6-4]と3[1,6-2]が存在する。 いやあ、懐かしいですねぇ
ちなみに割数列とコラッツ展開は密接に関係しています。
実はコラッツ展開は、割数列から派生して得られたものだったりします。
例えば 9 のコラッツ展開は
1,0,1,1,1,0,1,0,0,1,0,0,0,1,…
ですが、このとき 1 が現れてから次の 1 が現れるまでの項数を見ていくと
2,1,1,2,3,4
となり、これが割数列に一致します。 >>597
前スレで、「全てのstar変換後の完全割数列は、全ての3の倍数の奇数を尽くす」事を証明しました。
しかし、後ろに無限に長く、base caseである21[6]にたどり着かない
完全割数列を排除できなくて、その時は挫折しました。 star変換後に、割数列の要素が0や負になる事は禁止していますが、
これを認めたらどうなるでしょうか。
2つほど試してみます。
9[2,1,1,2,3,4]
↓ F[5,-2] y=8x/3-3
21[5,0,1,1,2,3,4]
・確認の計算
割数列を逆から辿る。4->3->2->1->1まででコラッツ値は7だから
(7*2^0-1)/3 = 2
(2*2^5-1)/3 = 21 辻褄は合ってます
15[1,1,1,5,4]
↓ C[4,-4] y=x/3-2
3[4,-3,1,1,5,4]
・確認の計算
割数列を逆から辿る。4->5->1->1まででコラッツ値は23だから
(23*2^-3-1)/3 = 5/8
((5/8)*2^4-1)/3 = 3 辻褄は合ってます
どちらも、コラッツのルールからは外れるけれども、
(3x+1)/2^pの計算自体は出来ているようです。 全ての場合でうまくいく訳ではありません。
star変換それぞれについて見てみます。
・3 mod 9
A[6,-4] y=4x/3-7 x=3+9t ⇒ y=3(4t-1) t=0は禁止する
B[1,-2] y=x/6-1/2 x=3+9t ⇒ y=3t/2 t:奇数は禁止する
・6 mod 9
C[4,-4] y=x/3-2 x=6+9t ⇒ y=3t t=0は禁止する
D[3,-2] y=2x/3-1 x=6+9t ⇒ y=3(2t+1) オールオッケー
・0 mod 9
E[2,-4] y=x/12-3/4 x=9t ⇒ y=(3/4)(t-1)
t-1が4の倍数でない時禁止する
F[5,-2] y=8x/3-3 x=9t ⇒ y=3(8t-1) オールオッケー
変換後のコラッツ値が、0や負や分数になるものを禁止すれば、
この変換は、3の倍数から3の倍数に写ります。
これで得られる割数列を「拡張完全割数列」「拡張コラッツ予想」と呼ぶ事にします。 拡張完全割数列のうちで、後ろに無限に長く、base caseである21[6]にたどり着かない、
最小反例を考えます。
この割数列にstar変換を施したものも、後ろの方は変わっていないので、反例です。
この反例が最小反例よりも小さければ、矛盾を引き出すことができます。
こういう目論見です。 考えていた物と別の証明が浮かんだので、そっちを書きます。
>>603の最小反例に、コラッツ値が偶数のものはありません。
2で割るとさらに小さくなるからです。
ということは、拡張完全割数列でコラッツ値が偶数のものは有限項です。
これに、star変換を逆に施した、普通の完全割数列も有限項（1に辿り着く）ということです。 普通の完全割数列に、star変換を施して、変換後のコラッツ値が偶数になるものを見てみましょう。
・3 mod 9
各star変換 変換関数 返還前 変換後
A[6,-4] y=4x/3-7 x=3+18t ⇒ y=24t-3 偶数はない
B[1,-2] y=x/6-1/2 x=3+18t ⇒ y=3t t:偶数でyは偶数 ⇒ x=36t+3は有限項
・6 mod 9
C[4,-4] y=x/3-2 x=15+18t ⇒ y=6t+3 偶数はない
D[3,-2] y=2x/3-1 x=15+18t ⇒ y=12t+9 偶数はない
・0 mod 9
E[2,-4] y=x/12-3/4 x=9+18t ⇒ y=(3/2)t t:4の倍数でyは偶数 ⇒ x=72t+9は有限項
F[5,-2] y=8x/3-3 x=9+18t ⇒ y=48t+21 偶数はない コラッツ値x=36t+3とx=72t+9は1にたどり着く事が分かりました。
（3と9は手計算で、ということにしましょう）
ここで思ったのですが、このパターン、剰余コラッツ予想で解かれてなかったっけ！？
>>4
＞前スレ>>786の予想は、以下の場合に証明できています。
＞・n は 83 以下の奇数, k は任意
36は81に帰着されるので有効、
72は243なので今のところout 偶数は「最小でない反例」の可能性があるのですね。
失礼しました。
>>604-606は無しでお願いします。 >>603を証明します。
拡張完全割数列のうちで、後ろに無限に長く、base caseである21[6]にたどり着かない、
最小反例cを考えます。
「cは奇数」であり、「c≠3」「c≠9」とします。
「c≡3 mod 9」「c≡6 mod 9」「c≡0 mod 9」で場合分けをします。
・c≡3 mod 9のとき
star変換B[1,-2]をおこないます。変換関数はy=c/6-1/2
入力は
c=9t+3 (t≦0) から始めて
cは奇数なので c=18t'+3 (t'≦0)
cは3ではないので c=18t'' +21 (t''≦0)
変換関数に代入すると
y=3t'' +3 < c より小さい反例が得られました。
・c≡6 mod 9のとき
star変換D[3,-2]をおこないます。変換関数はy=(2/3)c-1
入力は
c=9t+6 (t≦0) から始めて
cは奇数なので c=18t'+15 (t'≦0)
変換関数に代入すると
y=12t' +9 < c より小さい反例が得られました。 ・c≡0 mod 9のとき
star変換E[2,-4]をおこなうと、分数になる場合があります。
なので入力を分割します。
c=9t+9 (t≦0) を
c1=36t'+9 (t'≦0) 9を除いて36t'' +45 (t''≦0)
c2=36t'+18 (t'≦0) 偶数なので除外
c3=36t'+27 (t'≦0)
c4=36t'+36 (t'≦0) 偶数なので除外
・c1のときはE[2,-4]をおこなう
y=c1/12-3/4 = 3t'' +3 < c1 より小さい反例が得られました。
・c3のときは、以下をそれぞれF後のmod9に応じておこないます。
F → C (1/3)((8/3)c3-3)-2 = (8/9)c3 -3 < c3
F → B (1/6)((8/3)c3-3)-1/2 = (4/9)c3 -1 < c3
F → E (1/12)((8/3)c3-3)-3/4 = (2/9)c3 -1 < c3
どの場合も、より小さい反例が得られました。
なお、F → Eのときは循環する可能性がありますが、
y=(8/3)(27+36t')-3 = 72+96t'-3 = 27+ 42+96t'
42+96t' = 36t'' とおくと、一次不定方程式になりますが、
42はgcd(96, 36)=12 の倍数ではないので、この式は整数解を持ちません。
よって、27+36t' ―F→ 27+36t'' になることはありません。
いずれの場合も、より小さい反例が得られたので、
最小反例cは存在しません。 拡張完全割数列に対して、無限項のものがないと分かりました。
よって、全ての項が正である、通常の完全割数列に限定しても、無限項のものはありません。
以上より、全ての3の倍数の奇数は、1に辿り着くことが言えました。 えっ
ちょい待ち
全ての6n-3が1を含む枝に属する事が証明できた？
コラッツ予想の証明完了じゃん >>608で、c=18t''+21 から y=3t''+3 への変換で
対応する割数列の変換が本当に B[1,-2] になってるかが怪しいような。 >>614
c=18t''+21 ーB[1,-2]→ y=3t''+3 を
先頭5個を手計算してみました。
21[0,6] → 3[1,4]
39[0,1,1,2,1,... → 6[1,-1,1,2,...
57[0,2,1,2,2,... → 9[1,0,1,2,...
75[0,1,2,8] → 12[1,-1,2,8]
93[0,3,1,5,4] → 15[1,1,1,5,4]
ひとまずうまくいっているようです。 c≡0 mod 9のときに不備がありそうです。
調査します。 0 や負の項を許しているのを失念していました。
ただそうすると、一つの数に対して複数の数列が対応することになります。
c=18t''+21 の割数列に変換 B[1,-2] を施すと、y=3t''+3 の拡張完全割数列の一つが得られますが、
それは y=3t''+3 の通常の割数列と同じとは限らず、通常の割数列が無限に長いとは言い切れない、
すなわち反例になっているとは言い切れないと思います。 せっかく解けない問題があるんだから、何かに使えないんでしょうか
数独のようなパズルを作る
乱数を作る
暗号システムを作る >>617
入力も拡張完全割数列にすればどうでしょう。
図を書いてみました。
https://github.com/righ1113/CollatzMod/blob/master/picture/divSeq_logic.jpg
反例を、
「ある3の倍数のコラッツ値を表す、拡張完全割数列の少なくとも一つが無限項である」
と定義します。これならどうでしょうか。 最小反例が 3 である可能性がありますね。
その場合、コラッツ値をより小さくすることはできず、矛盾は生じません。 そうですねぇ、だめですね……
ありがとうございました。 レベルというものを導入します。
6x+3のコラッツ値で、全ての項が正の完全割数列のみがあらわす
ものを、レベル0のコラッツ値とします。
レベル0のコラッツ値と、全ての項が正の完全割数列は、
1対1対応しています。
レベル0のコラッツ値を、0,負も認めたstar変換を1,2,3回施した
ものを、レベル1のコラッツ値とします。
レベル1のコラッツ値で、最小反例が無い事を証明します。
・レベル1のコラッツ値3が最小反例でない事
3から、star変換を逆に施していきます。
それぞれ、1,2,3回逆に施したところで、レベル0に戻るので、
1対1対応した割数列を割り当てます。
有限個の割数列が得られるので、1つ1つ有限項か計算すれば良いです。 プログラムを使って説明します。
コラッツ値をあらわす割数列を列挙する関数allDivSeqを考えます。
第一引数は、コラッツ値です。
第二引数は、star変換を施した回数です。
allDivSeq 3 1を例にとって説明します。
star変換を1回施して、コラッツ値が3になるものを考えて、
allDivSeq 3 1
= B[1,-2] ++ allDivSeq 21 0
, C[4,-4] ++ allDivSeq 15 0
, D[3,-2] ++ allDivSeq 6 0
, E[2,-4] ++ allDivSeq 45 0
と再帰的に表せます。
第二引数が0になった所で、そのコラッツ値があらわす、
全ての項が正の完全割数列を当てはめます。偶数は無視します。
allDivSeq 3 1
= B[1,-2] ++ [6]
, C[4,-4] ++ [1,1,1,5,4]
, D[3,-2] ++ Nothing
, E[2,-4] ++ [3,2,3,4]
と、有限項の割数列で列挙できました。 レベル1のコラッツ値3x+3に、最小反例が存在しない事を証明します。
3と9はallDivSeqを使って、
残りの数は、>>608-609を手直ししたものを使います。 3の倍数に0も含めることにします。
3も9もstar変換で0になって、小さくなるのでOKとします。
レベル1のコラッツ値3xに、最小反例が存在しない事を証明します。（後日）
0はallDivSeqを使って、
残りの数は、>>608-609を手直ししたものを使います。 見直しというか、証明の形式化にチャレンジしています。
Idrisというマニアックな言語を使っています。Coqみたいな事ができます。
型を合わせるのがめんど……いや、難しいですね。 場合分けが尽くせてないですが、Ver0.1をリリースします。
https://github.com/righ1113/collatzProof_DivSeq
最終的な定理はProofColDivSeqMain.idrにあって、以下です。
allDivSeqInfFalse : (n:Nat)
-> any unLimited (allDivSeq (n+n+n) 0) = False
これは、3の倍数の奇数の完全割数列が全て、有限項である（1に辿り着く）
事を示しています。 数学の60年来の難問を、「不老不死研究」の生物医学者がこうして解き明かした
https://wired.jp/2018/08/02/a-decades-old-math-problem/
押しても引いてもだめなら、まったく違う方面からのほうがいいのかもね >>637
はー、なるほど。分かったような、分からないような。 一つ注意点があります。
プログラムでの証明中に、postulate（無条件の仮定）を使っています。
なので、完全な形式化という訳ではないです。
postulateな命題については、紙の上で証明すれば良いと考えています。 なにげに結構なボリュームあるな
普通にすごいわ
内容的にただしいのか俺の実力じゃジャッジできないけど DIR EN GREYのアルバムを買った。
これを聴いて証明を頑張ろう。 紙の証明 第二部が作成完了しました。
良かったら見てみて下さい。
第2部 レベル0のallDivSeqは、全て有限項 （これが言えればコラッツ予想も真）
https://github.com/righ1113/collatzProof_DivSeq/wiki 正直、１０００万円くらいの懸賞かかっててもいいと思うけどね そうですよね。100万でも「おおっ」ってなります。 懸賞かかってなくてもコラッツとけたら年収１０００万の職につけないかなぁ？ 証明は出来たのですか？
完全に素人質問で悪いのですが、証明の全容をここに載せたら盗まれる可能性があるのではないでしょうか？
arXivに上げるなどして正式に発表したほうがいいのでは…と思ってしまいます。 >>654
ありがとうございます。
証明はほぼ完成しています。
https://github.com/righ1113/collatzProof_DivSeq
arXivに投稿するには、endorser裏書人が必要なので、難しいかなと思っています。 >>655
そのページは情報が欠けていて論理を追うことができません。 ／￣`Y ￣ヽ､
/ / / / l | | lヽヽ
/ / // ⌒ ⌒ヽ
| | |/ （●） （●）
（Ｓ|| | ⌒ ･ｨ ヽ 芸能人が吹き替えに挑戦というのは
| || | ﾄ-＝-ｧ ﾉ
| || | |-ｒ ､/ /|
| || | ＼＿｀ﾆ'_／ |
(( ( つ ヽつ、
. 〉 i ))
（__ノ^（＿）
／￣`Y ￣ヽ､
/ / / / l | | lヽヽ
/ / // ⌒ ⌒ヽ
| | |/ （●） （●）
（Ｓ|| | ⌒ ･ｨ ヽ 許せないという気持ちが分かる
| || | ﾄ-＝-ｧ ﾉ
| || | |-ｒ ､/ /|
| || | ＼＿｀ﾆ'_／ |
⊂/ ⊂ ）
i ヽ
(( （＿）^ヽ.__） )) 👀
Rock54: Caution(BBR-MD5:1341adc37120578f18dba9451e6c8c3b) この証明の鍵は、star変換によってコラッツ列の無限性を維持しつつ元の整数を小さくできるとする主張にあります。
しかし変換の定義から そのようなことが常に可能とは思えない というのが私の直感です。
まず確認ですが、star変換によって割数列に負の項が出てくることを許しているわけではない ですよね？
各chapterを一読しましたが、『計算上は合う』というコメントもあり判然としません。
プログラムを読めば分かるのかもしれませんが素人なのでお許しを。
［chapter3より引用］
> 変換後のコラッツ値が、負数や分数になるものを禁止すれば、
> この変換は、3の倍数から3の倍数に写ります。
> これで得られる割数列を 「拡張完全割数列」 と呼ぶ事にします。
割数列の定義から負の項は存在できません。
たとえ最終計算が合っていたとしても、2を掛ける操作はコラッツ列の生成ルールにはありませんから、
負の項が出現するような変換は許されません。『拡張列』としてそれを 考えるだけ なら構いませんが、
拡張列から元の整数を復元する操作を統一的に行うことは許されないはずです。 >>658
詳細なコメントありがとうございます。
すぐには答えられないので、じっくり考えてみます。 例を挙げておきます。
[Chapter7より]
> コラッツ値がcである無限項の割数列を仮定して、コラッツ値が小さくなるようなstar変換を施します。
ここで筆者は、0（mod9）である36t＋9なる整数に対しE[2，-4］（y＝x/12−3/4）を施すと変換後は3t＜36t＋9になると主張する。
t＝1とすれば、36t＋9の割数列は[3，2，3，4］であり、E[2，-4]をそのまま施すと[2，-1，2，3，4］となり負の項が現れる。
この第2項『-1』を『2を掛ける操作』と解釈すれば、[2，-1，2，3，4］が表す整数は確かに3tになる。
しかしコラッツのルールに『2を掛ける操作』は存在しないので、本問題でそのような解釈はできない（※）。
3tに対応する割数列はコラッツのルールで一意に決まる[1，4］であり[2，-1，2，3，4］ではない。
コラッツのルールに則れば、
『負の項を持つ割数列に対応する整数は存在しない』
としか言えない。
（※）
負の項を持ちうる拡張割数列を元の整数に対応づける解釈を行うことは
・2で割る、2を掛ける、3を掛けて1を足すという3つの操作を別のルールに則って行う。
・各操作後の値は整数とは限らない。
このような拡張されたコラッツ問題を考えることに相当する。
その拡張されたルールを前提とすれば、[1，4]と[2，-1，2，3，4］は共に3tに対応する。
言えるのはこれだけのように思える。 そもそもcoq使うなら全部coqにしなきゃ意味ないと思うが >>658,660
以下3つをおこなえば良いのではないかと考えています。
◆定義1 拡張コラッツ予想
6t+3（t≦0）を用意する。（ここからコラッツ操作すれば通常のコラッツ予想になる）
一度コラッツ操作を施したものをαとおく。
6t+3から1~3回star変換をおこなう。
そこから拡張コラッツ操作をおこなう。αに戻ったところで通常のコラッツ操作に切り替える。
これを拡張コラッツ予想と名付ける。
※拡張コラッツ操作
コラッツ値xに対し、(3x+1)/2^pを施す。pは割数列の初項（0や負も取りうる）。
◆定理1
あるコラッツ値（一度コラッツ操作したものをα）からstar変換したものを、
2回拡張コラッツ操作すると、αに戻る
◆定理2
拡張コラッツ予想が真 ⇒ コラッツ予想も真 ◆定理1
あるコラッツ値（一度コラッツ操作したものをα）からstar変換したものを、
2回拡張コラッツ操作すると、αに戻る
・1つのパターン
x=9t+3 [3, *,...]
を1回コラッツ操作すると、(3(9t+3)+1)/8 = (27t+10)/8 になります。
xに A[6,-4] y=(4/3)x-7 でstar変換すると
12t-3 [6, -1, *,...] になります。
拡張コラッツ操作1回目で (3(12t-3)+1)/2^6 = (9t-2)/2^4
拡張コラッツ操作2回目で (3((9t-2)/2^4)+1)2
= (27t+10)/8 になって二つは一致します。
残りはGitHubでやります。 ◆定理2
拡張コラッツ予想が真 ⇒ コラッツ予想も真
star変換したものから拡張コラッツ操作を繰り返すと、
定理1より、全ての6t+3から遷移するαと同じものが、
欠けることなく得られます。
よって、拡張コラッツ予想が真ならば、
後方を共有する、通常のコラッツ予想も真になります。 >>664-666
その方針でこの問題が簡単化されるとは思いませんが。
righ1113さんの腕の見せ所ですね。
がんばってください。 自然数xに対してコラッツ展開に似た数列collatz_array(x)を次のようなrubyプログラムで定義する。
def collatz_array(x)
if(x==1)
then
return []
elsif(x%2==0)
return [0]+col(x/2)
else
return [1]+col((x*3+1)/2)
end
end
collaz_array(x)をビット列とみなして2進数の整数に直したものをcollatz_number(x)とする。
collatz_numberはrubyプログラムで次のように定義される。
def collatz_number(x)
res=0;
x.each_with_index{|v,i|res+=v*(2**i)}
return res
end
3の倍数でない、かつx==collatz_number(x)となるような自然数xは存在するか？ ちょっと言ってることがおかしいかもしれない。
ようするにコラッツ展開に対する不動点みたいなものはあるか？という話をしたいのだが 朝の6時にスレチェックかよｗすげえｗ
まあ俺も人のこと言えないけどｗお疲れ様です。 新たな不動点が見つかったら新たなループが見つかるみたいな方向に持っていけたらベストなんだけど。
まあまだぼんやりしたイメージがあるだけです。 うーん、collatz_arrayの停止条件がx==1だとあんまり意味のない議論になってしまうかもしれないorz x==collatz_number(x)をチェックすると
3*2^tは該当するみたい。そりゃそうか。
あと、「先頭nビットが一致する」だと意味ないかな？ >>679
意味ないかどうかはまだわかりませんが、先頭nビットについては>>528のような割とはっきりした規則性があるようなので、
規則性の見えなくなる後ろのほうのビットのふるまいを何とかできないかという思いはあります。 ■ このスレッドは過去ログ倉庫に格納されています
