コラッツ予想がとけたらいいな　その2

コラッツ予想がとけた ..

563:前786
18/07/28 22:40:43.24 wb0cTFEt.net
あまり期待はしないで下さいな。
出力の並び順ですが、
00000
10000
01000
11000
:
:
のようにしてもいいかもしれません。可能ならば。
>>546で言ったようにコラッツ展開を2進展開の類似物と捉えると、
コラッツ展開の初項が一の位に対応するので。
もしくは2進展開にならってコラッツ展開も右から左に書くことにするとか。

564:１３２人目の素数さん
18/07/28 23:51:31.58 7NxoS75W.net
確かに左右反転してるのが結構ありますねぇ…

565:M.B.
18/07/29 00:20:38.47 sLBYc3Xd.net
ぜんぜん関係のない話なんで、スレ汚しスマン。
以前、原始ピタゴラス数の絡みで、直角二等辺三角形に
収束する数列を、スターン＝ブロコット木の上で追いかけていたら、
そこにフィボナッチ数列が出てきたことがある。
どういう境界条件で左右反転が起きるのかは、追いかけてみたら
面白そうな気がする。
（私が面白そうな気がするだけで、結果についてはいっさい責任は
取らないということは、いうまでもないが）

566:１３２人目の素数さん
18/07/29 01:01:26.47 apdazvkC.net
桁数：左右反転している個数
1: 2
2: 4
3: 6
4: 10
5: 16
6: 22
7: 30
8: 44
9: 58
10: 68
11: 80
12: 96
13: 122
14: 144
15: 162
16: 182
17: 200
18: 212
19: 228
20: 254

567:１３２人目の素数さん
18/07/29 01:05:24.07 apdazvkC.net
割合的には急激に減る
桁数をnとすると、n*log nくらいのオーダーか？

568:１３２人目の素数さん
18/07/29 01:06:53.56 oePH1MMB.net
さらに>>１にお願いしたいが
入力ｎに対して丁度nビットの01列とそれに対応するコラッツ展開をもつ2^n以下の自然数を列挙
コラッツ展開と自然数を２進であらわしたものが反転してる関係にあるものは行頭に空白４個入れる
反転ではないものは行頭に空白を入れずに表示
でプログラムお願いできない？

569:１３２人目の素数さん
18/07/29 01:14:15.62 apdazvkC.net
左右反転になるもの
1 [0, 1]
2 [0, 1, 2, 3]
3 [0, 2, 3, 4, 6, 7]
4 [0, 3, 4, 6, 7, 8, 11, 12, 14, 15]
5 [0, 3, 6, 8, 11, 12, 14, 15, 16, 19, 22, 24, 27, 28, 30, 31]
6 [0, 6, 11, 12, 15, 16, 22, 24, 28, 30, 31, 32, 38, 43, 44, 47, 48, 54, 56, 60, 62, 63]
7 [0, 12, 15, 22, 24, 30, 32, 43, 44, 47, 48, 56, 60, 62, 63, 64, 76, 79, 86, 88, 94, 96, 107, 108, 111, 112, 120, 124, 126, 127]
8 [0, 15, 24, 30, 43, 44, 48, 60, 63, 64, 79, 86, 88, 94, 96, 107, 111, 112, 120, 124, 126, 127, 128, 143, 152, 158, 171, 172, 176, 188, 191, 192, 207, 214, 216, 222, 224, 235, 239, 240, 248, 252, 254, 255]
9 [0, 30, 43, 48, 60, 63, 79, 86, 88, 96, 120, 126, 128, 158, 171, 172, 176, 188, 191, 192, 214, 222, 224, 235, 240, 248, 252, 254, 255, 256, 286,
299, 304, 316, 319, 335, 342, 344, 352, 376, 382, 384, 414, 427, 428, 432, 444, 447, 448, 470, 478, 480, 491, 496, 504, 508, 510, 511]
10 [0, 60, 79, 86, 96, 120, 126, 158, 171, 172, 176, 191, 192, 240, 252, 255, 256, 316, 342, 344, 352, 376, 382, 384, 428, 444, 448, 470, 480, 496,
504, 508, 510, 511, 512, 572, 591, 598, 608, 632, 638, 670, 683, 684, 688, 703, 704, 752, 764, 767, 768, 828, 854, 856, 864, 888, 894, 896,
940, 956, 960, 982, 992, 1008, 1016, 1020, 1022, 1023]

570:前786
18/07/29 12:59:45.00 sVL1UhWV.net
左右反転については考えたことは無かったですね。
とりあえず偶数は奇数に帰着されるので、奇数だけ見るのがいいような気がします。

571:righ1113
18/07/29 14:30:52.71 z6BL7vg2.net
>>568
>>563の案についてはどうしましょうか？
ビット列を左から書くようにすると、
ビット列とコラッツ展開が『左右反転している』　→　『同一である』
になって分かりやすいと思うのですが。

572:566
18/07/29 14:59:40.32 QwhF8wXZ.net
>>571
じゃあ採用してみましょうか
お願いします

573:righ1113
18/07/29 16:26:02.64 z6BL7vg2.net
>>572
できました。
URLﾘﾝｸ(github.com)
CE02_n=10.txt
CollatzExpansion02.exe
CollatzExpansion02.hs

574:１３２人目の素数さん
18/07/29 16:49:37.95 QwhF8wXZ.net
ありがとうございます
いま外にいるので帰ったらみてみます

