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

**righ1113** ◆OPKWA8uhcY · 2018/05/10(木) 22:10:23.74

コラッツ予想に挑戦するスレです。

前スレ　コラッツ予想がとけたらいいな
https://rio2016.5ch.net/test/read.cgi/math/1350178359/

>>1の証明（未検証）
https://github.com/righ1113/collatzProof

それより弱い成果もあります（未検証）
コラッツのループはあるとしてもとても長い
https://github.com/righ1113/collatzLongLoop

**M.B.** · 2018/07/26(木) 12:57:15.46

そのあたりの議論については、たぶん
>>113-116
あたりの話につながりそうに思うので、
そこいらからツッコミをいれてくれると
分かりやすいと思います。

**前786** ◆5A/gU5yzeU · 2018/07/26(木) 17:31:49.36

>>516の命題を証明します。

以降、奇数に対しては「3倍して1を足して2で割る」までをひとつの操作とします。
また、面倒な条件付けを避けるため、整数の範囲で考えることにします。(さらに広げることもできますが、省略します)
コラッツ操作を f で表します。

まず、後で使う補題をひとつ用意します。

補題
任意の整数 a,k に対して、f(a+2k)=f(a)+ck, ただし c=1 or 3

証明
a が奇数の場合
　f(a+2k) = (3(a+2k)+1)/2 = ((3a+1)/2)+3k =f(a)+3k
a が偶数の場合
　f(a+2k) = (a+2k)/2 = (a/2)+k = f(a)+k □

次に「コラッツ展開」を定義します。
（私が勝手に作った言葉であり、一般的な言い方ではありません）

定義
整数 a に対して、数列 {a[n]} を
　a[1]=a
　a[n+1]=f(a[n]) (n≧1)
によって定める。
次に、0 と 1 からなる無限列を
　a[n] が偶数なら第 n 項は 0、a[n] が奇数なら第 n 項は 1
として構成する。
こうしてできる無限列を a のコラッツ展開と呼ぶことにする。

例えば a=5 のとき数列{a[n]} は
　5,8,4,2,1,2,1,2,…
となるので、5 のコラッツ展開は
　1,0,0,0,1,0,1,0,…
となります。

一般に、f(a) のコラッツ展開は a のコラッツ展開の初項を除いたものになります。

**前786** ◆5A/gU5yzeU · 2018/07/26(木) 17:32:25.15

補題
a,b を整数とする。このとき
　a と b のコラッツ展開が少なくとも第 n 項まで等しい ⇔ a≡b (mod 2^n)

証明
n=1の場合
　コラッツ展開の初項が等しい ⇔ a と b の偶奇が等しい
より成り立つ。

n=m まで成り立つとして、n=m+1 の場合を示す。

左⇒右:
少なくとも第 m 項まで等しいので、ある整数 k を用いて
　a=b+2^m*k
と表せる。a,b にコラッツ操作を m 回施して得られる数を a', b' とすると、前補題より
　a'=b'+3^e*k　（e は非負整数）
と表せる。仮定より、a' と b' の偶奇は等しいので k は偶数。
よって a≡b (mod 2^(m+1))

右⇒左:
整数 k を用いて
　a=b+2^(m+1)*k
と表せる。a,b にコラッツ操作を m 回施して得られる数を a', b' とすると、前補題より
　a'=b'+3^e*2k　(e は非負整数)
と表せる。よって、a' と b' の偶奇は等しいので、a と b のコラッツ展開の第 m+1 項は等しい。□

系
整数 a,b に対し、両者のコラッツ展開が一致するならば a=b

**前786** ◆5A/gU5yzeU · 2018/07/26(木) 17:32:59.15

>>516の命題の対偶を証明します。

命題
整数 a のコラッツ展開が、有限個の項を除いて循環しているとする。
このとき、a にコラッツ操作を繰り返し施すとループに到達する。

