18/07/28 00:41:28.27 7NxoS75W.net
なにかグレイコードっぽい雰囲気を感じる
あくまで雰囲気だけど
580:righ1113
18/07/28 09:07:10.25 lMBBDrWw.net
>>543
しばしお待ちを。
581:前786
18/07/28 11:48:18.14 wb0cTFEt.net
コラッツ展開は 2 進展開に似ていますが、
以下のようにして明確に類似物であることを説明できます。
コラッツ操作 f の代わりに
x が奇数のとき g(x)=(x-1)/2
x が偶数のとき g(x)=x/2
という操作 g を考えます。
操作 g を用いて、整数( 2 進整数でも可)に対してコラッツ展開と同様に 0,1 からなる無限列が得られますが、
この無限列(を逆の順で並べたもの)は初期値の 2 進展開に一致します。
実際の 2 進展開の手順と見比べてみればわかると思います。
同様に、奇数 p,q を固定して
x が奇数のとき h(x)=(px+q)/2
x が偶数のとき h(x)=x/2
という操作 h を考えれば、同じ手順で 01 列への展開が得られ、
>>523>>524で示した事実の類似が成り立ちます。
582:righ1113
18/07/28 17:56:46.51 lMBBDrWw.net
>>543
できたよ～
URLﾘﾝｸ(github.com)
583:１３２人目の素数さん
18/07/28 18:15:36.05 7NxoS75W.net
>>547
おお、仕事速いっすな。
ありがとうございます。
584:１３２人目の素数さん
18/07/28 19:04:59.11 FfbExHmU.net
Python版
def collatz_bits(n):
result = [0] * pow(2,n)
for i in range(1, pow(2,n)+1):
x = i
s = ""
for j in range(n):
s += str(x % 2)
x = x // 2 if x % 2 == 0 else (3*x+1) // 2
result[int(s,2)] = i
return result
def print_collatz_bits(n):
for bits, k in enumerate(collatz_bits(n)):
print(f"{bits:0{n}b}:{k}")
>> collatz_bits(3)
[8, 4, 2, 6, 5, 1, 3, 7]
585:１３２人目の素数さん
18/07/28 19:12:39.28 7NxoS75W.net
>>547
動かしてみました。
確かになんらかの法則性があるように見えますが、うまく言語化できないorz
うーん。なんだろうこれは
586:１３２人目の素数さん
18/07/28 19:16:50.85 7NxoS75W.net
前786さんならなにかピンとくるものがあるかも知
587:れませんねぇ
588:１３２人目の素数さん
18/07/28 19:29:16.09 7NxoS75W.net
>>1へ
とりあえず前786さんにも見ていただきたいのですが、
前見たく出力結果をgithubにあげていただけませんか？
とりあえずn=10位がいいかなぁ
589:１３２人目の素数さん
18/07/28 20:14:20.24 7NxoS75W.net
あるビット列xに対し対応するコラッツ展開を持つ数を昇順にならべたものを[a_1,a_2,,,,a_2n]
とすると
x+'0'に対応するコラッツ展開をもつ数は[a_1,a_3,a_5,,,a_(2n-1)]
x+'1'に対応するコラッツ展開を持つ数は[a_2,a_4,a_6,,,a_2n]
になる？
590:righ1113
18/07/28 20:14:28.87 lMBBDrWw.net
>>552
n=10を上げました。
URLﾘﾝｸ(github.com)
591:１３２人目の素数さん
18/07/28 20:17:08.60 7NxoS75W.net
いや、ちょっとちがうな。
でも添え字が偶数のものと奇数のものに分かれるのは言えそう。
592:１３２人目の素数さん
18/07/28 20:20:56.40 7NxoS75W.net
>>554
ありがとうございます。
前７８６さんもぜひご覧になってなにか法則性がないか考察お願いします。
593:１３２人目の素数さん
18/07/28 20:49:43.10 7NxoS75W.net
すいません。また>>1にお願いがあるのですが
今１０進で表示されている数字をnビット先頭0埋め2進数で表示させられませんか？
ひょっとしたら法則性が見えやすくなるかもしれないのですが。
594:righ1113
18/07/28 21:32:38.98 lMBBDrWw.net
あげました～
URLﾘﾝｸ(github.com)
プログラムでやりたい場合は、
最新版のCollatzExpansion.hsの
74行目をコメントアウトして、
75行目のコメントを外すと、バイナリになります。
595:１３２人目の素数さん
18/07/28 22:00:14.13 7NxoS75W.net
おお、ありがとうございます。
さらに追加で要求でもうしわけないんですが、
１０進版とバイナリ版のexeもgithubに上げてもらえませんか
exeなら前786さんやほかの方も抵抗が少ないだろうし
596:righ1113
18/07/28 22:21:49.34 lMBBDrWw.net
上げました。
URLﾘﾝｸ(github.com)
CollatzExpansion.exe
CollatzExpansionB.exe
です。
597:１３２人目の素数さん
18/07/28 22:31:14.58 7NxoS75W.net
おお、何度もありがとうございます。
>>1にも聞いてみたいですが結構法則性ありそうに見えますよね？
598:righ1113
18/07/28 22:36:46.25 lMBBDrWw.net
>>561
2進数で左右反転しているのと、そうでないのとがありますね。
599:前786
18/07/28 22:40:43.24 wb0cTFEt.net
あまり期待はしないで下さいな。
出力の並び順ですが、
00000
10000
01000
11000
:
:
のようにしてもいいかもしれません。可能ならば。
>>546で言ったようにコラッツ展開を2進展開の類似物と捉えると、
コラッツ展開の初項が一の位に対応するので。
もしくは2進展開にならってコラッツ展開も右から左に書くことにするとか。
600:１３２人目の素数さん
18/07/28 23:51:31.58 7NxoS75W.net
確かに左右反転してるのが結構ありますねぇ…
601:M.B.
18/07/29 00:20:38.47 sLBYc3Xd.net
ぜんぜん関係のない話なんで、スレ汚しスマン。
以前、原始ピタゴラス数の絡みで、直角二等辺三角形に
収束する数列を、スターン＝ブロコット木の上で追いかけていたら、
そこにフィボナッチ数列が出てきたことがある。
どういう境界条件で左右反転が起きるのかは、追いかけてみたら
面白そうな気がする。
（私が面白そうな気がするだけで、結果についてはいっさい責任は
取らないということは、いうまでもないが）
602:１３２人目の素数さん
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
603:１３２人目の素数さん
18/07/29 01:05:24.07 apdazvkC.net
割合的には急激に減る
桁数をnとすると、n*log nくらいのオーダーか？
604:１３２人目の素数さん
18/07/29 01:06:53.56 oePH1MMB.net
さらに>>１にお願いしたいが
入力ｎに対して丁度nビットの01列とそれに対応するコラッツ展開をもつ2^n以下の自然数を列挙
コラッツ展開と自然数を２進であらわしたものが反転してる関係にあるものは行頭に空白４個入れる
反転ではないものは行頭に空白を入れずに表示
でプログラムお願いできない？
605:１３２人目の素数さん
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]
606:前786
18/07/29 12:59:45.00 sVL1UhWV.net
左右反転については考えたことは無かったですね。
とりあえず偶数は奇数に帰着されるので、奇数だけ見るのがいいような気がします。
607:righ1113
18/07/29 14:30:52.71 z6BL7vg2.net
>>568
>>563の案についてはどうしましょうか？
ビット列を左から書くようにすると、
ビット列とコラッツ展開が『左右反転している』 → 『同一である』
になって分かりやすいと思うのですが。
608:566
18/07/29 14:59:40.32 QwhF8wXZ.net
>>571
じゃあ採用してみましょうか
お願いします
609:righ1113
18/07/29 16:26:02.64 z6BL7vg2.net
>>572
できました。
URLﾘﾝｸ(github.com)
CE02_n=10.txt
CollatzExpansion02.exe
CollatzExpansion02.hs
610:１３２人目の素数さん
18/07/29 16:49:37.95 QwhF8wXZ.net
ありがとうございます
いま外にいるので帰ったらみてみます
611:１３２人目の素数さん
18/07/29 17:29:22.44 oePH1MMB.net
ん、これコラッツ展開のビットのほうを左右反転させたんじゃなくて
コラッツ展開に対応する自然数のビットを反転させたってことですかね？
612:righ1113
18/07/29 17:53:25.69 z6BL7vg2.net
いや、両方反転させてるような......
なのに『同一』？？？
613:１３２人目の素数さん
18/07/29 18:13:30.45 oePH1MMB.net
>>576
つまりどういうことだってばよ？
614:righ1113
18/07/29 18:15:38.20 z6BL7vg2.net
>>576は無視してください。
コラッツ展開のビット（初項）を反転させています。
615:１３２人目の素数さん
18/07/29 18:34:34.10 oePH1MMB.net
すまん、まだよくわかってないんだが、
そうするとこの10進で表示してあるのは何を表してるの？
616:righ1113
18/07/29 18:41:19.06 z6BL7vg2.net
>>579
初項がコラッツ展開のビットで、
第二項が初期値（2進数）で、
第三項が初期値（10進数）です。
617:１３２人目の素数さん
18/07/29 18:44:40.84 oePH1MMB.net
第二項は左右反転してません？
618:righ1113
18/07/29 18:53:23.89 z6BL7vg2.net
してますね～ う～ん
619:１３２人目の素数さん
18/07/29 19:20:56.12 oePH1MMB.net
字下げされているデータは、上からｎ番目にあると第三項もnになる
という法則はありそうなきがする
620:righ1113
18/07/29 19:26:26.92 z6BL7vg2.net
>>583
あ、それはコラッツ展開のビットを1から順番に並べているので、
コラッツ展開と初期値が一致するなら、当然そうなると思われます。
621:righ1113
18/07/29 19:31:39.53 z6BL7vg2.net
>>575-582
色々とすみませんでした。
プログラムの説明不足でした。
622:１３２人目の素数さん
18/07/29 19:36:14.28 oePH1MMB.net
どうでもいいことだけど、いま私のメインマシンが壊れていて
古いノートPC（32bit OS)使ってます。
githubにあげてもらったexeは64bit版ですかね？動きませんでした。
私は�
623:\ースのほう使ってるのでそれでも大丈夫ですが。
624:前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)
：
：
と出力させる感じで。
625:righ1113
18/07/31 21:40:25.63 RSiZq6mC.net
|
＼ __ ／
＿ （ｍ） ＿ﾋﾟｺｰﾝ
|ミ|
／ ｀´ ＼
('A`)
ノヽノヽ
くく
626: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で覆えます。
627:righ1113
18/07/31 22:20:11.18 RSiZq6mC.net
そして、
「コラッツ展開を、下位2ビット以上の2進数の連結で覆い尽くせる」→「コラッツ操作で1に辿り着く」
が言えれば良いと思うのです。
628:１３２人目の素数さん
18/07/31 23:08:52.93 M/YYnaxA.net
ん、よくわからん。
前７８６さん、わかります？
629:前786
18/08/01 13:01:17.37 p3PictoW.net
どういう操作をしてるかはなんとなく分かりましたけど、
なんかNGワードがあるとかで書き込めないので画像にて失礼。
URLﾘﾝｸ(i.imgur.com)
そこからの>>1さんの主張は私もはっきりとはわかりませんが、
「常に 2 ビット以上覆う」ということを利用してコラッツ予想を証明できないか、みたいな感じでしょうか。
630:righ1113
18/08/02 10:26:14.57 dbqVsLkv.net
>>592
そうです、こんな感じです。
（確かに26は3ビット覆えますね）
631:righ1113
18/08/04 14:45:23.85 T94V2xDI.net
うまくいきませんでした。
632:１３２人目の素数さん
18/08/06 20:24:49.16 msOD46p7.net
登って下がってというループで山が四つくらいまでのループは無いらしいが、この方面では難しそうだ
Zudilin あたりが書いた 超越数の≪(3/2)^n≫ あたりからなんか言えんかね
ABC が絡むような話もどこかにあったような気がするのは気がふれたみたいだからさようなら
633: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]はふつうの割数列です。
634:前786
18/08/08 22:53:01.75 4mjRQHYS.net
(割数列の話を始めたのも私だったり)
635:righ1113
18/08/08 23:11:14.38 owzSvaKk.net
マジっすか!?
636:righ1113
18/08/08 23:29:36.29 owzSvaKk.net
star変換というものがありました。
（名前は勝手に僕がつけました）
長さｎの完全割数列→長さｎ＋１の完全割数列
まず、長さｎの完全割数列を、初項に０
637:をつけたｎ＋１型で表す。 長さｎの完全割数列でできる最終値を９で割ったあまりが・・ ３ ・・ 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]が存在する。
638:前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
となり、これが割数列に一致します。
639:righ1113
18/08/09 00:04:34.00 h30rXcjy.net
なるほど。そんな歴史があったのですね。
640:righ1113
18/08/09 05:30:13.84 h30rXcjy.net
>>599
前スレで、「全てのstar変換後の完全割数列は、全ての3の倍数の奇数を尽くす」事を証明しました。
しかし、後ろに無限に長く、base caseである21[6]にたどり着かない
完全割数列を排除できなくて、その時は挫折しました。
641: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の計算自体は出来ているようです。
642: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の倍数に写ります。
これで得られる割数列を「拡張完全割数列」「拡張コラッツ予想」と呼ぶ事にします。
643:righ1113
18/08/10 23:41:44.61 tK64NAzp.net
拡張完全割数列のうちで、後ろに無限に長く、base caseである21[6]にたどり着かない、
最小反例を考えます。
この割数列にstar変換を施したものも、後ろの方は変わっていないので、反例です。
この反例が最小反例よりも小さければ、矛盾を引き出すことができます。
こういう目論見です。
644:righ1113
18/08/13 15:49:38.48 7T5v8z4w.net
考えていた物と別の証明が浮かんだので、そっちを書きます。
>>605の最小反例に、コラッツ値が偶数のものはありません。
2で割るとさらに小さくなるからです。
ということは、拡張完全割数列でコラッツ値が偶数のものは有限項です。
これに、star変換を逆に施した、普通の完全割数列も有限項（1に辿り着く）ということです。
645: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
646:は有限項 F[5,-2] y=8x/3-3 x=9+18t ⇒ y=48t+21 偶数はない
647: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
648:righ1113
18/08/14 15:24:26.87 jD9M+OTo.net
偶数は「最小でない反例」の可能性があるのですね。
失礼しました。
>>606-608は無しでお願いします。
649: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 より小さい反例が得られました。
650: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は存在しません。
651:righ1113
18/08/15 13:38:16.32 GlbaFw1x.net
拡張完全割数列に対して、無限項のものがないと分かりました。
よって、全ての項が正である、通常の完全割数列に限定しても、無限項のものはありません。
以上より、全ての3の倍数の奇数は、1に辿り着くことが言えました。
652:１３２人目の素数さん
18/08/15 16:53:18.16 GLWugf1o.net
えっ
ちょい待ち
全ての6n-3が1を含む枝に属する事が証明できた？
コラッツ予想の証明完了じゃん
653:righ1113
18/08/15 17:00:20.05 GlbaFw1x.net
>>613
そうなりますねぇ......
654:１３２人目の素数さん
18/08/15 23:30:39.14 kdLKmBaZ.net
マジで？
記念ﾊﾟﾋﾟｺ
655:前786
18/08/16 00:57:42.04 M+raKM1N.net
>>610で、c=18t''+21 から y=3t''+3 への変換で
対応する割数列の変換が本当に B[1,-2] になってるかが怪しいような。
656: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]
ひとまずうまくいっているようです。
657:righ1113
18/08/16 07:46:18.73 SnTp/ir+.net
c≡0 mod 9のときに不備がありそうです。
調査します。
658:前786
18/08/16 10:23:39.87 M+raKM1N.net
0 や負の項を許しているのを失念していました。
ただそうすると、一つの数に対して複数の数列が対応することになります。
c=18t''+21 の割数列に変換 B[1,-2] を施すと、y=3t''+3 の拡張完全割数列の一つが得られますが、
それは y=3t''+3 の通常の割数列と同じとは限らず、通常の割数列が無限に長いとは言い切れない、
すなわち反例になっているとは言い切れないと思います。
659:righ1113
18/08/16 13:10:13.37 1OdknrZ/.net
うーむ……
もうちょっと考えてみます。
660:１３２人目の素数さん
18/08/17 03:14:56.80 vsonpbq1.net
せっかく解けない問題があるんだから、何かに使えないんでしょうか
数独のようなパズルを作る
乱数を作る
暗号システムを作る
661:righ1113
18/08/18 15:11:04.30 D9NuquiS.net
>>619
入力も拡張完全割数列にすればどうでしょう。
図を書いてみました。
URLﾘﾝｸ(github.com)
反例を、
「ある3の倍数のコラッツ値を表す、拡張完全割数列の少なくとも一つが無限項である」
と定義します。これならどうでしょうか。
662:righ1113
18/08/18 15:15:35.49 D9NuquiS.net
画像が見えませんでした
URLﾘﾝｸ(imgur.com)
663:前786
18/08/19 13:08:49.21 Nc96juHr.net
最小反例が 3 である可能性がありますね。
その場合、コラッツ値をより小さくすることはできず、矛盾は生じません。
664:righ1113
18/08/19 16:15:52.14 z4KwPURj.net
そうですねぇ、だめですね……
ありがとうございました。
665:righ1113
18/08/20 11:12:57.60 rrcWSjx+.net
もうちょっと粘ってみます。
666: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つ有限項か計算すれば良いです。
667: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]
と、有限項の割数列で列挙できました。
668:righ1113
18/08/25 07:17:46.04 uY6dzjku.net
レベル1のコラッツ値3x+3に、最小反例が存在しない事を証明します。
3と9はallDivSeqを使って、
残りの数は、>>610-611を手直ししたものを使います。
669:righ1113
18/08/26 21:21:27.79 Oj7Z7mtg.net
3の倍数に0も含めることにします。
3も9もstar変換で0になって、小さくなるのでOKとします。
レベル1のコラッツ値3xに、最小反例が存在しない事を証明します。（後日）
0はallDivSeqを使って、
残りの数は、>>610-611を手直ししたものを使います。
670:righ1113
18/08/31 10:08:50.31 rYUAgAC8.net
いろいろ見直しています。
時間がかかりそうです。
671:righ1113
18/09/07 00:24:45.25 cStMejnA.net
見直しというか、証明の形式化にチャレンジしています。
Idrisというマニアックな言語を使っています。Coqみたいな事ができます。
型を合わせるのがめんど……いや、難しいですね。
672:righ1113
18/09/10 00:29:04.64 3QK+PA5a.net
場合分けが尽くせてないですが、Ver0.1をリリースします。
URLﾘﾝｸ(github.com)
最終的な�
673:阯揩ﾍProofColDivSeqMain.idrにあって、以下です。 allDivSeqInfFalse : (n:Nat) -> any unLimited (allDivSeq (n+n+n) 0) = False これは、3の倍数の奇数の完全割数列が全て、有限項である（1に辿り着く） 事を示しています。
674:righ1113
18/09/10 17:40:25.69 5z7WrYfQ.net
レベルを下げる関数に不備がありそうです。
675:righ1113
18/09/17 02:46:14.64 bqQZOfDF.net
>>634
関数を変更中です。手こずっています。
676:１３２人目の素数さん
18/09/18 19:02:33.53 pWdQneLm.net
笑
677:１３２人目の素数さん
18/09/18 21:06:42.03 Ww3uzjyt.net
しかし>>1の情熱がすごい
よくあきらめないな
678:righ1113
18/09/18 21:38:11.79 0UzjDC9R.net
>>637
なんというか、諦めきれないのです。
679:１３２人目の素数さん
18/09/19 02:37:49.74 +Q956Ag5.net
数学の60年来の難問を、「不老不死研究」の生物医学者がこうして解き明かした
URLﾘﾝｸ(wired.jp)
押しても引いてもだめなら、まったく違う方面からのほうがいいのかもね
680:righ1113
18/09/19 06:04:16.85 SqxJ5GTm.net
>>639
はー、なるほど。分かったような、分からないような。
681:righ1113
18/09/20 23:55:04.37 pHGNvy1m.net
ひとまずレベルを下げる関数の変更ができました。
URLﾘﾝｸ(github.com)
682:righ1113
18/09/20 23:58:02.70 pHGNvy1m.net
一つ注意点があります。
プログラムでの証明中に、postulate（無条件の仮定）を使っています。
なので、完全な形式化という訳ではないです。
postulateな命題については、紙の上で証明すれば良いと考えています。
683:righ1113
18/09/22 01:11:42.46 2udthHUG.net
URLﾘﾝｸ(github.com)
こんな感じで紙の証明も作ってってます。
684:１３２人目の素数さん
18/09/22 02:25:57.68 u2bLw4/9.net
なにげに結構なボリュームあるな
普通にすごいわ
内容的にただしいのか俺の実力じゃジャッジできないけど
685:righ1113
18/09/22 04:26:55.20 3m3m4Y8s.net
>>644
ありがとうございます。
686:righ1113
18/09/26 15:54:57.58 oAYpDJEp.net
DIR EN GREYのアルバムを買った。
これを聴いて証明を頑張ろう。
687:righ1113
18/10/01 03:21:47.90 wmcGCB2y.net
紙の証明 第二部が作成完了しました。
良かったら見てみて下さい。
第2部 レベル0のallDivSeqは、全て有限項 （これが言えればコラッツ予想も真）
URLﾘﾝｸ(github.com)
688:１３２人目の素数さん
18/10/02 01:11:28.28 F4M3UZCA.net
糞スレ晒しage
689:１３２人目の素数さん
18/10/02 22:53:15.38 OaloQ4ah.net
コラッツ予想を解くと500ドルもらえるらしい
690:righ1113
18/10/03 11:35:22.75 bBWfQNB+.net
>>649
多いのか、少ないのか……
691:１３２人目の素数さん
18/10/03 20:24:37.00 o70MBvQP.net
正直、１０００万円くらいの懸賞かかっててもいいと思うけどね
692:righ1113
18/10/03 20:30:12.03 nw1H62gV.net
そうですよね。100万でも「おおっ」ってなります。
693:１３２人目の素数さん
18/10/22 02:38:43.53 PnaJVaBQ.net
１０万円でもあればうれしい
694:１３２人目の素数さん
18/10/25 00:10:59.36 3G32divF.net
懸賞かかってなくてもコラッツとけたら年収１０００万の職につけないかなぁ？
695:１３２人目の素数さん
18/10/25 01:11:36.97 cTIjCy05.net
>>654
googleが採用してくれるかも
696:１３２人目の素数さん
18/10/27 00:52:40.01 NYHShEyu.net
証明は出来たのですか？
完全に素人質問で悪いのですが、証明の全容をここに載せたら盗まれる可能性があるのではないでしょうか？
arXivに上げるなどして正式に発表したほうがいいのでは…と思ってしまいます。
697:righ1113
18/10/27 01:22:28.45 3YbEazlL.net
>>656
ありがとうございます。
証明はほぼ完成しています。
URLﾘﾝｸ(github.com)
arXivに投稿するには、endorser裏書人が必要なので、難しいかなと思っています。
698:１３２人目の素数さん
18/10/27 07:43:06.53 4wEgV5jN.net
>>657
そのページは情報が欠けていて論理を追うことができません。
699:１３２人目の素数さん
18/10/27 10:44:44.71 sjLLdu9W.net
／￣`Y ￣ヽ､
/ / / / l | | lヽヽ
/ / // ⌒ ⌒ヽ
| | |/ （●） （●）
（Ｓ|| | ⌒ ･ｨ ヽ 芸能人が吹き替えに挑戦というのは
| || | ﾄ-＝-ｧ ﾉ
| || | |-ｒ ､/ /|
| || | ＼＿｀ﾆ'_／ |
(( ( つ ヽつ、
. 〉 i ))
（__ノ^（＿）
／￣`Y ￣ヽ､
/ / / / l | | lヽヽ
/ / // ⌒ ⌒ヽ
| | |/ （●） （●）
（Ｓ|| | ⌒ ･ｨ ヽ 許せないという気持ちが分かる
| || | ﾄ-＝-ｧ ﾉ
| || | |-ｒ ､/ /|
| || | ＼＿｀ﾆ'_／ |
⊂/ ⊂ ）
i ヽ
(( （＿）^ヽ.__） )) 👀
Rock54: Caution(BBR-MD5:1341adc37120578f18dba9451e6c8c3b)
700:１３２人目の素数さん
18/10/27 17:09:07.82 4wEgV5jN.net
この証明の鍵は、star変換によってコラッツ列の無限性を維持しつつ元の整数を小さくできるとする主張にあります。
しかし変換の定義から そのようなことが常に可能とは思えない というのが私の直感です。
まず確認ですが、star変換によって割数列に負の項が出てくることを許しているわけではない ですよね？
各chapterを一読しましたが、『計算上は合う』というコメントもあり判然としません。
プログラムを読めば分かるのかもしれませんが素人なのでお許しを。
［chapter3より引用］
> 変換後のコラッツ値が、負数や分数になるものを禁止すれば、
> この変換は、3の倍数から3の倍数に写ります。
> これで得られる割数列を 「拡張完全割数列」 と呼ぶ事にします。
割数列の定義から負の項は存在できません。
たとえ最終計算が合っていたとしても、2を掛ける操作はコラッツ列の生成ルールにはありませんから、
負の項が出現するような変換は許されません。『拡張列』としてそれを 考えるだけ なら構いませんが、
拡張列から元の整数を復元する操作を統一的に行うことは許されないはずです。
701:righ1113
18/10/27 18:14:31.31 q47UWgiA.net
>>660
詳細なコメントありがとうございます。
すぐには答えられないので、じっくり考えてみます。
702:１３２人目の素数さん
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つの操作を別のルールに則って行う
703:。 ・各操作後の値は整数とは限らない。 このような拡張されたコラッツ問題を考えることに相当する。 その拡張されたルールを前提とすれば、[1，4]と[2，-1，2，3，4］は共に3tに対応する。 言えるのはこれだけのように思える。
704:righ1113
18/10/27 20:08:48.02 q47UWgiA.net
う～ん困りました……
705:１３２人目の素数さん
18/10/27 23:51:07.91 EnsDGGon.net
そもそもcoq使うなら全部coqにしなきゃ意味ないと思うが
706:１３２人目の素数さん
18/10/28 09:20:08.07 Inuvl635.net
私の指摘（>>660、>>662）は >>616や>>619の焼き直しでした。
707: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
拡張コラッツ予想が真 ⇒ コラッツ予想も真
708: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でやります。
709:righ1113
18/11/01 23:56:34.87 JDsMJ7mn.net
◆定理2
拡張コラッツ予想が真 ⇒ コラッツ予想も真
star変換したものから拡張コラッツ操作を繰り返すと、
定理1より、全ての6t+3から遷移するαと同じものが、
欠けることなく得られます。
よって、拡張コラッツ予想が真ならば、
後方を共有する、通常のコラッツ予想も真になります。
710:１３２人目の素数さん
18/11/03 10:40:12.37 0X36i8df.net
>>666-668
その方針でこの問題が簡単化されるとは思いませんが。
righ1113さんの腕の見せ所ですね。
がんばってください。
711:righ1113
18/11/03 10:58:34.66 zGxL77aT.net
ありがとうございます。
頑張ります！
712:righ1113
18/11/16 00:08:05.29 rLiEECgK.net
ちょっとお休みします。
713:righ1113
18/11/21 00:38:18.69 5W7Y7t3o.net
完成しました。
URLﾘﾝｸ(github.com)
714:１３２人目の素数さん
18/12/27 21:03:12.26 QsKaQysV.net
突っ込みもなくなってしまったか。
寂しいのう。
715:righ1113
18/12/28 15:02:21.19 vw3Deup+.net
そうですね……
716:１３２人目の素数さん
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は存在するか？
717:１３２人目の素数さん
19/04/20 06:11:30.83 qXeTVoFa.net
ちょっと言ってることがおかしいかもしれない。
ようするにコラッツ展開に対する不動点みたいなものはあるか？という話をしたいのだが
718:righ1113
19/04/20 06:22:48.34 58m0UT5j.net
なるほど、ちょっと考えてみます
719:１３２人目の素数さん
19/04/20 06:24:30.09 qXeTVoFa.net
朝の6時にスレチェックかよｗすげえｗ
まあ俺も人のこと言えないけどｗお疲れ様です。
720:１３２人目の素数さん
19/04/20 06:30:30.11 qXeTVoFa.net
新たな不動点が見つかったら新たなループが見つかるみたいな方向に持っていけたらベストなんだけど。
まあまだぼんやりしたイメージがあるだけです。
721:１３２人目の素数さん
19/04/20 07:07:33.52 qXeTVoFa.net
うーん、collatz_arrayの停止条件がx==1だとあんまり意味のない議論になってしまうかもしれないorz
722:righ1113
19/04/20 08:32:56.05 gsPKCWwo.net
x==collatz_number(x)をチェックすると
3*2^tは該当するみたい。そりゃそうか。
あと、「先頭nビットが一致する」だと意味ないかな？
723:１３２人目の素数さん
19/04/20 08:52:09.89 qXeTVoFa.net
>>681
意味ないかどうかはまだわかりませんが、先頭nビットについては>>530のような割とはっきりした規則性があるようなので、
規則性の見えなくなる後ろのほうのビットのふるまいを何とかできないかという思いはあります。
724:１３２人目の素数さん
19/04/20 08:53:34.80 qXeTVoFa.net
あ、でもnを増やしていったらなんか出てくるんだろうか？
725:１３２人目の素数さん
19/04/20 09:20:18.07 qXeTVoFa.net
ちなみに勢いで書いちゃったけど仮に不動点が見つかったとして、それをどう生かせばいいかまだ全然見えてませんｗ
726:１３２人目の素数さん
19/04/20 09:23:37.92 qXeTVoFa.net
不動点というキーワードでコラッツ展開をみたときに、
ちょうど3が不動点になっていたのでこれが1,4,2のループを表しているのでは？
という思い付きというか期待から書き込んでしまいました。
727:１３２人目の素数さん
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)… で元に戻る
728:１３２人目の素数さん
19/04/20 10:44:40.51 2B/xzIiP.net
見捨てられた過疎スレかと思ってたら
意外とそうでもないのか
729:１３２人目の素数さん
19/04/20 12:02:57.09 2B/xzIiP.net
2進整数とやらを標準ライブラリで持ってるプログラム言語はありますか？
730:righ1113
19/04/20 12:48:56.09 gsPKCWwo.net
>>688
Mapleにありそうだけど
Mapleってフリーじゃないもんね
731:１３２人目の素数さん
19/04/20 13:09:40.55 kQapNYTQ.net
無限桁の2進数みたいなものだから、プログラムで扱うのは難しいのでは？
有限桁以降が繰り返しのものに限定すれば扱えるのかな
(10)…と-1/3、(100)…と-1/7、みたいに、
理論上は(分母の素因数に2を含まない)有理数に対応するはず
732:１３２人目の素数さん
19/04/20 13:21:28.65 qXeTVoFa.net
とりあえず、2-進整数の厳密な定義ってどこかにあります？
四則演算とかも含めて。
733:１３２人目の素数さん
19/04/20 13:27:40.12 qXeTVoFa.net
ハスケルは遅延評価があるんでしたっけ？
ルビーにもあったかな？
734:righ1113
19/04/20 13:45:31.66 gsPKCWwo.net
>>692
Haskellはデフォルトで遅延評価です。
Rubyも遅延評価がありそうですが、僕は詳しくないです。
735:１３２人目の素数さん
19/04/20 13:52:34.74 qXeTVoFa.net
2-進整数、使えそうなら使いたいですね
でも2-進整数にしちゃうと不動点のアイディアをどう扱えばいいかわからなくなるかなぁ？
736:１３２人目の素数さん
19/04/20 14:00:26.66 kQapNYTQ.net
とりあえずwikipediaよりp進数(p-a
737:dic number) https://ja.m.wikipedia.org/wiki/P%E9%80%B2%E6%95%B0 「定義」の最後にあるp進整数環でpが2のものを考えてるんですが、付値やら完備化や、専門的過ぎてたぶんわけわからんと思います 計算だけなら「略式の解説」のこの辺 > 整数側に無限桁加えたもの、例えば …1246328.125 のようなものが p 進数であると解釈できる。 > p 進数の中でも、小数点以下がない …1246328 のようなものは p 進整数と呼ばれるものに対応する。 > p 進数同士の足し算、引き算、掛け算は、p 進表記の有理数における通常のアルゴリズムを自然に無限桁に拡張することで得られ、割り算は掛け算の逆演算として定義される。
738:１３２人目の素数さん
19/04/20 14:04:10.33 qXeTVoFa.net
なるほど、わからんｗ
739:１３２人目の素数さん
19/04/20 14:08:48.97 qXeTVoFa.net
自力実装は相当厳しいかなこりゃ。
740:１３２人目の素数さん
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
}
741:１３２人目の素数さん
19/04/20 15:48:17.01 qXeTVoFa.net
でも分数にしたところで不動点のアイディアとどう結び付けていいかわからぬｗ
まあもともと不動点はそれほど目があるアイディアじゃないかもだけど
742:１３２人目の素数さん
19/04/20 16:03:08.59 qXeTVoFa.net
ありゃ、バグがあるっぽい
すまん、直す
743:１３２人目の素数さん
19/04/20 17:07:12.41 qXeTVoFa.net
URLﾘﾝｸ(ideone.com)
うーん、こうかな？
744:１３２人目の素数さん
19/04/20 17:09:11.57 qXeTVoFa.net
ちょっと疲れたｗ
休憩ｗ
745:１３２人目の素数さん
19/04/20 18:15:52.88 qXeTVoFa.net
スタートは不動点だったはずだが脱線してしまったなｗ
うーん、どうしよう
746: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)
747:１３２人目の素数さん
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
のようになります
そして、このようなものに限ると有理数としての加減乗除でまったく問題なかったりします
循環小数=有理数、みたいなもんですね
748:１３２人目の素数さん
19/04/20 21:01:20.91 qXeTVoFa.net
不動点ということは繰り返し処理をかけても変わらないということですが、
コラッツ展開に対してさらにそのコラッツ展開を求めることに何の意味があるのかが不明瞭なのが現状痛いですね。
そこに何らかの意味が見いだせればもう少し面白くなるのですが
749:righ1113
19/04/21 01:05:53.95 eAsDk9Da.net
特に何か得られた訳ではないですが、upします。
URLﾘﾝｸ(github.com)
気がついた事は、（不動点じゃないですが）
例えばxが17~31の奇数の区間で、コラッツ展開先頭5ビットが1~31の奇数を、
コラッツ3x+1と3x-1で分けあうことです。
750:righ1113
19/04/21 01:27:22.72 eAsDk9Da.net
>>707
書いてから思ったのですが、
>>530と関連があるのかどうか、というところですかね。
751:１３２人目の素数さん
19/04/21 07:54:17.77 npoMZDGj.net
負数の3x+1問題は実質3x-1問題(x→-x)なので
負数側の結果がスライドしてきている、と考えればよいのかなと
752:１３２人目の素数さん
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.
これは有理数の範囲で一つの解をもつ
753:１３２人目の素数さん
19/04/21 21:18:37.12 58cJHsba.net
すいません、不動点はあまり実りがなさそうなので撤退します。申し訳ない。
今1～2^nのコラッツ展開の先頭nビットを並べてコラッツ展開のkビット目にどのようなパターンが表れるかというのを見ようかと思ってます。
754:１３２人目の素数さん
19/04/21 21:54:43.91 58cJHsba.net
むむ、綺麗な周期が表れるかと思ったらそうでもない？
755:１３２人目の素数さん
19/04/21 22:53:56.35 58cJHsba.net
いや、周期になるみたい。
でもパターンは凄い複雑。
756: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-進整数ネタも一休み
また週末かなー
757:righ1113
19/04/26 08:31:01.99 RlIUNLEW.net
コラッツ展開のコラッツ展開をいくつか計算してみましたが、いまいちでした。
URLﾘﾝｸ(github.com)
-1, 0, 1だけが特別で、（>>686）
これ以外の数は、コラッツ展開を施すごとに、どんどん複雑になっていくようです。
「3x-1」シートは、3x-1にして負値を計算したものです。
758:１３２人目の素数さん
19/04/26 20:39:33.09 xTZynMFI.net
繰り返したら元に戻るとか、そういうことはない感じですかね
フーリエ変換に対する逆変換みたいなものが見つからないか、というのは今のところ夢想かなあ
759:１３２人目の素数さん
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の場合が示される.
760:righ1113
19/04/26 22:52:24.34 edmDBtkV.net
>>716
繰り返したら元に戻るとか、
小さくなる、とかだったら良かったですけどね。
761:１３２人目の素数さん
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).
系. コラッツ展開は単射.
762:１３２人目の素数さん
19/05/08 21:48:28.23 U/58yMQ3.net
コラッツ展開はかなりいい線いってるとは思うが、次の一歩が難しい？
763:１３２人目の素数さん
19/05/08 22:07:04.85 U/58yMQ3.net
例えばxのコラッツ展開のyビット目がxのサイズの多項式時間で求まれば
764:大きな前進と言える？
765:１３２人目の素数さん
19/05/08 22:10:31.84 U/58yMQ3.net
ここでいうxのサイズっていうのは自然数xに対してそれを表すのに必要なビット数log(x)のことね
766:righ1113
19/05/09 06:34:48.07 ysyHHFnM.net
>>721
入力サイズに対して、
コラッツ操作で何回2で割るかが分からないので、
難しいと思います。
特殊な場合だと、
2^n±1は、コラッツ展開のnビット目までを
多項式(定数?)時間で求められます。
767:１３２人目の素数さん
19/05/09 07:08:14.74 +tHX/zWL.net
個人的には
・Z(有理整数環)→(Z/2Z)の列 で単射になる
・>523の性質から、Z_2(2-進整数環)上にwell-definedに拡張できる
(環Zと素イデアル2Zの話が環Z_2と素イデアル2Z_2の話になるだけで、まったく同じロジックが展開できる)
・Z_2上全射(よって全単射)になる
ということでZ_2上で考えたらなんか出てこないかなー、とは。
コラッツ展開がループ
→一次方程式の解
→Q∩Z_2
とか。
なお、p-進整数環については、射影極限を経由するルートの方がわかりやすいかもしれません。
768:１３２人目の素数さん
19/05/09 08:06:12.63 +tHX/zWL.net
1ビットでも違うとそこから先は別物というか、カオス的な振る舞いをしますね
2で割ることで折りたたまれたフラクタル構造といいますか……
769:righ1113
19/05/09 08:26:35.55 c2RXSWlw.net
ところで、
>>686から書いている2-進整数とは少し違うものが英語版Wikipediaにあった。
URLﾘﾝｸ(en.wikipedia.org)
の"Iterating with odd denominators or 2-adic integers"
例えば、コラッツ展開(1011001)のループを考える。
このコラッツ展開の長さn=7で、"1"の個数m=4。
"1"のビット位置k_0,...k_(m-1)は、0, 2, 3, 6。
これらを元に、
(3^(m-1)*2^k_0 + ... + 3^0*2^k_(m-1))/(2^n - 3^m)
を計算すると、151/47になる。
この数を分数でコラッツ操作すると、
151/47 → 250/47 → 125/47 → 211/47 → 340/47 → 170/47 → 85/47 → 151/47 → ...
となって、確かにループしている。偶奇のコラッツ展開とも一致している。
(10)からは1が得られるし、(110)からは-5が得られる。
一つのループから一つの有理数が得られるようだ。
これも2-進整数って言うのかなあ。
770:１３２人目の素数さん
19/05/09 18:33:29.57 +tHX/zWL.net
2-進整数環Z_2においては、2Z_2の元でなければ可逆元となるので、47の逆元が2-進整数として存在します。
151/47と書くより151・47^-1と書く方が実情を正しく表現しているかもしれません。
また、加法・乗法は有理整数環上のものが延長されているので、分母が奇数の有理数についてはそのまま有理数として計算しても問題が発生することはありません。
771:righ1113
19/05/09 18:39:46.62 ysyHHFnM.net
ありがとうございます。
よく分かってないですが……
精進しますm(_ _)m
772:１３２人目の素数さん
19/05/09 19:13:07.75 yA5UfL3f.net
じゃあxのコラッツ展開のyビット目をもとめるのはNP困難か？
だったらどう？
773:１３２人目の素数さん
19/05/09 19:57:09.94 +tHX/zWL.net
分母が47の2-進整数は、
2^23-1 = 8388607 = 47×178481
であることから、
47^-1 が繰り返しが23桁の2-進整数となることがわかります。
具体的には
23桁の (11…1) = -1
であることから、
23桁の (10…0) = -1 × 47^-1 × 178481^-1
両辺に -1, 178481 をかけるという手順で求まります。
774:727
19/05/09 20:16:04.29 19c66qNB.net
NP困難がむりでも素因数分解とかグラフの同型問題とかに帰着出来たら一定の成果と言えると思う。
775:１３２人目の素数さん
19/05/09 20:21:22.85 19c66qNB.net
あれ、逆か？
素因数分解とかグラフの同型問題をコラッツに帰着できるか？
かな
776:１３２人目の素数さん
19/05/09 21:52:30.09 19c66qNB.net
自然数xのコラッツ展開のxビット目
777:、すなわちコラッツ展開の対角線に着目したら何か出てこないだろうか？
778:１３２人目の素数さん
19/05/09 22:16:54.60 19c66qNB.net
巨大数探索スレでは対角線というのは非常に注目されていて
ゲーデルの不完全性定理とかにもでてくる有用な概念らいしぞ。
779:１３２人目の素数さん
19/05/09 22:21:31.00 19c66qNB.net
例えば自然数xのコラッツ展開のyビット目をcollatz_bit(x,y)と置くとき、
collatz_bit(x,y)をxとyとcollatz_bit(z,z)で表すことが可能であれば、
本質的にコラッツの問題は対角線だけ着目すればいいという結論が出るかもわからない。
そうなったらちょっとすごい。
780:１３２人目の素数さん
19/05/09 23:11:30.02 19c66qNB.net
すまん、また先走ってしまったかもｗ
781:１３２人目の素数さん
19/05/11 00:46:16.20 fcymDsY6.net
>>719 の x-y∈(2^n)Z という式をみて、ユークリッドの互除法みたいにどんどん小さくしていけないかなぁとふと思った。
782:１３２人目の素数さん
19/05/14 16:53:13.29 8Q7VJT2b.net
藁
783:１３２人目の素数さん
19/05/30 21:36:43.15 cLyNr8Oe.net
さすがの>>1もここまで荒らされてしまってはギブアップか？
784:righ1113
19/05/31 07:22:26.05 v8IIjC8x.net
>>739
荒らされてる……?
証明はここにあります。
URLﾘﾝｸ(github.com)
割数列を使っています。
また、定理証明支援系Idrisを使用しています。
785:１３２人目の素数さん
19/07/23 20:59:18.66 9Y319zyX.net
藤林丈司
786:前786
19/07/31 22:27:24.78 IpAiLCvW.net
覗いてみたらコラッツ展開が注目されてて嬉しい。
コラッツ展開については私も色々考えていますが、>>546で書いた通り 3x+1 に限らず任意の px+q (p,q は奇数) で同様のことができるので、
3x+1 の特殊性をどう出すかが悩みどころ。
>>740
プログラムのことは良くわかりませんが、定理7-2 では 0 の全ての拡張完全割数列が有限項であることを示しているのですか？
787:righ1113
19/07/31 23:12:25.82 MdqshjyU.net
>>742
お久しぶりです。
最近プログラムに大きく手を入れたのですが、そこちょっと引っかかっていました。
示せてないです……
788:righ1113
19/07/31 23:36:04.76 MdqshjyU.net
1つ前のバージョンでは、レベルというものを導入していて、
『レベル2の』0の全ての拡張完全割数列が有限項であること
は実際に計算できたので、それを証明としていました。
789:前786
19/08/01 18:21:35.97 VR/ErDyu.net
>>743
やはりそうですか…。
了解です。
ついでに添削
ch01
・コラッツ予想
＞コラッツ操作をおこなう数を 「コラッツ値」 と呼ぶことにする。
既に同じ意味で「初期値」という言葉が使われているので「初期値」で統一してはどうでしょうか。
「コラッツ値」を残すにしても、『初期値のことを「コラッツ値」とも呼ぶ』などと定義した方が意味がはっきりします。
・定義1-1
これも分かりにくいので、
自然数 n を初期値としてコラッツ操作を連続して行ったとき、各操作において 2 で割った回数を並べてできる数列を n の割数列と呼ぶ。
とか。
有限列になる場合、無限列になる場合もここではっきりさせておくべき。
また、「コラッツ列」が未定義なので付け加えるか表現を変えるか。
・定義1-2
＞初期値が3の倍数の…
上で提案した定義に則るなら「初期値が」は不要。
このままにしたければ定義1-1を「初期値が n の割数列」に変更。
・3の倍数だけ調べれば良い
「コラッツ逆操作」が未定義。
ch02
・定義2-1
＞A[6,-4] or B[1,-2]をつける
「つける」では通じないので、
有限または無限数列 [a_1, a_2, a_3, ...] を数列 [6, a_1-4, a_2, a_3, ...] に写す変換を A[6,-4] と書く。
とか。
また、この時点ではまだ完全割数列を完全割数列に写すことが示されていないので、
その旨を削るか、書くとすれば「すぐ後で示すが」などと書き加えた方がいいと思います。
(重要)
・全ての3の倍数の奇数は、完全割数列で表わされる
ある数が完全割数列で表わされる、という文言がそもそもおかしいですが、
なにより 3 の倍数の割数列が完全割数列であるというのは完全割数列の定義そのもので、ここで示されることではありません。。
タイトルを何かしら変えるべきでしょう。ここで示されているのは
「star変換は完全割数列を完全割数列に写す」
「任意の完全割数列は、ある完全割数列にstar変換を施したものとして得られる」
です。
790:righ1113
19/08/01 18:38:18.77 mFTghELa.net
>>745
添削ありがとうございます。
すごく有難いです。
791:前786
19/08/01 18:51:35.06 VR/ErDyu.net
(重要)
ch03
コラッツ値が非負整数にならないものは禁止するのかしないのかはっきりさせて下さい。
禁止するならば、定義3-1は
n≧0 を 3 の倍数とする。整数列 [a_1, a_2, ...] が n の拡張完全割数列であるとは、
ある 3 の倍数 n'≧0 が存在して
・n' の割数列に、0 や負数が現れることも許してstar変換を有限回施すと数列[a_1, a_2, ...] が得られ、かつ
・n' に対応するコラッツ値の変換を施すと n が得られる
を満たすことを言う。
ってところですかね。
(重要)
ch04
「拡張コラッツ予想」とありますが、これは操作を定義しているだけで予想になっていません。
「拡張コラッツ操作」などと呼ぶべきでしょう。また、ここでも「1回の操作」をはっきり定義しておくといいでしょう。
拡張コラッツ予想とは
任意の拡張完全割数列は有限項である。
とかでしょうか。
あとはプログラムが分からないのでパスで
792:righ1113
19/08/10 16:30:41.61 WEEBIQI2.net
>>745
プログラムを変更して、
帰納法のbase caseは、『（拡張でない）完全割数列が有限項』を示せば良いようにしました。
0の完全割数列は[]と定義するので、有限項です。
793:前786
19/08/16 19:31:46.97 2gnceVey.net
どう改善したんです？
794:righ1113
19/08/17 09:46:57.28 /+c7d2Vv.net
すみません、2~3日まってください。
795:righ1113
19/08/18 20:20:16.33 /T55OTnz.net
すみません、もうしばらく時間をください。
796:righ1113
19/08/21 08:04:36.17 1YNIVvH6.net
GitHubのWikiとprogram3は直しかけです。
証明の流れは以下です。
①まず、二つの述語を用意します。
FirstLimited x ： xの完全割数列は有限長である
AllLimited x ： xの完全割数列および拡張完全割数列達は全て有限長である
示したい命題は、x -> FirstLimited x です。 ---(a)
②次に、パースの法則の述語論理版を用意します。
"∀x::nat. ￢(∀z::nat. (P z -> Q z))
-> (∀z::nat. (P z -> Q z) -> (∀n::nat. P n))
-> P x"
これは定理証明支援系Isabelleで自動証明したので間違いないと思います。
③(∀z::nat. (P z -> Q z) -> (∀n::nat. P n))
のP, QにFirstLimited, AllLimitedを代入したものを証明します。
無限降下法はやめて、整礎帰納法を使います。
④ (x -> FirstLimited x -> AllLimited x) は、排中律により真か偽のどちらかです。
・真の場合
これと③を使って(a)が証明できます。
・偽の場合
これと③とパースの法則を使って(a)が証明できます。
797:１３２人目の素数さん
19/08/21 19:42:19.19 D7jjX8DP.net
>>752
> 示したい命題は、x -> FirstLimited x です。 ---(a)
？？？
x は単なる自然数でしょ？ なのに、x -> ・・・ と含意命題の仮定部に出て来るとは？？？
示したい命題って、AllLimited x -> FirstLimited x ですか？
798:righ1113
19/08/21 20:01:27.13 1YNIVvH6.net
>>753
プログラムで「x ->」と書いたら、全称量化を意味します。
参考記事です。
URLﾘﾝｸ(mandel59.hateblo.jp)
799:前786
19/08/21 21:08:20.89 fPaJwHz3.net
となると④の命題は
任意の自然数xに対して「FirstLimited x ならば AllLimited x」
ですか。
②
800:は 命題 -> 命題 -> 命題 の形になってるけどどういう意味？
801:righ1113
19/08/21 21:21:49.59 1YNIVvH6.net
②は
「任意の自然数xに対して、α -> β -> P x」
α：￢(∀z::nat. (P z -> Q z))
β：((∀z::nat. (P z -> Q z)) -> (∀n::nat. P n))
です。
802:righ1113
19/08/21 22:11:29.10 1YNIVvH6.net
＞ 命題 -> 命題 -> 命題
は、
十分条件1 -> 十分条件2 -> 命題
と書いても良いと思います。
803:前786
19/08/21 22:37:59.72 fPaJwHz3.net
A -> B -> C は
・「A ならば B」かつ「B ならば C」
・「A ならば B」ならば C
・A ならば 「B ならば C」
のどれかかと思ったけど
・「A かつ B」ならば C
ってこと？
804:前786
19/08/21 22:41:32.77 fPaJwHz3.net
あ、それとも
・「A または B」ならば C
ですか？
805:righ1113
19/08/21 22:44:55.92 1YNIVvH6.net
>>758
・A ならば 「B ならば C」
です。
（右結合といいます）
806:前786
19/08/22 01:12:58.29 giLkMHnx.net
分かりました。
あとは③の証明がちゃんとできてるかどうかですね。
807:１３２人目の素数さん
19/08/22 03:04:34.92 nw1u5r5f.net
>>754
はぁ～、依存型サポートしてる関数プログラミング言語のIdris独特の記法なのね、、、
808:righ1113
19/08/22 06:55:11.10 PJ5J9TL4.net
②の括弧の書き方が怪しいようです。
見直します。
809:前786
19/08/23 11:36:02.85 Zs0jDKxG.net
>>756の記号を使うと、②は
α：￢A
β：A -> B
の形をしていて、α が真なら β も常に真、したがって β があってもなくても変わらない
となってしまっているように見えますが、これも括弧の書き方のせいですかね。
810:righ1113
19/08/23 20:08:10.05 eq9wFyaJ.net
>>764
>>756は間違いでした。
自分が不用意に括弧を付け足したせいです。
(Isabelleも>>756にはNGを返します)
正しくは以下です。
「任意の自然数xに対して、α -> β -> P x」
α：￢(∀z::nat. (P z -> Q z))
β：(∀z::nat. (P z -> Q z) -> (∀n::nat. P n))
しかしこれだと、βに(∀z::nat. (P z -> Q z))を渡せないので、
コラッツ予想の証明には使えません。
811:righ1113
19/08/24 03:54:12.96 y6gPu1qv.net
②のαを少し変えて
「任意の自然数xに対して、α -> β -> P x」
α：(∀z::nat. ￢(P z -> Q z))
β：((∀z::nat. (P z -> Q z)) -> (∀n::nat. P n))
とすると、IsabelleもOKを返します。
これを使って上手いこと出来ないか考え中です。
812:righ1113
19/08/31 17:08:17.30 maX3S4cO.net
すごく時間がかかりそうです。
813:righ1113
19/09/04 14:27:10.54 0SsvI0JE.net
>>752の③からIdrisで直接(∀n::nat. FirstLimited n)を証明できる
目処が立ちました。
パースの法則は使わずに済みそうです。
Isabelleも使わずに済みそうです。
Idrisプログラムを書き上げる事とWikiを手直しする事が必要ですが、
3か月くらいかけてじっくり取り組もうと思います。
814:righ1113
19/09/11 08:56:27.39 eEtvbVM0.net
テレンスタオ氏によって
コラッツ予想に進展があったみたいですね。
815:１３２人目の素数さん
19/09/11 20:39:58.57 bzYg9Jhl.net
まじで
詳しく
816:１３２人目の素数さん
19/09/11 20:45:42.89 xhfGTjEt.net
URLﾘﾝｸ(terrytao.wordpress.com)
817:１３２人目の素数さん
19/09/11 20:54:44.39 bzYg9Jhl.net
>>771
分らんということが分かった
818:前786
19/09/11 21:26:42.43 8GdAP/RF.net
とりあえず出だしだけ見てみた。
この結果は Korec の結果を一般化(厳密にはちょっと違う)したもの。
・Korec の結果
自然数 N を初期値としてコラッツ操作を施して得られる数の最小値を Col_min(N) と書く。(コラッツ予想が正しければ常に Col_min(N)=1)
このとき、ほとんどすべての自然数に対して Col_min(N) < N^θ (ここで θ=(log3)/(log4)) が成り立つ。
「ほとんどすべての」というのは数学用語で、密度というものを使って定義される概念。
密度には種類があり、異なる密度に対しては「ほとんどすべての」の意味が異なる。
Korec が用いたのは natural densit
819:y (自然密度？) というもの。 ・Terence Tao の結果 上の N^θ の部分を一般化したもの。 f を自然数に対して実数を対応させる関数で、lim_[N→∞]f(N)=∞ を満たすものとする。 このとき、ほとんどすべての自然数に対して Col_min(N) < f(N) が成り立つ。 ただし、Korec とは異なり logarithmic density (対数的密度？) という密度を用いている。
820:１３２人目の素数さん
19/09/11 22:35:47.47 bzYg9Jhl.net
カンタン言うと無限大には多分発散しないよってこと？
821:１３２人目の素数さん
19/09/11 22:42:30.82 bzYg9Jhl.net
じゃなくて必ず元の値より小さくなるよってことだろうか？
822:１３２人目の素数さん
19/09/11 22:52:04.32 bzYg9Jhl.net
Col_minってなんか微妙な表現だな。
Col_minの上限が言えても無限大に発散しないことは言えなくない？
823:前786
19/09/12 00:31:35.05 HO87Fd5n.net
5ページの (1.8) に現れる数列は割数列(の最初のn項)ですね！
論文では n-Syracuse valuation と名付けられています。
その後「n-Syracuse valuation と n-Syracuse offset map について理解する必要がある。前者のために…」というくだりがあって次の話に続いているようです。
これ割数列がなかなか活躍してるのでは。
824:１３２人目の素数さん
19/09/12 06:51:26.68 KFZB1fcL.net
>>776
そのとおり。無限大に発散しないことは言えない。
個人的には、この手法を応用して
・ an＋b問題(ただしa≧5)ではほとんどの初期値で発散する
という予想が証明できることを期待したい。
・・・と思ったが、ブログのコメント欄を見てみると、
Tao氏本人が「今回の手法ではムリ」と書いていた。
どんだけ闇が深いんだこの問題ｗ
825:１３２人目の素数さん
19/09/17 21:04:04.67 umydRiIr.net
なんか言葉では表せないが、3n+1の抜けがないことを証明出来ないか。
URLﾘﾝｸ(i.imgur.com)
826:righ1113
19/09/18 10:45:47.10 X1ldMZz+.net
>779
Excelで書いてみました。
URLﾘﾝｸ(github.com)
（Downloadボタンを押してください）
ここから先はよく分からないのですが、
3の倍数の×印で全て覆える、という事でしょうか？
827:１３２人目の素数さん
19/09/18 12:14:52.09 Q9zF2o5s.net
>>780
ありがとうございます。
論文を見てそう考えました。
スラッシュしてあるのは前項により固定になっている所です。
それで固定になっていない所の位置変化に注目してます。
2^nになれば収束するので2^nの位置変化と3n+1の箇所が2^nを内包するn^2のシートを使われているかもと考えました。
828:righ1113
19/09/19 07:31:26.58 Ro0nf9Vh.net
すみません。返信遅くなります。
829:779です
19/09/19 15:32:22.38 MvMcPhmF.net
追記
3n+1がどのような代謝をするか考えると3n+1は初期のn/2は代謝させないで
後半のn/2をすべて代謝させるだけで初期のn/2で深度？がわかるようなそうじゃないような…
URLﾘﾝｸ(i.imgur.com)
830:righ1113
19/09/20 04:18:16.82 3y2eEA/C.net
>>781
Excel更新しました。......が、あまりうまくいかないです。
3*奇数+1
はn^2正方形の辺上に並ぶかと思いましたが、違うようです。
>>783
OE : (3/2)n+1
が何故3n+1になるか分からないです。
831:779です
19/09/20 06:11:25.81 mz9+bxEb.net
お疲れ様です。
16がうまくいってるだけで正方マスはうまくいかないのかもしれないです。結局変化おこるのが斜めにずれて噛み合ってになるので2^nマスでしか起こらないのかもしれないです。
もうひとつの方なにやら壮大な計算ミスが起こっているようですごめんなさい。
832:１３２人目の素数さん
19/09/20 13:37:10.76 KyAOfC1j.net
3715
かずきち@dy_dt_dt_dx 8月28日
学コン8月号Sコース1等賞1位とれました！
マジで嬉しいです！
来月からも理系に負けず頑張りたいと思います！
URLﾘﾝｸ(twitter.com)
(deleted an unsolicited ad)
833:１３２人目の素数さん
19/10/03 20:20:37.21 PRx2pJec.net
なんかワケわからんくなってきた。
コラッツ予想ってどうなれば解けると言えるんだ？
834:１３２人目の素数さん
19/10/03 21:26:46.49 p16UL9SE.net
反例を見つけるか、すべての自然数がコラッツ操作によって１に収束することがいればいい。
835:BLACKX
19/10/03 21:49:54.55 PRx2pJec.net
そうか。とりあえずこれ見て。
どう思う？
URLﾘﾝｸ(i.imgur.com)
URLﾘﾝｸ(i.imgur.com)
URLﾘﾝｸ(i.imgur.com)
836:１３２人目の素数さん
19/10/03 22:32:42.14 p16UL9SE.net
これでエスパーするのはかなり厳しいｗ
837:BLACKX
19/10/03 23:04:43.87 Rbe16hSc.net
整数を代入した表通りに辿ると各整数で計算した値になるからそのままグラフにして座標のもう片方の数字を辿ってみた。
初めの数字はy座標から始めてyxyxと交互に座標を辿るとコラッツ数になる。
x/2だけは逆数でもたどれるからy=2xを介しても良い(逆数を介さなくてもそのまま行ける)
だから座標上の数列3式で全て対応可能だと思うよね。
というか対応可能じゃないと代入しただけだから困るが。
矢印の線は一例
838:righ1113
19/10/04 21:32:06.44 UHkJbXE/.net
>>791
スプレッドシートで描いてみました。
URLﾘﾝｸ(docs.google.com)
こういう形の図はコラッツ予想ではよく見るのですが、
＞ yxyxと交互に座標を辿るとコラッツ数になる。
という所は新しいかも、と思いました。
839:BLACKX
19/10/04 23:02:42.16 ZbCHQ69z.net
>>792
斜めのx/2介さない方が一貫性あるかなと思うんだが、この法則で1に収束すると言えないかな
840:righ1113
19/10/04 23:29:24.49 UHkJbXE/.net
>>793
う～ん、1に収束するかどうかは何とも言えないですねぇ。
もう少し、1に収束する根拠というか、詳細を書いてもらえないでしょうか。
841:BLACKX
19/10/04 23:31:03.67 ZbCHQ69z.net
URLﾘﾝｸ(i.imgur.com)
なんかこういう感じの式で見たらメルセンヌの素数判定式と同じ類いの証明が出来そうな気がする。
それはコラッツ問題においてはn/2は0が原点となるし、3n+1は(1.0)もしくは(0.1)を取り問題帰着するし、
何処の座標でも合同の距離ベクトルであると言えるから代謝構成も同じと言えないか？
息抜きでかじった程度なので分からんが。
842:righ1113
19/10/04 23:41:27.20 UHkJbXE/.net
>>795
すぐにはコメントできないですねぇ。
じっくり考えてみます。
843:BLACKX
19/10/05 01:38:10.80 OL94vrVV.net
移動座標
xyは座標目盛り
40x、20y、10x、5y、16x、8y(真横)、4x
、2y(真横)、1x(END)
は並べかえると、
x:40、10、16、8、4、1
y:20、5、8、2、
ベクトル距離は、
x:-30、6、-12、-2、2
y:-15、3、-6、2、-3
(x.y)=(-19.-36)で初め(40.20)からでENDの読みがXだからyからxを足すと1が出てくるな
844:BLACKX
19/10/05 01:43:14.54 OL94vrVV.net
まぁ、操作そのものだから自明だが
845:righ1113
19/10/05 03:16:11.20 EPlAKeUQ.net
5x+1のループを描いてみました。÷2の描き方は変えてあります。
10, 5, 26, 13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13, ...
URLﾘﾝｸ(docs.google.com)
シート2です。（見づらくてすみません）
3x+1でもこのような可能性があるので、難しいと思いました。
846:BLACKX
19/10/05 09:09:17.25 uoHvpmE8.net
ちょっとかんがえてみるわ
でも5x+1の時は特殊性あって16で限定でx/2に対応する式だと思う。
そういう計算をしてるブログあるしトリガーを16で持たせたと言って過言じゃないと思う
xy対応グラフはn/2と3n+1限定の対応グラフだからトリガーがy=n/2とy=2xとy=x/3-1/3しか対応してない。
それは(-2.-1)の共有点もって無いと対応しない。y=2xの共有点はx/2
逆数なので、x=y
847:１３２人目の素数さん
19/10/05 13:04:34.60 fDQh4Kkd.net
>>791
分岐するところはどうなるの？
848:１３２人目の素数さん
19/10/06 04:55:26.48 nni1fM7t.net
2n+1→6n+4→3n+2
2n+2→n+1
どちらも和は4n+3で同じ
奇数と奇数+1の2つの数を変換しても和は保存された
849:BLACKX
19/10/06 10:57:34.94 X1pstQ7F.net
>>801
x=16の直線上に5、8、32は同じ直線上に居るようにxだけ読めればyの値を読むのでちゃんと結ぶよ
850:BLACKX
19/10/06 17:59:01.95 X1pstQ7F.net
なるほど。
ちょっと今日分かったとこワードで纏めるわ
851:BLACKX
19/10/07 04:21:08.42 zHCD2zLI.net
コラッツ小予想
URLﾘﾝｸ(dotup.org)
852:righ1113
19/10/07 08:58:21.68 H+XdBCjD.net
>>805
なるほど、4本の直線の間をぐるぐるしながら遷移するのですね。
4-2-1ループは例えば、
(2,1)→(4,1)→(4,2)→(1,2)→(1,4)→(2,4)→(2,1)→...
と遷移すれば良いかなと思いました。
853:BLACKX
19/10/07 18:56:22.72 6TY/9fav.net
>>806
そかそか、見落としとった
1は3n+1か！
854:１３２人目の素数さん
19/10/07 19:12:42.63 BmUoT7kv.net
コラッツ問題の定義に従えば
y=x,3x+1,x/2の3本の間を
3x+1→x
↑奇数
x
↓偶数
x/2→x
とx軸/y軸方向に行ったり来たりすることで表現できる
これを適宜y=xで反転して
・y=xで曲がらない
・折り返すところを省略
とやってる感じですかねー
855:righ1113
19/10/07 22:48:48.15 H+XdBCjD.net
>>808
そのような感じだと思います。
856:BLACKX
19/10/08 15:08:09.01 TzPmIY36.net
>>808
逆数の式の線上の座標が経由されてるのがよくわかりませんが、値が保存されるので収束するのがよくわかります。
857:前786
19/10/08 17:35:41.71 cGIo+lIN.net
y=3x+1, y=(1/3)x-(1/3) を奇数ライン
y=2x, y=x/2 を偶数ラインと呼ぶことにすると
奇数ラインからは偶数ラインにのみ移る。
この際、近い方の偶数ラインに向かって、原点から離れる方向に進む。
偶数ラインからは奇数ライン、偶数ライン両方に移り得る。
奇数ラインに移るときは上と同様、近い方の奇数ラインに向かって、原点から離れる方向に進む。
偶数ラインに移るときは原点に近づく方向に進む。
という動き方になっていますね。
外側で増加、内側で減少を繰り返していることになります。
あと個人的には、奇数に対して「3倍して1を加えて2で割る」までをひとつの操作とした場合どうなるか、というのも気になります。
858:BLACKX
19/10/08 20:24:00.32 nAoQTulA.net
あ、もう反例や否定意見が出てこないから、
さらに色々またワードに纏めるわ
今度はかなり遅れます。
859:１３２人目の素数さん
19/10/08 20:52:45.13 Ypehd4ey.net
よくわからんが期待できそうなの？
860:BLACKX
19/10/09 07:59:04.51 bxDyrUTc.net
>>813
次はこのスレの住人なら自分の頭の中を全部吐き出せば何か他の法則が見つかるのかなって感じ。まだ頭の中整理出来てないから1週間位掛かるかも
861:righ1113
19/10/09 09:48:49.82 QvxcI3Gv.net
>>811
偶数ラインの外側で増加、内側で減少しているのですね。
それとはちょっと違うかもですが、コラッツ操作で1に辿り着く時は、
『始点=3の倍数の奇数』
『最大点』
『終点=1』
の三つのポイントがあって、
『始点』→『最大点』を<上り>のフロー
『最大点』→『終点』を<下り>のフロー
として遷移するのかなあと思いました。
862:BLACKX
19/10/11 00:23:27.71 a9ESd36D.net
ちょっと教えてください。
5n+1ではy=2xとなる点は無いの？
863:righ1113
19/10/11 03:30:35.31 tbnZSvvM.net
>>816
>>805にならえば、
例えば5n+1で1→6→3→16→8→4→2→1→...は、
(2,1)→(6,1)→(6,3)→(16,3)→(16,8)→*(4,8)→(4,2)→
→*(1,2)→(1,6)→*(3,6)→(3,16)→*(8,16)→(8,4)→*(2,4)→(2,1)...
となって、印をつけた点がy=2x上にあります。
864:BLACKX
19/10/11 08:35:19.48 a9ESd36D.net
>>817
なるほど。ありがとうございます。
それなら3n+1も同一処理になりますね
865:righ1113
19/10/16 15:34:21.23 OTKtaZgW.net
>>768
うまくいきません。
「3か月で完成させる」は撤回します。
現状
----------
(ロ)二つの述語を用意します。
P(d, n) : FirstLimited(d, n) : nの完全割数列は有限長である
Q(d, n) : AllLimited(d, n) : nの完全割数列および拡張完全割数列達は全て有限長である
示したい命題は、∀d.∀n.FirstLimited(d, n) です。 ---(a)
(ハ)補題を二つ証明します。
makeFtoA : ∀d.∀n.(∀z.P(d, z) -> (P(d, n) -> Q(d, n)))
makeLimitedDivSeq : ∀d.∀n.(∀z.(P(d, z) -> Q(d, z)) -> P(d, n))
※これは達成できました。
(ニ)
補題を使って、(a)を、相互再帰で証明します。
※ここがうまくいきません。
----------
866:BLACKX
19/10/22 11:27:16.05 iR/Ln1SE.net
ベクトルの面積で処理するのかなり難しい
ループするときの数式処理が難しくて結局0ベクトルになるから厳しかった。まだ諦めないけど
867:righ1113
19/10/22 12:04:20.87 QXGkAQTT.net
ベクトルの面積を処理しているのですか。
かなりオリジナリティ溢れる展開ですね。
868:１３２人目の素数さん
19/10/23 20:35:42.05 18OXj+iw.net
この場合の面積ってコラッツ問題における何の量を表しているんだろう？
869:righ1113
19/10/23 20:40:22.71 pRP9XRPU.net
>>822
う～ん、パッとはひらめかないですねー。
870:BLACKX
19/10/24 07:41:48.24 sFNWgaFI.net
ぐちゃぐちゃだけど雰囲気だけとりあえず見てくれ
確定だと思われる所まで貼るよ
結局ループ場合AnとDnはx=yで同じにならんといけないので固定
BnとCnの係数比になるから交点からの面積求めて差分の面積を係数比較したかったけどそこの所は無理っぽさがあった
URLﾘﾝｸ(i.imgur.com)
URLﾘﾝｸ(i.imgur.com)
URLﾘﾝｸ(i.imgur.com)
URLﾘﾝｸ(i.imgur.com)
871:righ1113
19/10/24 09:41:18.27 0pxG9RqR.net
う～ん......
雰囲気はつかめます。
872:BLACKX
19/10/25 07:20:11.74 n41S92Ki.net
一枚貼れてなかったすまぬ。
それとベクトルの向きと操作は前のは間違ってる。すまん
これが正しい
URLﾘﾝｸ(i.imgur.com)
873:BLACKX
19/10/27 15:29:41.06 7c/8AR0O.net
やっとワード起こしました。
URLﾘﾝｸ(dotup.org)
874:righ1113
19/10/27 18:02:21.62 IamAjedT.net
>>827
ベクトルのところは、以下のように計算するのかな、と思いました。
（何も言えないですけど）
B→C：(0, -3)
C→D：(2, 0)
D→C：(0, 1)
C→B：(-3, 0)
B→A：(0, 2)
A→B：(1, 0)
--------------
総和：(0, 0)
875:１３２人目の素数さん
19/10/27 19:28:31.04 CU+gc259.net
>>827
ベクトルじゃなくて座標系スキームやな
876: あとなんで複素平面の所y/2xなん？ >∴arg[z]=arctan(y/x) if x>0 >arctan(y/2x)+π if x<0 and y>=0 >arctan(y/2x)-π if x<0 and y<0 ここはx/2で見てる訳じゃないので ∴arg[z]=arctan(y/x) if x>0 arctan(y/x)+π if x<0 and y>=0 arctan(y/x)-π if x<0 and y<0 Π/2 if x =0 and y>0 -Π/2 if x =0 and y<0 になると思うで
877:BLACKX
19/10/27 19:29:16.75 7c/8AR0O.net
>>828
そうですね！書いてるのベクトルじゃないじゃんってことですよね。ごめんなさい。ただの座標で書いてるのにベクトルって書いてますね。
(2.4)→(2.1)の４→１の時と同じような未知数で増減ループの場合以下となると思ったのでこれにしました。
B→C：(0 , y/3 - 1/3)
C→D：(2x , 0)
D→C：(0 , 2y)
C→B：(y/3 - 1/3 , 0)
B→A：(0 , 2y)
A→B：(2x , 0)
878:BLACKX
19/10/27 21:42:42.87 7c/8AR0O.net
>>829
arctan(y/x)+πだと第一象限？全体を示すような気がして...
ｙ＝ｘ/2～ｙ＝2ｘまでを差したい場合はどうしたら...うーむ
879:１３２人目の素数さん
19/10/28 12:50:52.20 2jX/JBjG.net
シンプルに疑問なんだけど、ここでそういうアイディアを書きながら証明するの怖くないの？普通に盗まれる気がするんだけど
880:righ1113
19/10/28 19:28:48.66 hZDz/HM9.net
>>832
自分はこことGitHubに上げてるのですが、
GitHubのソースコードにはライセンスを付けているし、
全ての更新記録と日時が残っているので、
なんとかなるんじゃね?、って感じです。
881:BLACKX
19/10/28 19:45:33.06 oH5Lh31p.net
>>832
自分は数学板に10月頭からまだ心臓部のアイデアを載せていません。
人のアイデアを盗むのと自分のアイデアで書き上げてジャーナルに出すのどっちのほうが正確で早いでしょうか？
ちなみに自分のアイデアは自分の中の解決済みの穴については触れていません。小予想うｐろだから消え得ちゃったし誰も気づかんやろって感じです。
882:１３２人目の素数さん
19/10/28 20:47:31.08 RpX1u6Bc.net
ここの2人ガチガチのライバルやん
883:BLACKX
19/10/28 21:28:57.33 oH5Lh31p.net
ライバルだなんて////
righ1113さんすなば珈琲でお茶会しましょ////
884:righ1113
19/10/28 21:52:29.58 hZDz/HM9.net
嬉しいのですが、
ちょっと遠いです...(*_*)
885:１３２人目の素数さん
19/11/01 18:02:56.92 Ceaoafi6.net
URLﾘﾝｸ(i.imgur.com)
886:１３２人目の素数さん
19/11/03 20:08:27 1cBnE+o6.net
進展は？
メビウスの輪の二回巻きも普通のメビウスの輪とは違うように8の字型で2重のとかループありそうだけどその辺どうなんだろ
887:１３２人目の素数さん
19/11/04 13:00:07.73 1D686fWA.net
>>839
1つの項は最大2つの前項を持つけど次項は常に1つしかないから8の字にはならない
888:１３２人目の素数さん
19/11/04 18:25:32.54 v76/uzJo.net
>>840
常に一つ？
x/2と3x+1の値が同じ所は分岐するけど2回続いたら4つ取れるよ？
そしたら1つコラッツ数被るんじゃない？
889:righ1113
19/11/04 21:02:17.79 DOdDoHKE.net
>>841
こういう事だと思いますが、
→・→...→・→
↑ ↑
流入矢印3つ、流出矢印1つなので、
（準）8の字も作れないと思います。
890:BLACKX
19/11/05 19:29:36.23 jPz5EJSm.net
>>841
皆さんの言うとおりコラッツ座標はコラッツ数を1つずつ受けついていくので二重にはなりません
あと継承の構造上2xよりも大きい数枝分かれが起こりません
継承が2重で行われる場合単独のループとなりますから、ループ因子を持ってる事になりますし、4214のループに継承される以外の関数が合同変換される事になります
891:righ1113
19/11/10 09:24:44.20 sNj6byvw.net
>> 817
割数列を使った証明もうまくいかないので、
自分はコラッツ予想をギブしようと思います。ありがとうございました。
次スレもいらないかな。
892:BLACKX
19/11/10 12:48:23.59 lMUTtZWo.net
>>844
残念です。
お疲れさまでした。
righ1113様に代わりましてBLACKXがお送りします。
次スレは1さんの意向により無しの方向で。
現在次元拡張での証明で書き切り、校正業者に投げてあります。
893:１３２人目の素数さん
19/11/10 13:38:13.84 euFsC3j+.net
>>1
いつでも戻ってきていいんやで
894:１３２人目の素数さん
19/11/13 00:25:46.51 EstW1i4s.net
スレ主また気が向いたら戻って来てな
BLACKX氏、あららもう出しちゃったかい？
もう遅いかもしれんが偏角はどうなった？
座標の移動先についての範囲を決めるならA→B間、B→C間、C→D間の3つ必要になるんじゃないかな。でもそれが1に帰着するか因数が変動するから言えないんじゃない？
895:１３２人目の素数さん
19/11/14 22:10:17.42 BkKMP99D.net
VIPから見つけた
どっか間違いあるんじゃないの？
とりあえず乙
896:１３２人目の素数さん
19/11/19 15:42:34.55 OAfgULHP.net
藤林丈司
897:１３２人目の素数さん
19/11/20 09:22:26.73 QcCuZ2iX.net
複素実数ｚ=x+iyでy=0でｘが偶数だとx/2、xが奇数だと3n+1になるような
関数 z'=f(z)を見つけて（作って）、その関数の挙動を調べる方法はなし？
898:１３２人目の素数さん
19/11/20 21:10:52.69 YLPClUAA.net
作れるもんなら作ってみろ
899:前786
19/11/20 23:10:45.11 m8ua4B6f.net
>>850じゃないけど
f(z)=((3z+1)/2)*(1-cos(πz))+(z/4)*(1+cos(πz))
実際にどこかの文献で使われてたと思う
900:前786
19/11/20 23:32:54.08 m8ua4B6f.net
ありました
URLﾘﾝｸ(www.auemath.aichi-edu.ac.jp)
901:BLACKX
19/11/21 01:15:54.70 uBoD5cGh.net
>>850
y→xの場合のみZ'(x)で立てることが出来ますのでx→yの場合をフーリエ変換して複素的にどうぞ。
私のは(clatzX,clatzX')を使ってやってるのでp←qを満たせなくて校正添削の時点でNGだったので諦めましたので是非どうぞ。
902:BLACKX
19/11/21 01:57:42.98 uBoD5cGh.net
現在私は複素アプローチをやめて相似構成でループがないことの幾何学的証明に修正してます。
903:１３２人目の素数さん
19/11/25 22:56:50.63 /48kvYYK.net
>>852をテイラー展開すると何か出てきたりするのだろうか？
904:BLACKX
19/11/26 14:07:46.50 ZJEd3fmX.net
>>856
近似はするからやってみると良いと思う
俺の頭が空っぽなだけかもしれないけど収束性は言えない気がする。
905:１３２人目の素数さん
19/11/26 19:44:26.91 QD/pL8A5.net
>>857
wolfram alpha 先生 に教えてもらった。
1/4 (2 + 7 z - (2 + 5 z) cos(π z)) = 1/4 (2 + 7 z - (2 + 5 z) sum_(k=0)^∞ ((-1)^k π^(2 k) z^(2 k))/((2 k)!))
ここから何か言えるかどうかは全くアイディアなしｗ