575:１３２人目の素数さん
18/07/29 17:29:22.44 oePH1MMB.net
ん、これコラッツ展開のビットのほうを左右反転させたんじゃなくて
コラッツ展開に対応する自然数のビットを反転させたってことですかね？

576:righ1113
18/07/29 17:53:25.69 z6BL7vg2.net
いや、両方反転させてるような......
なのに『同一』？？？

577:１３２人目の素数さん
18/07/29 18:13:30.45 oePH1MMB.net
>>576
つまりどういうことだってばよ？

578:righ1113
18/07/29 18:15:38.20 z6BL7vg2.net
>>576は無視してください。
コラッツ展開のビット（初項）を反転させています。

579:１３２人目の素数さん
18/07/29 18:34:34.10 oePH1MMB.net
すまん、まだよくわかってないんだが、
そうするとこの10進で表示してあるのは何を表してるの？

580:righ1113
18/07/29 18:41:19.06 z6BL7vg2.net
>>579
初項がコラッツ展開のビットで、
第二項が初期値（2進数）で、
第三項が初期値（10進数）です。

581:１３２人目の素数さん
18/07/29 18:44:40.84 oePH1MMB.net
第二項は左右反転してません？

582:righ1113
18/07/29 18:53:23.89 z6BL7vg2.net
してますね～　う～ん

583:１３２人目の素数さん
18/07/29 19:20:56.12 oePH1MMB.net
字下げされているデータは、上からｎ番目にあると第三項もnになる
という法則はありそうなきがする

584:righ1113
18/07/29 19:26:26.92 z6BL7vg2.net
>>583
あ、それはコラッツ展開のビットを1から順番に並べているので、
コラッツ展開と初期値が一致するなら、当然そうなると思われます。

585:righ1113
18/07/29 19:31:39.53 z6BL7vg2.net
>>575-582
色々とすみませんでした。
プログラムの説明不足でした。

586:１３２人目の素数さん
18/07/29 19:36:14.28 oePH1MMB.net
どうでもいいことだけど、いま私のメインマシンが壊れていて
古いノートPC（32bit OS)使ってます。
githubにあげてもらったexeは64bit版ですかね？動きませんでした。
私はソースのほう使ってるのでそれでも大丈夫ですが。

587:前786
18/07/29 21:59:54.79 sVL1UhWV.net
・コラッツ展開の表記は元のまま。縦の並び順だけを変えている。
・2進数表記は反転させている。
という状態みたいですね。
2進数表記を変えると混乱を招きそうなので
コラッツ展開の方を反転させた方がいいかも？。
つまり
("0000000000","0000000000",1024)
("0000000001","0101010101",341)
("0000000010","1010101010",682)
("0000000011","0011100011",227)
("0000000100","0101010100",340)
：
：
と出力させる感じで。

588:righ1113
18/07/31 21:40:25.63 RSiZq6mC.net
　　　　　 |
　　＼　　__　　／
　　＿　（ｍ）　＿ﾋﾟｺｰﾝ
　　　　　|ミ|
　　／　｀´　＼
　　　　　('A`)
　　　　　ノヽノヽ
　　　　　　　くく

589:righ1113
18/07/31 22:16:53.79 RSiZq6mC.net
コラッツ展開の一部が、コラッツ値の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で覆えます。

590:righ1113
18/07/31 22:20:11.18 RSiZq6mC.net
そして、
「コラッツ展開を、下位2ビット以上の2進数の連結で覆い尽くせる」→「コラッツ操作で1に辿り着く」
が言えれば良いと思うのです。

591:１３２人目の素数さん
18/07/31 23:08:52.93 M/YYnaxA.net
ん、よくわからん。
前７８６さん、わかります？

592:前786
18/08/01 13:01:17.37 p3PictoW.net
どういう操作をしてるかはなんとなく分かりましたけど、
なんかNGワードがあるとかで書き込めないので画像にて失礼。
URLﾘﾝｸ(i.imgur.com)
そこからの>>1さんの主張は私もはっきりとはわかりませんが、
「常に 2 ビット以上覆う」ということを利用してコラッツ予想を証明できないか、みたいな感じでしょうか。

593:righ1113
18/08/02 10:26:14.57 dbqVsLkv.net
>>592
そうです、こんな感じです。
（確かに26は3ビット覆えますね）

594:righ1113
18/08/04 14:45:23.85 T94V2xDI.net
うまくいきませんでした。

595:１３２人目の素数さん
18/08/06 20:24:49.16 msOD46p7.net
登って下がってというループで山が四つくらいまでのループは無いらしいが、この方面では難しそうだ
Zudilin あたりが書いた超越数の≪(3/2)^n≫ あたりからなんか言えんかね
ABC が絡むような話もどこかにあったような気がするのは気がふれたみたいだからさようなら

596:righ1113
18/08/08 20:15:08.57 owzSvaKk.net
ちょっと思い出話でも。
自分がスレを立てる前のコラッツスレに、
「割数列」というものがありました。
コラッツ操作で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]はふつうの割数列です。

597:前786
18/08/08 22:53:01.75 4mjRQHYS.net
(割数列の話を始めたのも私だったり)

598:righ1113
18/08/08 23:11:14.38 owzSvaKk.net
マジっすか!?

599:righ1113
18/08/08 23:29:36.29 owzSvaKk.net
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]が存在する。