証明
a のコラッツ展開が第 n 項から循環しているとし、k 項ずつ繰り返しているとする。
このとき、a にコラッツ操作を n 回施して得られる数を b、
a にコラッツ操作を n+k 回施して得られる数を c とすると、
b と c のコラッツ展開は一致するので、系より b=c
したがって、a にコラッツ操作を繰り返し施すとループに到達する。□

**１３２人目の素数さん** · 2018/07/26(木) 18:39:32.05

ん、なんか上手くいき過ぎな気がするが
かといって間違えを指摘できるわけでもない
ちょっと考えてみます

**M.B.** · 2018/07/26(木) 19:00:28.10

うん。概念的に理解しやすいのがいい。
久々のビッグウェーブが来た予感。
今後の展開に期待。

**１３２人目の素数さん** · 2018/07/26(木) 19:09:16.60

>>1の目にはどう映る？
上手くいき過ぎじゃね？

**１３２人目の素数さん** · 2018/07/26(木) 20:35:49.91

たとえばだけど任意の有限長の01列に対してそのコラッツ展開をもつ整数が存在する
とかは言えるの？

**１３２人目の素数さん** · 2018/07/26(木) 20:45:09.99

ちょっと言い方がおかしいか
任意の有限長の０１列（長さｎ）に対してコラッツ展開の初項から第ｎ項が一致する整数が存在する
はいえるの？

なら通じるかな

**前786** ◆5A/gU5yzeU · 2018/07/26(木) 21:30:21.51

>>527
これは言えます。

1 から 2^n までの自然数のコラッツ展開を考えます。
どの2つを見ても、>>521の補題より、初項から第 n 項までが一致することはありません。
長さ n の 01 列は全部で 2^n 通りあるので、全てのパターンが現れていることになります。

例えば長さ 3 の場合を考えると、
1→101
2→010
3→110
4→001
5→100
6→011
7→111
8→000
となって、全てのパターンが現れていることが確認できます。

**１３２人目の素数さん** · 2018/07/26(木) 21:39:47.97

えっなんかすげくね？
ここから対角線論法つかってごにょごにょしたら
なんか出てきそうな気もするけどそんな甘くないかな

**１３２人目の素数さん** · 2018/07/26(木) 21:52:15.76

>527

f(x×2+0)=x×1+0
f(x×2+1)=x×3+2
xの係数は奇数なので、この奇偶はxの奇偶によって定まる。

さらに x→x×2+0, x→x×2+1
で置き換えてコラッツ操作を行うと
4x+y(y=0,1,2,3)について長さ2のコラッツ展開は全て異なることがわかる

以下繰り返すことにより
f^k(x×2^n+y)のnの係数は奇数(3の冪)であり、
y=0,1,…,2^n-1に対し長さnのコラッツ展開は全て異なることが示せる

**１３２人目の素数さん** · 2018/07/26(木) 21:55:10.54

いくら場合わけしてもとり尽せない理由もこのへんにあるのかなぁ

**530** · 2018/07/26(木) 22:03:15.00

これに気づいた時点で「単純な分類でとうにかするのは無理だ」とは考えました
上位ビットを適当に選べば、増加を繰り返すものが必ずあるのか、と

突破するにはパラダイムシフトが必要でしょうね……

**１３２人目の素数さん** · 2018/07/26(木) 22:21:07.82

たとえば√2を2進数で表したとして、
その第n桁までコラッツ展開が一致する数のうち最小のもをa_nとおいて
F(√2)=lim n->∞ a_n
とでもして
F(√2)が有限の値をとるかどうかは考察できる？

**righ1113** ◆OPKWA8uhcY · 2018/07/26(木) 22:24:11.72

>>525
異常ありませんでした!

**１３２人目の素数さん** · 2018/07/26(木) 22:52:09.41

>>534
おおう、まじか。
チェックありがとうございます。
ちなみにe5fE+xPzとVbgF2ohAは同一です

**１３２人目の素数さん** · 2018/07/27(金) 03:28:39.24

このスレで証明されたら誰の手柄になるの？

**M.B.** · 2018/07/27(金) 09:27:20.65

>>536
手柄とかはどうでもいいんじゃね？
論文に名前が出るかっていう話なら、
有限群の分類とか新素粒子の発見の論文みたいに、
著者の名前のリストのほうが本文より長かったりするんじゃねーの？
おれの名前は入ってなくていーや。
でなかったら『電車男』の「電車」と「エルメス」みたいに
「righ1113」と「前786」と「その他協力者のみなさん」とか。

**M.B.** · 2018/07/27(金) 14:01:13.64

あー、なんか厭な予感がしてきた。
べつに >>516 以降の議論を尊重しないわけじゃないけど、
>>146 あたりの議論を考えると、たぶん全射にならないんじゃないかと
思うんですけどね。そこを避けるための手当をすればイケる感じは
あると思います。
「コラッツ展開」の精密化と、関数 f() の性質について、さらに検討すれば、
>>530 氏のいう
> 突破するにはパラダイムシフトが必要でしょうね ……
のあたりに到達できそうな気はするんですけど ……
「また元に戻ってきてガックリ」みたいな話は、ありそうに
思うんですけどね。

**１３２人目の素数さん** · 2018/07/27(金) 19:31:28.11

任意の{0,1}無限列に対して、
コラッツ展開が一致する正整数が存在するかと言えば否。
00000…には0,
11111…には-1が対応する。

**１３２人目の素数さん** · 2018/07/27(金) 19:50:56.29

では整数に拡張すれば大丈夫かと言えば、これも否で、
2進整数(2-adic integer)まで拡張する必要がある

任意の{0,1}無限列に対し、
先頭のn項がコラッツ展開と一致する非負整数はZ/2^nZで一意になり、また、nの増加とともに下位を共有しなから伸びていくのはすでに示された通りだけど、
これがちょうど2-進整数の条件を満たしている

**１３２人目の素数さん** · 2018/07/27(金) 23:23:55.63

>>1に頼みたいんだが以下の仕様でプログラム組んでくれない？

n(自然数)を入力とする
nビット以下の01列とそれに対応するコラッツ展開をもつ2^n以下の自然数を列挙する

例　n=3の時

0:{2,4,6,8}
1:{1,3,5,7}
00:{4,8}
01:{2,6}
10:{1,5}
11:{3,7}
000:{8}
001:{4}
010:{2}
011:{6}
100:{5}
101:{1}
110:{3}
111:{7}

お願いします。

**１３２人目の素数さん** · 2018/07/28(土) 00:41:28.27

なにかグレイコードっぽい雰囲気を感じる
あくまで雰囲気だけど

**righ1113** ◆OPKWA8uhcY · 2018/07/28(土) 09:07:10.25

>>541
しばしお待ちを。

**前786** ◆5A/gU5yzeU · 2018/07/28(土) 11:48:18.14

コラッツ展開は 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 列への展開が得られ、
>>521>>522で示した事実の類似が成り立ちます。

**righ1113** ◆OPKWA8uhcY · 2018/07/28(土) 17:56:46.51

>>541
できたよ～
https://github.com/righ1113/CollatzMod/blob/master/CollatzExpansion.hs

**１３２人目の素数さん** · 2018/07/28(土) 18:15:36.05

>>545
おお、仕事速いっすな。
ありがとうございます。

**１３２人目の素数さん** · 2018/07/28(土) 19:04:59.11

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]

**１３２人目の素数さん** · 2018/07/28(土) 19:12:39.28

>>545
動かしてみました。
確かになんらかの法則性があるように見えますが、うまく言語化できないorz
うーん。なんだろうこれは

**１３２人目の素数さん** · 2018/07/28(土) 19:16:50.85

前786さんならなにかピンとくるものがあるかも知れませんねぇ