600:前786
18/08/08 23:56:36.04 4mjRQHYS.net
いやあ、懐かしいですねぇ
ちなみに割数列とコラッツ展開は密接に関係しています。
実はコラッツ展開は、割数列から派生して得られたものだったりします。
例えば 9 のコラッツ展開は
　1,0,1,1,1,0,1,0,0,1,0,0,0,1,…
ですが、このとき 1 が現れてから次の 1 が現れるまでの項数を見ていくと
　2,1,1,2,3,4
となり、これが割数列に一致します。

601:righ1113
18/08/09 00:04:34.00 h30rXcjy.net
なるほど。そんな歴史があったのですね。

602:righ1113
18/08/09 05:30:13.84 h30rXcjy.net
>>599
前スレで、「全てのstar変換後の完全割数列は、全ての3の倍数の奇数を尽くす」事を証明しました。
しかし、後ろに無限に長く、base caseである21[6]にたどり着かない
完全割数列を排除できなくて、その時は挫折しました。

603:righ1113
18/08/09 23:59:53.30 h30rXcjy.net
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の計算自体は出来ているようです。

604:righ1113
18/08/10 00:28:24.11 tK64NAzp.net
全ての場合でうまくいく訳ではありません。
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の倍数に写ります。
これで得られる割数列を「拡張完全割数列」「拡張コラッツ予想」と呼ぶ事にします。

605:righ1113
18/08/10 23:41:44.61 tK64NAzp.net
拡張完全割数列のうちで、後ろに無限に長く、base caseである21[6]にたどり着かない、
最小反例を考えます。
この割数列にstar変換を施したものも、後ろの方は変わっていないので、反例です。
この反例が最小反例よりも小さければ、矛盾を引き出すことができます。
こういう目論見です。

606:righ1113
18/08/13 15:49:38.48 7T5v8z4w.net
考えていた物と別の証明が浮かんだので、そっちを書きます。
>>605の最小反例に、コラッツ値が偶数のものはありません。
2で割るとさらに小さくなるからです。
ということは、拡張完全割数列でコラッツ値が偶数のものは有限項です。
これに、star変換を逆に施した、普通の完全割数列も有限項（1に辿り着く）ということです。

607:righ1113
18/08/13 15:53:03.94 7T5v8z4w.net
普通の完全割数列に、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　偶数はない

608:righ1113
18/08/13 16:12:32.34 7T5v8z4w.net
コラッツ値x=36t+3とx=72t+9は1にたどり着く事が分かりました。
（3と9は手計算で、ということにしましょう）
ここで思ったのですが、このパターン、剰余コラッツ予想で解かれてなかったっけ！？
>>4
＞前スレ>>786の予想は、以下の場合に証明できています。
＞・n は 83 以下の奇数, k は任意
36は81に帰着されるので有効、
72は243なので今のところout

609:righ1113
18/08/14 15:24:26.87 jD9M+OTo.net
偶数は「最小でない反例」の可能性があるのですね。
失礼しました。
>>606-608は無しでお願いします。

610:righ1113
18/08/15 13:30:28.73 GlbaFw1x.net
>>605を証明します。
拡張完全割数列のうちで、後ろに無限に長く、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　　より小さい反例が得られました。

611:righ1113
18/08/15 13:33:56.44 GlbaFw1x.net
・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は存在しません。

612:righ1113
18/08/15 13:38:16.32 GlbaFw1x.net
拡張完全割数列に対して、無限項のものがないと分かりました。
よって、全ての項が正である、通常の完全割数列に限定しても、無限項のものはありません。
以上より、全ての3の倍数の奇数は、1に辿り着くことが言えました。

613:１３２人目の素数さん
18/08/15 16:53:18.16 GLWugf1o.net
えっ
ちょい待ち
全ての6n-3が1を含む枝に属する事が証明できた？
コラッツ予想の証明完了じゃん

614:righ1113
18/08/15 17:00:20.05 GlbaFw1x.net
>>613
そうなりますねぇ......

615:１３２人目の素数さん
18/08/15 23:30:39.14 kdLKmBaZ.net
マジで？
記念ﾊﾟﾋﾟｺ

616:前786
18/08/16 00:57:42.04 M+raKM1N.net
>>610で、c=18t''+21 から y=3t''+3 への変換で
対応する割数列の変換が本当に B[1,-2] になってるかが怪しいような。

617:righ1113
18/08/16 05:27:05.36 TWEwRPxI.net
>>616
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]
ひとまずうまくいっているようです。

618:righ1113
18/08/16 07:46:18.73 SnTp/ir+.net
c≡0 mod 9のときに不備がありそうです。
調査します。

619:前786
18/08/16 10:23:39.87 M+raKM1N.net
0 や負の項を許しているのを失念していました。
ただそうすると、一つの数に対して複数の数列が対応することになります。
c=18t''+21 の割数列に変換 B[1,-2] を施すと、y=3t''+3 の拡張完全割数列の一つが得られますが、
それは y=3t''+3 の通常の割数列と同じとは限らず、通常の割数列が無限に長いとは言い切れない、
すなわち反例になっているとは言い切れないと思います。

620:righ1113
18/08/16 13:10:13.37 1OdknrZ/.net
うーむ……
もうちょっと考えてみます。

621:１３２人目の素数さん
18/08/17 03:14:56.80 vsonpbq1.net
せっかく解けない問題があるんだから、何かに使えないんでしょうか
数独のようなパズルを作る
乱数を作る
暗号システムを作る