**１３２人目の素数さん** · 2018/07/28(土) 19:29:16.09

>>1へ

とりあえず前786さんにも見ていただきたいのですが、
前見たく出力結果をgithubにあげていただけませんか？
とりあえずn=10位がいいかなぁ

**１３２人目の素数さん** · 2018/07/28(土) 20:14:20.24

あるビット列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]
になる？

**righ1113** ◆OPKWA8uhcY · 2018/07/28(土) 20:14:28.87

>>550
n=10を上げました。
https://github.com/righ1113/CollatzMod/blob/master/CE_n%3D10.txt

**１３２人目の素数さん** · 2018/07/28(土) 20:17:08.60

いや、ちょっとちがうな。
でも添え字が偶数のものと奇数のものに分かれるのは言えそう。

**１３２人目の素数さん** · 2018/07/28(土) 20:20:56.40

>>552
ありがとうございます。
前７８６さんもぜひご覧になってなにか法則性がないか考察お願いします。

**１３２人目の素数さん** · 2018/07/28(土) 20:49:43.10

すいません。また>>1にお願いがあるのですが
今１０進で表示されている数字をnビット先頭0埋め2進数で表示させられませんか？
ひょっとしたら法則性が見えやすくなるかもしれないのですが。

**righ1113** ◆OPKWA8uhcY · 2018/07/28(土) 21:32:38.98

あげました～
https://github.com/righ1113/CollatzMod/blob/master/CE_n%3D10b.txt

プログラムでやりたい場合は、
最新版のCollatzExpansion.hsの
74行目をコメントアウトして、
75行目のコメントを外すと、バイナリになります。

**１３２人目の素数さん** · 2018/07/28(土) 22:00:14.13

おお、ありがとうございます。
さらに追加で要求でもうしわけないんですが、
１０進版とバイナリ版のexeもgithubに上げてもらえませんか
exeなら前786さんやほかの方も抵抗が少ないだろうし

**righ1113** ◆OPKWA8uhcY · 2018/07/28(土) 22:21:49.34

上げました。
https://github.com/righ1113/CollatzMod
CollatzExpansion.exe
CollatzExpansionB.exe

です。

**１３２人目の素数さん** · 2018/07/28(土) 22:31:14.58

おお、何度もありがとうございます。
>>1にも聞いてみたいですが結構法則性ありそうに見えますよね？

**righ1113** ◆OPKWA8uhcY · 2018/07/28(土) 22:36:46.25

>>559
2進数で左右反転しているのと、そうでないのとがありますね。

**前786** ◆5A/gU5yzeU · 2018/07/28(土) 22:40:43.24

あまり期待はしないで下さいな。

出力の並び順ですが、
00000
10000
01000
11000
:
:
のようにしてもいいかもしれません。可能ならば。
>>544で言ったようにコラッツ展開を2進展開の類似物と捉えると、
コラッツ展開の初項が一の位に対応するので。

もしくは2進展開にならってコラッツ展開も右から左に書くことにするとか。

**１３２人目の素数さん** · 2018/07/28(土) 23:51:31.58

確かに左右反転してるのが結構ありますねぇ…

**M.B.** · 2018/07/29(日) 00:20:38.47

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

**１３２人目の素数さん** · 2018/07/29(日) 01:01:26.47

桁数：左右反転している個数
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

**１３２人目の素数さん** · 2018/07/29(日) 01:05:24.07

割合的には急激に減る
桁数をnとすると、n*log nくらいのオーダーか？

**１３２人目の素数さん** · 2018/07/29(日) 01:06:53.56

さらに>>１にお願いしたいが

入力ｎに対して丁度nビットの01列とそれに対応するコラッツ展開をもつ2^n以下の自然数を列挙

コラッツ展開と自然数を２進であらわしたものが反転してる関係にあるものは行頭に空白４個入れる
反転ではないものは行頭に空白を入れずに表示