622:righ1113
18/08/18 15:11:04.30 D9NuquiS.net
>>619
入力も拡張完全割数列にすればどうでしょう。
図を書いてみました。
URLﾘﾝｸ(github.com)
反例を、
「ある3の倍数のコラッツ値を表す、拡張完全割数列の少なくとも一つが無限項である」
と定義します。これならどうでしょうか。

623:righ1113
18/08/18 15:15:35.49 D9NuquiS.net
画像が見えませんでした
URLﾘﾝｸ(imgur.com)

624:前786
18/08/19 13:08:49.21 Nc96juHr.net
最小反例が 3 である可能性がありますね。
その場合、コラッツ値をより小さくすることはできず、矛盾は生じません。

625:righ1113
18/08/19 16:15:52.14 z4KwPURj.net
そうですねぇ、だめですね……
ありがとうございました。

626:righ1113
18/08/20 11:12:57.60 rrcWSjx+.net
もうちょっと粘ってみます。

627:righ1113
18/08/24 21:38:07.63 md4HSYVM.net
レベルというものを導入します。
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つ有限項か計算すれば良いです。

628:righ1113
18/08/24 21:40:15.28 md4HSYVM.net
プログラムを使って説明します。
コラッツ値をあらわす割数列を列挙する関数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]
と、有限項の割数列で列挙できました。

629:righ1113
18/08/25 07:17:46.04 uY6dzjku.net
レベル1のコラッツ値3x+3に、最小反例が存在しない事を証明します。
3と9はallDivSeqを使って、
残りの数は、>>610-611を手直ししたものを使います。

630:righ1113
18/08/26 21:21:27.79 Oj7Z7mtg.net
3の倍数に0も含めることにします。
3も9もstar変換で0になって、小さくなるのでOKとします。
レベル1のコラッツ値3xに、最小反例が存在しない事を証明します。（後日）
0はallDivSeqを使って、
残りの数は、>>610-611を手直ししたものを使います。

631:righ1113
18/08/31 10:08:50.31 rYUAgAC8.net
いろいろ見直しています。
時間がかかりそうです。

632:righ1113
18/09/07 00:24:45.25 cStMejnA.net
見直しというか、証明の形式化にチャレンジしています。
Idrisというマニアックな言語を使っています。Coqみたいな事ができます。
型を合わせるのがめんど……いや、難しいですね。

633:righ1113
18/09/10 00:29:04.64 3QK+PA5a.net
場合分けが尽くせてないですが、Ver0.1をリリースします。
URLﾘﾝｸ(github.com)
最終的な定理はProofColDivSeqMain.idrにあって、以下です。
allDivSeqInfFalse : (n:Nat)
　-> any unLimited (allDivSeq (n+n+n) 0) = False
これは、3の倍数の奇数の完全割数列が全て、有限項である（1に辿り着く）
事を示しています。

634:righ1113
18/09/10 17:40:25.69 5z7WrYfQ.net
レベルを下げる関数に不備がありそうです。

635:righ1113
18/09/17 02:46:14.64 bqQZOfDF.net
>>634
関数を変更中です。手こずっています。

636:１３２人目の素数さん
18/09/18 19:02:33.53 pWdQneLm.net
笑

637:１３２人目の素数さん
18/09/18 21:06:42.03 Ww3uzjyt.net
しかし >>1の情熱がすごい
よくあきらめないな

638:righ1113
18/09/18 21:38:11.79 0UzjDC9R.net
>>637
なんというか、諦めきれないのです。

639:１３２人目の素数さん
18/09/19 02:37:49.74 +Q956Ag5.net
数学の60年来の難問を、「不老不死研究」の生物医学者がこうして解き明かした
URLﾘﾝｸ(wired.jp)
押しても引いてもだめなら、まったく違う方面からのほうがいいのかもね

640:righ1113
18/09/19 06:04:16.85 SqxJ5GTm.net
>>639
はー、なるほど。分かったような、分からないような。

641:righ1113
18/09/20 23:55:04.37 pHGNvy1m.net
ひとまずレベルを下げる関数の変更ができました。
URLﾘﾝｸ(github.com)

642:righ1113
18/09/20 23:58:02.70 pHGNvy1m.net
一つ注意点があります。
プログラムでの証明中に、postulate（無条件の仮定）を使っています。
なので、完全な形式化という訳ではないです。
postulateな命題については、紙の上で証明すれば良いと考えています。

643:righ1113
18/09/22 01:11:42.46 2udthHUG.net
URLﾘﾝｸ(github.com)
こんな感じで紙の証明も作ってってます。

644:１３２人目の素数さん
18/09/22 02:25:57.68 u2bLw4/9.net
なにげに結構なボリュームあるな
普通にすごいわ
内容的にただしいのか俺の実力じゃジャッジできないけど

645:righ1113
18/09/22 04:26:55.20 3m3m4Y8s.net
>>644
ありがとうございます。

646:righ1113
18/09/26 15:54:57.58 oAYpDJEp.net
DIR EN GREYのアルバムを買った。
これを聴いて証明を頑張ろう。

647:righ1113
18/10/01 03:21:47.90 wmcGCB2y.net
紙の証明　第二部が作成完了しました。
良かったら見てみて下さい。
第2部　レベル0のallDivSeqは、全て有限項　（これが言えればコラッツ予想も真）
URLﾘﾝｸ(github.com)

648:１３２人目の素数さん
18/10/02 01:11:28.28 F4M3UZCA.net
糞スレ晒しage