でプログラムお願いできない？

**１３２人目の素数さん** · 2018/07/29(日) 01:14:15.62

左右反転になるもの
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]

**前786** ◆5A/gU5yzeU · 2018/07/29(日) 12:59:45.00

左右反転については考えたことは無かったですね。
とりあえず偶数は奇数に帰着されるので、奇数だけ見るのがいいような気がします。

**righ1113** ◆OPKWA8uhcY · 2018/07/29(日) 14:30:52.71

>>566

>>561の案についてはどうしましょうか？
ビット列を左から書くようにすると、
ビット列とコラッツ展開が『左右反転している』　→　『同一である』
になって分かりやすいと思うのですが。

**566** · 2018/07/29(日) 14:59:40.32

>>569
じゃあ採用してみましょうか
お願いします

**righ1113** ◆OPKWA8uhcY · 2018/07/29(日) 16:26:02.64

>>570
できました。
https://github.com/righ1113/CollatzMod/tree/master/CE02
CE02_n=10.txt
CollatzExpansion02.exe
CollatzExpansion02.hs

**１３２人目の素数さん** · 2018/07/29(日) 16:49:37.95

ありがとうございます
いま外にいるので帰ったらみてみます

**１３２人目の素数さん** · 2018/07/29(日) 17:29:22.44

ん、これコラッツ展開のビットのほうを左右反転させたんじゃなくて
コラッツ展開に対応する自然数のビットを反転させたってことですかね？

**righ1113** ◆OPKWA8uhcY · 2018/07/29(日) 17:53:25.69

いや、両方反転させてるような......
なのに『同一』？？？

**１３２人目の素数さん** · 2018/07/29(日) 18:13:30.45

>>574
つまりどういうことだってばよ？

**righ1113** ◆OPKWA8uhcY · 2018/07/29(日) 18:15:38.20

>>574は無視してください。
コラッツ展開のビット（初項）を反転させています。

**１３２人目の素数さん** · 2018/07/29(日) 18:34:34.10

すまん、まだよくわかってないんだが、
そうするとこの10進で表示してあるのは何を表してるの？

**righ1113** ◆OPKWA8uhcY · 2018/07/29(日) 18:41:19.06

>>577
初項がコラッツ展開のビットで、
第二項が初期値（2進数）で、
第三項が初期値（10進数）です。

**１３２人目の素数さん** · 2018/07/29(日) 18:44:40.84

第二項は左右反転してません？

**righ1113** ◆OPKWA8uhcY · 2018/07/29(日) 18:53:23.89

してますね～　う～ん

**１３２人目の素数さん** · 2018/07/29(日) 19:20:56.12

字下げされているデータは、上からｎ番目にあると第三項もnになる
という法則はありそうなきがする

**righ1113** ◆OPKWA8uhcY · 2018/07/29(日) 19:26:26.92

>>581
あ、それはコラッツ展開のビットを1から順番に並べているので、
コラッツ展開と初期値が一致するなら、当然そうなると思われます。

**righ1113** ◆OPKWA8uhcY · 2018/07/29(日) 19:31:39.53

>>573-580
色々とすみませんでした。
プログラムの説明不足でした。

**１３２人目の素数さん** · 2018/07/29(日) 19:36:14.28

どうでもいいことだけど、いま私のメインマシンが壊れていて
古いノートPC（32bit OS)使ってます。
githubにあげてもらったexeは64bit版ですかね？動きませんでした。
私はソースのほう使ってるのでそれでも大丈夫ですが。

**前786** ◆5A/gU5yzeU · 2018/07/29(日) 21:59:54.79

・コラッツ展開の表記は元のまま。縦の並び順だけを変えている。
・2進数表記は反転させている。
という状態みたいですね。

2進数表記を変えると混乱を招きそうなので
コラッツ展開の方を反転させた方がいいかも？。
つまり
("0000000000","0000000000",1024)
("0000000001","0101010101",341)
("0000000010","1010101010",682)
("0000000011","0011100011",227)
("0000000100","0101010100",340)
：
：
と出力させる感じで。