649:１３２人目の素数さん
18/10/02 22:53:15.38 OaloQ4ah.net
コラッツ予想を解くと500ドルもらえるらしい

650:righ1113
18/10/03 11:35:22.75 bBWfQNB+.net
>>649
多いのか、少ないのか……

651:１３２人目の素数さん
18/10/03 20:24:37.00 o70MBvQP.net
正直、１０００万円くらいの懸賞かかっててもいいと思うけどね

652:righ1113
18/10/03 20:30:12.03 nw1H62gV.net
そうですよね。100万でも「おおっ」ってなります。

653:１３２人目の素数さん
18/10/22 02:38:43.53 PnaJVaBQ.net
１０万円でもあればうれしい

654:１３２人目の素数さん
18/10/25 00:10:59.36 3G32divF.net
懸賞かかってなくてもコラッツとけたら年収１０００万の職につけないかなぁ？

655:１３２人目の素数さん
18/10/25 01:11:36.97 cTIjCy05.net
>>654
googleが採用してくれるかも

656:１３２人目の素数さん
18/10/27 00:52:40.01 NYHShEyu.net
証明は出来たのですか？
完全に素人質問で悪いのですが、証明の全容をここに載せたら盗まれる可能性があるのではないでしょうか？
arXivに上げるなどして正式に発表したほうがいいのでは…と思ってしまいます。

657:righ1113
18/10/27 01:22:28.45 3YbEazlL.net
>>656
ありがとうございます。
証明はほぼ完成しています。
URLﾘﾝｸ(github.com)
arXivに投稿するには、endorser裏書人が必要なので、難しいかなと思っています。

658:１３２人目の素数さん
18/10/27 07:43:06.53 4wEgV5jN.net
>>657
そのページは情報が欠けていて論理を追うことができません。

659:１３２人目の素数さん
18/10/27 10:44:44.71 sjLLdu9W.net
　　　／￣`Y ￣ヽ､
　　 /　/ / / l | | lヽヽ
　　/　/ //　⌒　 ⌒ヽ
　　|　| |/　（●）（●）
　（Ｓ|| | 　　⌒　･ｨ　ヽ　　芸能人が吹き替えに挑戦というのは
　　|　|| |　　　ﾄ-＝-ｧ　ﾉ
　　|　|| |　　　|-ｒ､/　/|
　　|　|| | ＼＿｀ﾆ'_／　|
　　　　((　(　つヽつ、
　　　　　　. 〉　　　i　))
　　　　　　（__ノ^（＿）

　　　／￣`Y ￣ヽ､
　　 /　/ / / l | | lヽヽ
　　/　/ //　⌒　 ⌒ヽ
　　|　| |/　（●）（●）
　（Ｓ|| | 　　⌒　･ｨ　ヽ　　許せないという気持ちが分かる
　　|　|| |　　　ﾄ-＝-ｧ　ﾉ
　　|　|| |　　　|-ｒ､/　/|
　　|　|| | ＼＿｀ﾆ'_／　|
　　　　⊂/　⊂　）
　　　　　 i　　　　ヽ
　　 ((　（＿）^ヽ.__） )) 👀
Rock54: Caution(BBR-MD5:1341adc37120578f18dba9451e6c8c3b)

660:１３２人目の素数さん
18/10/27 17:09:07.82 4wEgV5jN.net
この証明の鍵は、star変換によってコラッツ列の無限性を維持しつつ元の整数を小さくできるとする主張にあります。
しかし変換の定義からそのようなことが常に可能とは思えないというのが私の直感です。
まず確認ですが、star変換によって割数列に負の項が出てくることを許しているわけではないですよね？
各chapterを一読しましたが、『計算上は合う』というコメントもあり判然としません。
プログラムを読めば分かるのかもしれませんが素人なのでお許しを。
［chapter3より引用］
> 変換後のコラッツ値が、負数や分数になるものを禁止すれば、
> この変換は、3の倍数から3の倍数に写ります。
> これで得られる割数列を「拡張完全割数列」と呼ぶ事にします。
割数列の定義から負の項は存在できません。
たとえ最終計算が合っていたとしても、2を掛ける操作はコラッツ列の生成ルールにはありませんから、
負の項が出現するような変換は許されません。『拡張列』としてそれを考えるだけなら構いませんが、
拡張列から元の整数を復元する操作を統一的に行うことは許されないはずです。

661:righ1113
18/10/27 18:14:31.31 q47UWgiA.net
>>660
詳細なコメントありがとうございます。
すぐには答えられないので、じっくり考えてみます。