**righ1113** ◆OPKWA8uhcY · 2018/07/31(火) 21:40:25.63

　　　　　 |
　　＼　　__　　／
　　＿　（ｍ）　＿ﾋﾟｺｰﾝ
　　　　　|ミ|
　　／　｀´　＼
　　　　　('A`)
　　　　　ノヽノヽ
　　　　　　　くく

**righ1113** ◆OPKWA8uhcY · 2018/07/31(火) 22:16:53.79

コラッツ展開の一部が、コラッツ値の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で覆えます。

**righ1113** ◆OPKWA8uhcY · 2018/07/31(火) 22:20:11.18

そして、
「コラッツ展開を、下位2ビット以上の2進数の連結で覆い尽くせる」→「コラッツ操作で1に辿り着く」
が言えれば良いと思うのです。

**１３２人目の素数さん** · 2018/07/31(火) 23:08:52.93

ん、よくわからん。
前７８６さん、わかります？

**前786** ◆5A/gU5yzeU · 2018/08/01(水) 13:01:17.37

どういう操作をしてるかはなんとなく分かりましたけど、
なんかNGワードがあるとかで書き込めないので画像にて失礼。
https://i.imgur.com/uYeyPKq.png

そこからの>>1さんの主張は私もはっきりとはわかりませんが、
「常に 2 ビット以上覆う」ということを利用してコラッツ予想を証明できないか、みたいな感じでしょうか。

**righ1113** ◆OPKWA8uhcY · 2018/08/02(木) 10:26:14.57

>>590
そうです、こんな感じです。
（確かに26は3ビット覆えますね）

**righ1113** ◆OPKWA8uhcY · 2018/08/04(土) 14:45:23.85

うまくいきませんでした。

**１３２人目の素数さん** · 2018/08/06(月) 20:24:49.16

登って下がってというループで山が四つくらいまでのループは無いらしいが、この方面では難しそうだ
Zudilin あたりが書いた超越数の≪(3/2)^n≫ あたりからなんか言えんかね
ABC が絡むような話もどこかにあったような気がするのは気がふれたみたいだからさようなら

**righ1113** ◆OPKWA8uhcY · 2018/08/08(水) 20:15:08.57

ちょっと思い出話でも。
自分がスレを立てる前のコラッツスレに、
「割数列」というものがありました。

コラッツ操作で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]はふつうの割数列です。

**前786** ◆5A/gU5yzeU · 2018/08/08(水) 22:53:01.75

(割数列の話を始めたのも私だったり)

**righ1113** ◆OPKWA8uhcY · 2018/08/08(水) 23:11:14.38

マジっすか!?

**righ1113** ◆OPKWA8uhcY · 2018/08/08(水) 23:29:36.29

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]が存在する。

**前786** ◆5A/gU5yzeU · 2018/08/08(水) 23:56:36.04

いやあ、懐かしいですねぇ

ちなみに割数列とコラッツ展開は密接に関係しています。
実はコラッツ展開は、割数列から派生して得られたものだったりします。

例えば 9 のコラッツ展開は
　1,0,1,1,1,0,1,0,0,1,0,0,0,1,…
ですが、このとき 1 が現れてから次の 1 が現れるまでの項数を見ていくと
　2,1,1,2,3,4
となり、これが割数列に一致します。

**righ1113** ◆OPKWA8uhcY · 2018/08/09(木) 00:04:34.00

なるほど。そんな歴史があったのですね。

**righ1113** ◆OPKWA8uhcY · 2018/08/09(木) 05:30:13.84

>>597
前スレで、「全てのstar変換後の完全割数列は、全ての3の倍数の奇数を尽くす」事を証明しました。

しかし、後ろに無限に長く、base caseである21[6]にたどり着かない
完全割数列を排除できなくて、その時は挫折しました。

**righ1113** ◆OPKWA8uhcY · 2018/08/09(木) 23:59:53.30

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の計算自体は出来ているようです。

**righ1113** ◆OPKWA8uhcY · 2018/08/10(金) 00:28:24.11

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

**righ1113** ◆OPKWA8uhcY · 2018/08/10(金) 23:41:44.61

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

**righ1113** ◆OPKWA8uhcY · 2018/08/13(月) 15:49:38.48

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

**righ1113** ◆OPKWA8uhcY · 2018/08/13(月) 15:53:03.94

普通の完全割数列に、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　偶数はない

**righ1113** ◆OPKWA8uhcY · 2018/08/13(月) 16:12:32.34

コラッツ値x=36t+3とx=72t+9は1にたどり着く事が分かりました。
（3と9は手計算で、ということにしましょう）
ここで思ったのですが、このパターン、剰余コラッツ予想で解かれてなかったっけ！？

>>4
＞前スレ>>786の予想は、以下の場合に証明できています。
＞・n は 83 以下の奇数, k は任意
36は81に帰着されるので有効、
72は243なので今のところout

**righ1113** ◆OPKWA8uhcY · 2018/08/14(火) 15:24:26.87

偶数は「最小でない反例」の可能性があるのですね。
失礼しました。
>>604-606は無しでお願いします。

**righ1113** ◆OPKWA8uhcY · 2018/08/15(水) 13:30:28.73

>>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　　より小さい反例が得られました。

**righ1113** ◆OPKWA8uhcY · 2018/08/15(水) 13:33:56.44

・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は存在しません。

**righ1113** ◆OPKWA8uhcY · 2018/08/15(水) 13:38:16.32

拡張完全割数列に対して、無限項のものがないと分かりました。
よって、全ての項が正である、通常の完全割数列に限定しても、無限項のものはありません。
以上より、全ての3の倍数の奇数は、1に辿り着くことが言えました。

**１３２人目の素数さん** · 2018/08/15(水) 16:53:18.16

えっ
ちょい待ち
全ての6n-3が1を含む枝に属する事が証明できた？
コラッツ予想の証明完了じゃん

**righ1113** ◆OPKWA8uhcY · 2018/08/15(水) 17:00:20.05

>>611
そうなりますねぇ......

**１３２人目の素数さん** · 2018/08/15(水) 23:30:39.14

マジで？
記念ﾊﾟﾋﾟｺ

**前786** ◆5A/gU5yzeU · 2018/08/16(木) 00:57:42.04

>>608で、c=18t''+21 から y=3t''+3 への変換で
対応する割数列の変換が本当に B[1,-2] になってるかが怪しいような。

**righ1113** ◆OPKWA8uhcY · 2018/08/16(木) 05:27:05.36

>>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]

ひとまずうまくいっているようです。

**righ1113** ◆OPKWA8uhcY · 2018/08/16(木) 07:46:18.73

c≡0 mod 9のときに不備がありそうです。
調査します。

**前786** ◆5A/gU5yzeU · 2018/08/16(木) 10:23:39.87

0 や負の項を許しているのを失念していました。
ただそうすると、一つの数に対して複数の数列が対応することになります。

c=18t''+21 の割数列に変換 B[1,-2] を施すと、y=3t''+3 の拡張完全割数列の一つが得られますが、
それは y=3t''+3 の通常の割数列と同じとは限らず、通常の割数列が無限に長いとは言い切れない、
すなわち反例になっているとは言い切れないと思います。

**righ1113** ◆OPKWA8uhcY · 2018/08/16(木) 13:10:13.37

うーむ……
もうちょっと考えてみます。

**１３２人目の素数さん** · 2018/08/17(金) 03:14:56.80

せっかく解けない問題があるんだから、何かに使えないんでしょうか

数独のようなパズルを作る
乱数を作る
暗号システムを作る