662:１３２人目の素数さん
18/10/27 19:27:37.82 4wEgV5jN.net
例を挙げておきます。
[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に対応する。
言えるのはこれだけのように思える。

663:righ1113
18/10/27 20:08:48.02 q47UWgiA.net
う～ん困りました……

664:１３２人目の素数さん
18/10/27 23:51:07.91 EnsDGGon.net
そもそもcoq使うなら全部coqにしなきゃ意味ないと思うが

665:１３２人目の素数さん
18/10/28 09:20:08.07 Inuvl635.net
私の指摘（>>660、>>662）は >>616や >>619の焼き直しでした。

666:righ1113
18/10/30 18:48:13.22 kWJk14TU.net
>>660,662
以下3つをおこなえば良いのではないかと考えています。
◆定義1　拡張コラッツ予想
6t+3（t≦0）を用意する。（ここからコラッツ操作すれば通常のコラッツ予想になる）
一度コラッツ操作を施したものをαとおく。
6t+3から1~3回star変換をおこなう。
そこから拡張コラッツ操作をおこなう。αに戻ったところで通常のコラッツ操作に切り替える。
これを拡張コラッツ予想と名付ける。
※拡張コラッツ操作
コラッツ値xに対し、(3x+1)/2^pを施す。pは割数列の初項（0や負も取りうる）。
◆定理1
あるコラッツ値（一度コラッツ操作したものをα）からstar変換したものを、
2回拡張コラッツ操作すると、αに戻る
◆定理2
拡張コラッツ予想が真　⇒　コラッツ予想も真

667:righ1113
18/11/01 23:53:32.36 JDsMJ7mn.net
◆定理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でやります。

668:righ1113
18/11/01 23:56:34.87 JDsMJ7mn.net
◆定理2
拡張コラッツ予想が真　⇒　コラッツ予想も真
star変換したものから拡張コラッツ操作を繰り返すと、
定理1より、全ての6t+3から遷移するαと同じものが、
欠けることなく得られます。
よって、拡張コラッツ予想が真ならば、
後方を共有する、通常のコラッツ予想も真になります。

669:１３２人目の素数さん
18/11/03 10:40:12.37 0X36i8df.net
>>666-668
その方針でこの問題が簡単化されるとは思いませんが。
righ1113さんの腕の見せ所ですね。
がんばってください。

670:righ1113
18/11/03 10:58:34.66 zGxL77aT.net
ありがとうございます。
頑張ります！

671:righ1113
18/11/16 00:08:05.29 rLiEECgK.net
ちょっとお休みします。

672:righ1113
18/11/21 00:38:18.69 5W7Y7t3o.net
完成しました。
URLﾘﾝｸ(github.com)

673:１３２人目の素数さん
18/12/27 21:03:12.26 QsKaQysV.net
突っ込みもなくなってしまったか。
寂しいのう。

674:righ1113
18/12/28 15:02:21.19 vw3Deup+.net
そうですね……

675:１３２人目の素数さん
19/04/20 06:08:45.05 qXeTVoFa.net
自然数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は存在するか？

676:１３２人目の素数さん
19/04/20 06:11:30.83 qXeTVoFa.net
ちょっと言ってることがおかしいかもしれない。
ようするにコラッツ展開に対する不動点みたいなものはあるか？という話をしたいのだが

677:righ1113
19/04/20 06:22:48.34 58m0UT5j.net
なるほど、ちょっと考えてみます

678:１３２人目の素数さん
19/04/20 06:24:30.09 qXeTVoFa.net
朝の6時にスレチェックかよｗすげえｗ
まあ俺も人のこと言えないけどｗお疲れ様です。

679:１３２人目の素数さん
19/04/20 06:30:30.11 qXeTVoFa.net
新たな不動点が見つかったら新たなループが見つかるみたいな方向に持っていけたらベストなんだけど。
まあまだぼんやりしたイメージがあるだけです。

680:１３２人目の素数さん
19/04/20 07:07:33.52 qXeTVoFa.net
うーん、collatz_arrayの停止条件がx==1だとあんまり意味のない議論になってしまうかもしれないorz

681:righ1113
19/04/20 08:32:56.05 gsPKCWwo.net
x==collatz_number(x)をチェックすると
3*2^tは該当するみたい。そりゃそうか。
あと、「先頭nビットが一致する」だと意味ないかな？

682:１３２人目の素数さん
19/04/20 08:52:09.89 qXeTVoFa.net
>>681
意味ないかどうかはまだわかりませんが、先頭nビットについては >>530のような割とはっきりした規則性があるようなので、
規則性の見えなくなる後ろのほうのビットのふるまいを何とかできないかという思いはあります。

683:１３２人目の素数さん
19/04/20 08:53:34.80 qXeTVoFa.net
あ、でもnを増やしていったらなんか出てくるんだろうか？

684:１３２人目の素数さん
19/04/20 09:20:18.07 qXeTVoFa.net
ちなみに勢いで書いちゃったけど仮に不動点が見つかったとして、それをどう生かせばいいかまだ全然見えてませんｗ

685:１３２人目の素数さん
19/04/20 09:23:37.92 qXeTVoFa.net
不動点というキーワードでコラッツ展開をみたときに、
ちょうど3が不動点になっていたのでこれが1,4,2のループを表しているのでは？
という思い付きというか期待から書き込んでしまいました。

686:１３２人目の素数さん
19/04/20 10:25:47.50 kQapNYTQ.net
コラッツ展開は01の無限列なので2-進整数に対応させるのはどうだろう
整数は2-進整数に埋め込めるし、コラッツ展開は2-進整数に自然に拡張できる
以下、簡略表記として左を下位、繰り返しを()で括る、とすると
0=(0)…
-1=(1)…
はコラッツ展開が自身と一致する
1=1(0)… のコラッツ展開は (10)…
(10)…は×3で(11)… = -1 なので
(10)…のコラッツ展開は 1(0)… で元に戻る

687:１３２人目の素数さん
19/04/20 10:44:40.51 2B/xzIiP.net
見捨てられた過疎スレかと思ってたら
意外とそうでもないのか

688:１３２人目の素数さん
19/04/20 12:02:57.09 2B/xzIiP.net
2進整数とやらを標準ライブラリで持ってるプログラム言語はありますか？

689:righ1113
19/04/20 12:48:56.09 gsPKCWwo.net
>>688
Mapleにありそうだけど
Mapleってフリーじゃないもんね

690:１３２人目の素数さん
19/04/20 13:09:40.55 kQapNYTQ.net
無限桁の2進数みたいなものだから、プログラムで扱うのは難しいのでは？
有限桁以降が繰り返しのものに限定すれば扱えるのかな
(10)…と-1/3、(100)…と-1/7、みたいに、
理論上は(分母の素因数に2を含まない)有理数に対応するはず

691:１３２人目の素数さん
19/04/20 13:21:28.65 qXeTVoFa.net
とりあえず、2-進整数の厳密な定義ってどこかにあります？
四則演算とかも含めて。

692:１３２人目の素数さん
19/04/20 13:27:40.12 qXeTVoFa.net
ハスケルは遅延評価があるんでしたっけ？
ルビーにもあったかな？

693:righ1113
19/04/20 13:45:31.66 gsPKCWwo.net
>>692
Haskellはデフォルトで遅延評価です。
Rubyも遅延評価がありそうですが、僕は詳しくないです。

694:１３２人目の素数さん
19/04/20 13:52:34.74 qXeTVoFa.net
2-進整数、使えそうなら使いたいですね
でも2-進整数にしちゃうと不動点のアイディアをどう扱えばいいかわからなくなるかなぁ？

695:１３２人目の素数さん
19/04/20 14:00:26.66 kQapNYTQ.net
とりあえずwikipediaよりp進数(p-adic number)
URLﾘﾝｸ(ja.m.wikipedia.org)
「定義」の最後にあるp進整数環でpが2のものを考えてるんですが、付値やら完備化や、専門的過ぎてたぶんわけわからんと思います
計算だけなら「略式の解説」のこの辺
> 整数側に無限桁加えたもの、例えば …1246328.125 のようなものが p 進数であると解釈できる。
> p 進数の中でも、小数点以下がない …1246328 のようなものは p 進整数と呼ばれるものに対応する。
> p 進数同士の足し算、引き算、掛け算は、p 進表記の有理数における通常のアルゴリズムを自然に無限桁に拡張することで得られ、割り算は掛け算の逆演算として定義される。

696:１３２人目の素数さん
19/04/20 14:04:10.33 qXeTVoFa.net
なるほど、わからんｗ

697:１３２人目の素数さん
19/04/20 14:08:48.97 qXeTVoFa.net
自力実装は相当厳しいかなこりゃ。

698:１３２人目の素数さん
19/04/20 15:43:16.25 qXeTVoFa.net
まともにやるとクソ難しそうなのでとりあえずコラッツ展開を分数で表現してみた
def collatz_rational(x)
l=x.length
res=0r
x.reverse.each_with_index{|v,i|res+=v*(1/2r)**(i+1)}
res+=((1/2r)**l)*1/3r
return res
end
def collatz_rational_array(x,l)
res=[]
(0...l).each{|i|
if(x>=1/2r)
then
x-=1/2r
res<<1
else
res<<0
end
x*=2r
}
return res.reverse
end
(1..1000).each{|x|
a=collatz_array(x)
l=a.length
r=collatz_rational(a)
b=collatz_rational_array(r,l)
if(a!=b)
then
print "#{x} #{r} #{a} #{b}\n"
end
}

699:１３２人目の素数さん
19/04/20 15:48:17.01 qXeTVoFa.net
でも分数にしたところで不動点のアイディアとどう結び付けていいかわからぬｗ
まあもともと不動点はそれほど目があるアイディアじゃないかもだけど

700:１３２人目の素数さん
19/04/20 16:03:08.59 qXeTVoFa.net
ありゃ、バグがあるっぽい
すまん、直す

701:１３２人目の素数さん
19/04/20 17:07:12.41 qXeTVoFa.net
URLﾘﾝｸ(ideone.com)
うーん、こうかな？

702:１３２人目の素数さん
19/04/20 17:09:11.57 qXeTVoFa.net
ちょっと疲れたｗ
休憩ｗ

703:１３２人目の素数さん
19/04/20 18:15:52.88 qXeTVoFa.net
スタートは不動点だったはずだが脱線してしまったなｗ
うーん、どうしよう

704:righ1113
19/04/20 18:43:16.20 gsPKCWwo.net
不動点ではないですが、
x == collatz_number(collatz_array(y))
y == collatz_number(collatz_array(x))
のように、相互に参照しあっているものを考え中です。
ちゃんとしたものは後日upします。
URLﾘﾝｸ(i.imgur.com)

705:１３２人目の素数さん
19/04/20 19:51:06.44 kQapNYTQ.net
2-進整数の計算についての補足
桁が繰り返しである2-進整数に限ると、
繰り返しが1で埋まれば-1であることを利用して
以下のように有理数との対応がわかります
(1)…=-1/(2^1-1)
(10)…=-1/(2^2-1)
(100)…=-1/(2^3-1)
途中から繰り返す場合についても、例えば
1(100)…=1+2(-1/7)=5/7
のようになります
そして、このようなものに限ると有理数としての加減乗除でまったく問題なかったりします
循環小数=有理数、みたいなもんですね

706:１３２人目の素数さん
19/04/20 21:01:20.91 qXeTVoFa.net
不動点ということは繰り返し処理をかけても変わらないということですが、
コラッツ展開に対してさらにそのコラッツ展開を求めることに何の意味があるのかが不明瞭なのが現状痛いですね。
そこに何らかの意味が見いだせればもう少し面白くなるのですが

707:righ1113
19/04/21 01:05:53.95 eAsDk9Da.net
特に何か得られた訳ではないですが、upします。
URLﾘﾝｸ(github.com)
気がついた事は、（不動点じゃないですが）
例えばxが17~31の奇数の区間で、コラッツ展開先頭5ビットが1~31の奇数を、
コラッツ3x+1と3x-1で分けあうことです。

708:righ1113
19/04/21 01:27:22.72 eAsDk9Da.net
>>707
書いてから思ったのですが、
>>530と関連があるのかどうか、というところですかね。

709:１３２人目の素数さん
19/04/21 07:54:17.77 npoMZDGj.net
負数の3x+1問題は実質3x-1問題(x→-x)なので
負数側の結果がスライドしてきている、と考えればよいのかなと

710:１３２人目の素数さん
19/04/21 21:02:50.26 pvqV4cbN.net
コラッツ展開が長さnの循環列
⇔xに対し「x→(3x+1)/2」または「x→x/2」の変換をある順番でn回行ってxに等しくできる
⇔0≦∃k≦n, ∃y∈Z, ((3^k)x+y)/2^n=x.
これは有理数の範囲で一つの解をもつ

711:１３２人目の素数さん
19/04/21 21:18:37.12 58cJHsba.net
すいません、不動点はあまり実りがなさそうなので撤退します。申し訳ない。
今1～2^nのコラッツ展開の先頭nビットを並べてコラッツ展開のkビット目にどのようなパターンが表れるかというのを見ようかと思ってます。

712:１３２人目の素数さん
19/04/21 21:54:43.91 58cJHsba.net
むむ、綺麗な周期が表れるかと思ったらそうでもない？

713:１３２人目の素数さん
19/04/21 22:53:56.35 58cJHsba.net
いや、周期になるみたい。
でもパターンは凄い複雑。

714:708
19/04/22 06:24:26.02 xqP02tmi.net
p進体Q_pにおいて、分母がpで割り切れない有理数はp進整数環Z_pに含まれることが知られている
(フェルマーの小定理より任意の素数q≠pに対してp^(q-1)≡0(mod q) なので、-1/qのp進展開がq-1桁の循環になる)
コラッツ問題の有理数への拡張は、Z_2への拡張と考えたほうが実は自然なのでは？
というところで2-進整数ネタも一休み
また週末かなー

715:righ1113
19/04/26 08:31:01.99 RlIUNLEW.net
コラッツ展開のコラッツ展開をいくつか計算してみましたが、いまいちでした。
URLﾘﾝｸ(github.com)
-1, 0, 1だけが特別で、（>>686）
これ以外の数は、コラッツ展開を施すごとに、どんどん複雑になっていくようです。
「3x-1」シートは、3x-1にして負値を計算したものです。

716:１３２人目の素数さん
19/04/26 20:39:33.09 xTZynMFI.net
繰り返したら元に戻るとか、そういうことはない感じですかね
フーリエ変換に対する逆変換みたいなものが見つからないか、というのは今のところ夢想かなあ

717:１３２人目の素数さん
19/04/26 20:57:44.06 xTZynMFI.net
>522
の補題を自分の中で整理してたらこうなった。
写像f: Z→Zを次で定義する.
x∈Z に対し,
f(x)=x/2 (x∈0+2Z)
f(x)=(3x+1)/2 (x∈1+2Z)
このとき, 0≦n∈Z, x, y∈Z に対して次が成り立つ.
x-y∈(2^n)Z ⇒ 0≦∃m≦n, s.t.
(2^n)(f^n(x)-f^n(y))=(3^m)(x-y).
(超略証)nに関する帰納法.
定義から0と1の場合がOK.
1とkをあわせてk+1の場合が示される.

718:righ1113
19/04/26 22:52:24.34 edmDBtkV.net
>>716
繰り返したら元に戻るとか、
小さくなる、とかだったら良かったですけどね。

719:１３２人目の素数さん
19/04/27 17:46:18.20 PhPZ0MkR.net
>717 に引き続き, >523 を代数学風に整理.
前述(>717)のf, x∈Z, 0≦i∈Zに対し x_i=f^i(x)+2Z で定まる Z/2Zの列{x_i}(i≧0)を「xのコラッツ展開」と呼ぶことにする.
x,y∈Zとそのコラッツ展開{x_i},{y_i}について次が成り立つ.
x-y∈(2^n)Z⇔x_i=y_i (0≦∀i≦n).
系. コラッツ展開は単射.

720:１３２人目の素数さん
19/05/08 21:48:28.23 U/58yMQ3.net
コラッツ展開はかなりいい線いってるとは思うが、次の一歩が難しい？

721:１３２人目の素数さん
19/05/08 22:07:04.85 U/58yMQ3.net
例えばxのコラッツ展開のyビット目がxのサイズの多項式時間で求まれば大きな前進と言える？

722:１３２人目の素数さん
19/05/08 22:10:31.84 U/58yMQ3.net
ここでいうxのサイズっていうのは自然数xに対してそれを表すのに必要なビット数log(x)のことね

723:righ1113
19/05/09 06:34:48.07 ysyHHFnM.net
>>721
入力サイズに対して、
コラッツ操作で何回2で割るかが分からないので、
難しいと思います。
特殊な場合だと、
2^n±1は、コラッツ展開のnビット目までを
多項式(定数?)時間で求められます。

次ページ