コラッツ予想がとけたらいいな　その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

**前786** ◆5A/gU5yzeU · 2018/05/25(金) 00:01:05.77

で、お気づきかもしれませんが、現在のアルゴリズムはコラッツ逆操作しか考えていません。
これが「コラッツ予想の 19n+1 版は成り立たない」とは結論づけらない理由です。
（コラッツ逆操作しか考えていない理由は、これだけでもさしあたってうまくいっていたことと、コラッツ操作まで考えると一気に複雑さが増すことということです）
（逆操作だけというのはかなり制限しているように見えますが、実はそれほどでもありません。また今度話します。）

今回の結果についてですが、
まず出力結果にある C' は「mod 133(=7*19) で 2 のべきである数の集合」になります。（これもまた今度）
このことから今回の結果を次のように述べることができます。

定理
コラッツ予想の 19n+1 版を考える。
このとき、mod 133 で 2 のべきである数からコラッツ逆操作を繰り返しても、
mod 133 で 2 のべきである数以外は得られない。

これはちょっと予想外でした。
3n+1 では今までコラッツ逆操作だけでうまくいってたけど、
そのうちコラッツ操作も考えなきゃいけなくなるかもしれない…

**１３２人目の素数さん** · 2018/05/25(金) 05:24:49.37

>>96
n が 127 以下については、手で描いてみた（A4 の 5mm 方眼紙四枚とか）。
以前誰かが書いてたように、「場合分けが面倒臭いことに
なって手に負えなくなる」という感じのある錯綜したケース
（確かに127 以下はけっこうややこしい）を脱して
ある程度規則性が見えてくるのは、ここより先
（255 とか 1023 とか 2047 とか）らしいんだよね。
そうすると、もう手描きだと追いつかなくなるのと、関係が錯綜して
見づらくなる（つーか、局所的な関係はわかるんだが、全体像が
把握できなくなる）ので、「２で割る」「３n + 1 して 2 で割る」
「その数の大きさ」みたいに次元を分けて空間的に散らばらせて、
ぐるっと見渡せれば何かわかるかな、と。
乱数の品質とかも、二次元空間にマッピングすると「あ、この
アルゴリズムだと、品質悪いな」とか判ったりするじゃん？
あんな感じ。

**righ1113** ◆OPKWA8uhcY · 2018/05/25(金) 22:16:46.77

>>100-101
う～む、そんなに単純ではないのですね。

ちなみに、
コラッツ予想の19n+1版において
7で割って
・0,1,2,4余る数→全ての木に現れる
・3,5,6余る数→一部の木にしか現れない
これは言えるのでしょうか？

**前786** ◆5A/gU5yzeU · 2018/05/25(金) 23:19:00.95

>>103
それが言えちゃうとまさに「コラッツ予想の 19n+1 版は成り立たない」になっちゃいます。

・0,1,2,4余る数→全ての木に現れる
これはプログラムによって証明できていますが、

・3,5,6余る数→一部の木にしか現れない
こっちは証明できていません。

**righ1113** ◆OPKWA8uhcY · 2018/05/25(金) 23:32:11.70

なるほど～失礼しましたー

**１３２人目の素数さん** · 2018/05/25(金) 23:45:29.86

しかし実際問題として19n+1版の反例というのはそんなに簡単には見つからないものなんですか？

**righ1113** ◆OPKWA8uhcY · 2018/05/26(土) 00:04:16.67

>>106
bn+1版でbが大きくなると、遷移の上昇幅も大きくなるから、無限大に発散する可能性は高くなると思います。
適当にプログラムを走らせて、どんどん大きくなっていくようなら、この初期値は無限大に発散する可能性が高い、とは言えると思います。
「無限大に発散する!」という証明はかなり難しいと思います。

**前786** ◆5A/gU5yzeU · 2018/05/26(土) 00:08:59.09

>>106
どうでしょうね…あまり考えたことはないので、難易度も分かりません。

**前786** ◆5A/gU5yzeU · 2018/05/26(土) 00:55:24.03

「コラッツ逆操作だけ」というのがそれほど強い制限でないという話。

まず、コラッツ逆操作では操作 3 を行うか操作 4 を行うかで分岐が起こりますが、
コラッツ操作では分岐は起きません。
なので、例えばある数にコラッツ逆操作を行ってからコラッツ操作を行うと、元の数に戻ることになります。

予想を証明するには、
「ある数 a からコラッツ操作、コラッツ逆操作を繰り返してある数 b にたどり着けるか」
を考える必要がありますが、上記のことから
「ある数 a から何度かコラッツ操作を行い、その後何度かコラッツ逆操作を行うことである数 b にたどり着けるか」
という道筋だけ考えればいいということになります。

そうすると、コラッツ逆操作だけを考えるというのは大体、操作の後半だけを考えるということになります。
これが強い制限と思うかどうかは人それぞれですが、
実際にこれまでは多くの場合にうまくいっているので、大した制限じゃないのだろうと私は思っています。

**前786** ◆5A/gU5yzeU · 2018/05/26(土) 00:55:45.59

ちなみにこれまで「コラッツ操作」の方を全く考えていない訳ではなく、

前スレ>>787の

命題
T を木とし、k=1 or 2 とする。
このとき、ある a∈T が存在して a≡k (mod 3) となる。

や、前スレ>>851の

補題
n を 5 以上の奇数とする。
任意の木には、3 の倍数でも n の倍数でもない数が含まれる。
（元々は奇数でなく素数としていたが、全く同じ証明で奇数の場合も示せる）

ではコラッツ操作を用いています。

**righ1113** ◆OPKWA8uhcY · 2018/05/26(土) 05:32:28.98

通常のコラッツ予想3x+1ですが、

①プログラムが無限走行→オールNothing出る
(Cを繰り返すと集合が1つになる事が使えないか)

②オールNothing出ない→プログラムは停止

③全てのnでオールNothing出ない(難しい?)

④全てのnでプログラムは停止する

というのを考えたのですが、
実際証明するとなると難しいですかね。

**１３２人目の素数さん** · 2018/05/26(土) 06:33:58.67

　また邪魔なプログラマが通りますよ

　コラッツ逆問題（３ｎ＋１版。「1 から出発して、すべての自然数に
到達できるか」）について、「（有限な）すべての偶数は、２で割り続ける
ことによって奇数に帰着するので、奇数についてだけ証明できれば足りる」
のは確か。

　逆コラッツ操作は、

　１）ｎを２倍する。
　２）ｎを二倍して１を引いたものが３で割りきれるなら、それ（２ｎ－１）を
３で割る。

が可能。

　で、このとき、「ｎが３で割りきれる場合は、（１）の操作によって
『ｎを二倍して１を引いたものが３で割りきれる数』が出てこない」ことが
判っていて、ｎの偶奇によらず（１）の操作の結果は偶数になるので、けっきょく
奇数は出てこないことがわかる。

　（２）に対応する正のコラッツ操作は、結果的に「ｎを二倍して１を引いたものが
３で割りきれない数」に「２ｎ＋１」操作を繰り返して「６で割って２余る偶数」に
至る“縦のルート”（有限長の上下のルート）を描くことであり、このとき（ｎの
偶奇によらず）３の倍数が出てきたときは逆コラッツ操作の
（１）（“右へ向かうルート”。こちらは際限なく右に延長できる）は
考慮しなくていい。

　なお、“縦のルート”は、最下位ビットが「２個以上の連続するオンビット」である
状態と関連している。

　この制約条件のもとで、「１を出発点として、すべての奇数に到達できるか？」が、
コラッツの逆問題となる。

　で、「最下位のオンビットが連続しない」数は、「４で割って１余るｎ」であり、
それが正のコラッツ操作（２）によって「６で割って２になる数」に変換されるはず
だから、それを満たす数について考えればいい ―― ような気がする。

　だけど、コラッツ予想に関する議論で「mod 12」って話が出てきたのを
見た記憶がオレにはないんだよな (-_-!)。

　これって、オレがなにか盛大な勘違いをしているってぇコトなのか？

**righ1113** ◆OPKWA8uhcY · 2018/05/26(土) 15:26:37.54

>>112
>「ｎを二倍して１を引いたものが３で割りきれない数」に「２ｎ＋１」操作を繰り返して「６で割って２余る偶数」に至る“縦のルート”

ここが分かりません。
具体的な一連の数とかありますか?

**１３２人目の素数さん** · 2018/05/26(土) 17:07:34.51

>>113
とりあえずこんな感じかな？

242:242 -> 161 -> 107 -> 71 -> 47 -> 31
728:728 -> 485 -> 323 -> 215 -> 143 -> 95 -> ☆63
1214:1214 -> 809 -> 539 -> 359 -> 239 -> ☆159
1700:1700 -> 1133 -> 755 -> 503 -> 335 -> 223
2186:2186 -> 1457 -> 971 -> 647 -> 431 -> 287 -> 191 -> 127
2672:2672 -> 1781 -> 1187 -> 791 -> 527 -> ☆351
3158:3158 -> 2105 -> 1403 -> 935 -> 623 -> 415
3644:3644 -> 2429 -> 1619 -> 1079 -> 719 -> 479 -> 319
4130:4130 -> 2753 -> 1835 -> 1223 -> 815 -> ☆543
4616:4616 -> 3077 -> 2051 -> 1367 -> 911 -> 607
5102:5102 -> 3401 -> 2267 -> 1511 -> 1007 -> 671 -> ☆447
5588:5588 -> 3725 -> 2483 -> 1655 -> 1103 -> ☆735
6074:6074 -> 4049 -> 2699 -> 1799 -> 1199 -> 799
6560:6560 -> 4373 -> 2915 -> 1943 -> 1295 -> 863 -> 575 -> 383 -> ☆255
7046:7046 -> 4697 -> 3131 -> 2087 -> 1391 -> ☆927
7532:7532 -> 5021 -> 3347 -> 2231 -> 1487 -> 991
8018:8018 -> 5345 -> 3563 -> 2375 -> 1583 -> 1055 -> 703
8504:8504 -> 5669 -> 3779 -> 2519 -> 1679 -> ☆1119
8990:8990 -> 5993 -> 3995 -> 2663 -> 1775 -> 1183
9476:9476 -> 6317 -> 4211 -> 2807 -> 1871 -> 1247 -> ☆831
9962:9962 -> 6641 -> 4427 -> 2951 -> 1967 -> ☆1311

詳細はのちほど。

**１３２人目の素数さん** · 2018/05/26(土) 17:11:05.80

つーか、「コラッツ操作」ということを考えたら、
「->」じゃなくて「<-」のほうが判りやすかったかも。
あ、「3n + 1」じゃなくて、「(3n + 1) / 2」で
表示してるのは、このスレを見てるような人だったら
察してくれるよね？

**１３２人目の素数さん** · 2018/05/26(土) 17:16:10.29

言うまでもないけど、
“☆”がついている値は、
「３の倍数なので、2 の冪乗を掛けても
『2n - 1 が 3 で割りきれる数にならんので、
下に延びる枝（3n + 1 操作の逆操作）がない枝』」
っちゅーことです。

**righ1113** ◆OPKWA8uhcY · 2018/05/26(土) 17:54:29.76

>>114-116

>>112は大体理解できました。mod12は分かりません。

>　で、「最下位のオンビットが連続しない」数は、「４で割って１余るｎ」であり、
>それが正のコラッツ操作（２）によって「６で割って２になる数」に変換されるはず
>だから、それを満たす数について考えればいい >―― ような気がする。
例えば17を見ると、4で割って1余る。
コラッツ操作(2)で26になって、6で割って2余る。
しかし17を2倍して1引いた数が3で割りきれてしまう。
コラッツ操作(2)に違反していると思うのだけど、こういう数はどう処理するの?

**１３２人目の素数さん** · 2018/05/26(土) 18:02:39.81

>>113
ごめん。
>（２）に対応する正のコラッツ操作は、結果的に「ｎを二倍して１を引いたものが
３で割りきれない数」に「２ｎ＋１」操作を繰り返して「６で割って２余る偶数」に
至る“縦のルート”（有限長の上下のルート）を描くことであり、
っつーのは、
>（２）に対応する正のコラッツ操作は、結果的に「ｎを二倍して１を引いたものが
３で割りきれない数」に「（３ｎ＋１）／ 2」という操作（←ここ重要）を繰り返して「６で割って２余る偶数」に
至る“縦のルート”（有限長の上下のルート）を描くことであり、
という意味だ。
とりあえずツッコミは歓迎なのだが、いまは遠山啓先生の『初等整数論』で
理論武装中なので、殲滅的攻撃は勘弁してくれいm(_ _)m。

**righ1113** ◆OPKWA8uhcY · 2018/05/26(土) 18:19:59.67

>>118
すみません、つい熱くなってしまって……

**１３２人目の素数さん** · 2018/05/26(土) 18:20:36.68

>>117
> 例えば17を見ると、4で割って1余る。
> コラッツ操作(2)で26になって、6で割って2余る。
> しかし17を2倍して1引いた数が3で割りきれてしまう。
> コラッツ操作(2)に違反していると思うのだけど、こういう数はどう処理するの?
典型的な例を挙げたので分かりにくかったと思うが、
(26 ->)17 -> 11 -> 7 というのは確かにあって、
「必ず 3 の倍数で終わる」とかいう話ではないのだ。

つーか、「どのあたりで齟齬が生じているか」について、
数学屋さんと電算屋の間では分かりにくいのだ。
「素数には必ず原始根がある」というのは納得するにせよ、
「原始根って複数あるんじゃないの？　そのあたりはどうなの」とか、
「そもそも『指数』という概念がよくわからん」とか、
「QRコードとか乱数生成とか、リクツは判らんでもないけど、
原始多項式うんぬんとか言われても、正直な話、小分かりがせんのよ」
みたいな感想がある。

そもそも「Z/pZ」っつーのが、「演算を定義せんと意味がねぇ」みたいな
話があって、よくわからん（加法なのか乗法なのかとか）。

せっかく大勢の人が見てくれているのだから、「数学的に厳密な記述」
ではない「わかりやすい説明」（まぁ、「『分かりやすい説明』は、
嘘の温床だ」という意見は確かにあるのだが）っつーのも
試みてくれんか。このスレで（見ているだけの奴もいるし、
書いている奴もいるわけだが）“解っている” 人間も
少なかろうと思うので。

**１３２人目の素数さん** · 2018/05/26(土) 18:35:17.86

>> 119
> すみません、つい熱くなってしまって……
いや、熱くなるのはまったく問題ないので、「こちらこそ、数学の門外漢が
半煮えの議論を持ち出してすまん m(_ _)m」とお詫びしたい。
とはいえ、実験数学が未解決問題の解決に貢献することもあるし、
「素人目線からの、視覚化だのなんだの」が有効なことがあるのだ。
数学屋さんには数式という武器があり、
電算屋にはプログラミング言語という武器がある。
（個人的に Wolfram は気に入らないが）Mathematica みたいに
その間を繋ぐツールもある。
とりあえず「共通の土俵」っつーのを用意したいと思う。

**１３２人目の素数さん** · 2018/05/26(土) 19:04:19.46

具体的にプログラム言語は何使えんのよ？

**１３２人目の素数さん** · 2018/05/26(土) 19:04:56.28

ちなみに>>1はhaskell使いらしい

**１３２人目の素数さん** · 2018/05/26(土) 19:52:05.47

>>122
> 具体的にプログラム言語は何使えんのよ？
わしゃぁのう、年寄りじゃけん、本当はアセンブラしか解らんのじゃ。
じゃけんども、C とか LISP とかは、理屈がよう分るんじゃ。
Pascal は、P-system があったんで、Java んような「中間言語」とか
「仮想マシン」っちゅーたらコンセプトは分らんでもないんじゃ。
年取ったけん、IDE がなけりゃプログラムなんぞ書けんように
なってしもうた。
そんなわけで、ようやく Java を使ってなんとかプログラムを
書いとるんじゃ。
ごめんつかぁさい。

**１３２人目の素数さん** · 2018/05/26(土) 20:15:39.62

中身のある話振ってくれるなら歓迎するけどね。
アイディアがあるなら具体的に頼む。

**１３２人目の素数さん** · 2018/05/26(土) 20:56:17.99

>>125
> アイディアがあるなら具体的に頼む。
ありがとう。

生煮えなので申し訳ないのだが、右（２の冪乗）から来る
値は、n ≡ 1(mod 3)か n ≡ 2(mod 3) だというのが
解っている（3 の倍数だったら、下((2n -1 が 3 の倍数になるので、
(3n + 1) / 2 の逆操作ができない)へ行けない)）と思う。
そうすると、わりとスケスケな感じで自然数の空間が
視えてくるような気はするのだが、「数直線」という
言葉があるように、フツーは自然数というのは一次元なんだよな？

そのあたり、なんかしらのパラダイム・シフトが必要な気はするんだが、
「それが具体的に何か」と訊かれても、「う～ん …」になっちゃうのだ。

「6 で割って 2 余る」とか「4 で割って 1 余る」とかいった話は
あるんだけど、6 と 4 の最小公倍数って 12 なんで、「(mod 12) って
ありそうな感じじゃねぇ？」とか言ってみただけな部分はあるわけですよ。

具体的な話をすると、「場合分けがパンクする」っつっても、
Tic-Tack-Toe＜（n-th Queen ではない）8-Queen ＜ make 10
＜ペントミノ＜四色問題と並べてみると、組合せ的な話であれば
ペントミノ程度の話なんじゃねーかと思ってるワケですよ。

ただ、「どういうコンセプトで捉えたら、数学的かつ計算器数学的な
問題に落とせるか」っていう切り口がわからんのよね。

そんなわけで、「アイディアがあるなら具体的に頼む。」という問いには、
「こっちが知りてぇよ」と応えざるを得ない。済まぬ m(_ _)m。

**１３２人目の素数さん** · 2018/05/26(土) 22:12:44.62

逆にxn+1問題で無限大に発散する場合もあるxを探すというのは？

**１３２人目の素数さん** · 2018/05/26(土) 22:44:42.03

コラッツ予想をセルオートマトンで可視化する事を試してみました。

ttps://dotup.org/uploda/dotup.org1543060.zip.html

キーは3nplus1です。

大まかに４つのパターンを図示してみました。
1）完全にランダムなパターン
2）1のビットが長く続くパターン(2^n-1)
3）最下位ビットと最上位ビットの間が0のビットで隔てられてるパターン(2^n+1)
4）1のビットが長く続き、さらに離れて最上位ビットが存在するパターン((2^n+1)*2^m-1)

最下位ビットが0の行は赤に塗ってあります。

プログラムに間違いがあればすいませんが、結構興味深い遷移がみられました。

**１３２人目の素数さん** · 2018/05/26(土) 23:12:06.85

>128 まとめ

○コラッツ操作を行った際に操作前よりも数が増えるのは最下位ビットから2ビット以上1が連続した場合のみ。それで増加する桁数は連続していた1の桁数よりもおそらく少なくなる。
○0が2ビット以上続いた箇所でグループを分けた場合(1011001101→1011　001101)、コラッツ操作3n+1のうち+1の影響を受けるのは最下位のグループのみ。それ以上のグループは3nの挙動となる。
○n桁の連続した1は3n+1操作で10(n-2桁の1)01になる。これが最下位グループなら+1操作で最下位ビットが繰り上がり10(n-1桁数の1)となる。

とりあえず挙げられるのはこんなところでしょうか。
既知の情報でしたら申し訳ない。

**１３２人目の素数さん** · 2018/05/26(土) 23:26:44.26

整数をビット列とみなして考えるのは>>1がかなりやってたから>>1の意見を聞きたいね。
まあ、この程度の成果では驚きはないだろうけど。

**１３２人目の素数さん** · 2018/05/26(土) 23:31:56.87

結構きれいな絵だけどきれいなものだけ抜き出したの？
よくわからんが全部きれいになるならもしかして凄いのかな？

**１３２人目の素数さん** · 2018/05/27(日) 00:11:19.66

>131

綺麗なパターンが出る値を選んでます。
大抵は増えて減ってを繰り返すパターンになると思いますが、その出現に規則性が見られるように思えます。
まぁ勘違いかもしれないんですが orz

**１３２人目の素数さん** · 2018/05/27(日) 07:33:04.20

>>129
「最下位ビットから2ビット以上1が連続した場合」については、
以下のようなことを考えたことがある。

「ここで、新たな操作を追加する。

　（３）n' = 3n + 2

である。
　たとえば "11101" のように、左に '1' が二個以上連続した部分（m 個）が
あるとする。これを、m - 1 個の '1' と '1' に分ける。 "11101" だったら
"11" と "101" だ。このとき、"11101" は、"**"と「 "101" に（３）の操作を
二回施した結果」で表される。

"11" -> "*" + "101"
"111" -> "**" + "10001"
"1101" -> "*" + "10001"
"1111" -> "***" + "101011"
"11001" -> "*" + "10111"」

その他の悪戦苦闘っぷりは
http://animaleconomicus.blog106.fc2.com/blog-category-33.html
を参照されたい。

**１３２人目の素数さん** · 2018/05/27(日) 08:58:45.44

逆コラッツ操作を行なうプログラムの中で、ずっと
「ｎを二倍して１を引いたものが３で割りきれたら３で割る」
とかいうロジックを使っていたのだが、よく考えたら
「ｎを３で割って２余る」（n ≡ 2(mod 3)）でよかったことに、
いま気づいた。

2*(m + 2) - 1 = 2m + 4 - 1 = 2m + 3

なんだから、3|m（「m が 3 で割切れる」あるいは「m は 3 の倍数」。
遠山啓さんの『初等整数論』のスタイルだと「3)m」）なら
当たりまえじゃん（だから数学は苦手なんだと(ry）。

　そうすると、

１）ｎを３で割って２余るなら、二倍して１を引いてから２で割る。（それが終わったら、次にｎを二倍して右を探す）
２）ｎを３で割って１余るなら、右に逃げる（ｎを二倍して右を探す）。
３）ｎが３で割りきれるなら、下には行けないし右側にも奇数へ向かう枝が出ないので、ひとつ前（根に近い数）に戻る。

という操作で再帰をかければ、「逆コラッツ操作で出てくる奇数の木を探索する」ことができるはずだ。

こうなったら奇数偶数関係ねぇじゃん。orz

**１３２人目の素数さん** · 2018/05/27(日) 13:50:43.81

個人的最近色々とデータをいじっているんだが、1になるまでの回数にちょっとした発見があるんだけど需要ある??

**１３２人目の素数さん** · 2018/05/27(日) 13:53:03.11

あとは逆コラッツとフィボナッチの関連性やn次のコラッツ、コラッツに群の導入などなど

**righ1113** ◆OPKWA8uhcY · 2018/05/27(日) 14:30:36.56

>>128-129
残念だけど目新しい情報はないかなあ。

**１３２人目の素数さん** · 2018/05/27(日) 17:28:34.65

>>135
> 個人的最近色々とデータをいじっているんだが、1になるまでの回数に
> ちょっとした発見があるんだけど需要ある??

>>136
> あとは逆コラッツとフィボナッチの関連性や、n 次のコラッツ、コラッツに群の
> 導入などなど

ここは、たぶん「『需要ある??』とか、つまんねぇ遠慮なんかしてるんじゃねぇ！　さっさと晒せよ！」
…… っつースレですから。燃料を投下していただければ、いくらでも。

**１３２人目の素数さん** · 2018/05/27(日) 19:19:29.97

スレがにぎわい始めましたね。
あとは>>786の議論についていけるレベルの人が来てくれればいい感じなのですが。

**１３２人目の素数さん** · 2018/05/27(日) 19:52:38.57

>> 139
> あとは（前スレの）＞＞786の議論についていけるレベルの人が来てくれればいい感じなのですが。

つーても、数学板は敷居が高いのよ。
前スレの＞＞8 の
> 最初に偶数はアウト（１に収束）
> ４の倍数になったらアウト

っつーのも、

×「最初に偶数はアウト」
〇「最初に２の冪乗数はアウト」（つーか、２で割り続ければ奇数に帰着するので、
奇数について証明できればオッケー。てなワケで「４の倍数になったらアウト」と
いうのも、ここに帰着）

とかいったツッコミ（つーか、解説）を誰かしてくれよ、みたいな話にはなる。

むしろ、素人目線の解説を丁寧にしてくれるヒトがいてくれると、もっと盛り上がる
ような気がするのだが。

**１３２人目の素数さん** · 2018/05/27(日) 21:51:55.33

藤林丈司

**前786** ◆5A/gU5yzeU · 2018/05/27(日) 22:57:17.76

なんだか盛り上がってますが
とりあえず>>92の出力が正しいことの説明がやっと書けそうなので、投下してから見ます。

**前786** ◆5A/gU5yzeU · 2018/05/28(月) 00:37:34.73

頭の中では図と数式だけしかないから大したことない議論に思えるけど
ちゃんと書こうとするとどうも長くなってしまう…

>>92の出力が正しいことの説明。

Z/nZ を図で表すイメージを導入します。

まず n が素数のときは、アルゴリズム (1) のようにグループ分けし、
https://i.imgur.com/h7RBsuk.jpg
図のように 2 倍すると右に 1 マス進むように数を並べます。
各グループの左端と右端は繋がっているイメージです。

n が素数べきの場合も同様です。
さらに一般の n でも同様の表現が可能ですが、ここでは別の表現を導入します。

p,q を相異なる素数とするとき、Z/pqZ は
Z/pZ を横軸、Z/qZ を縦軸にとった二次元配列で表せます。
https://i.imgur.com/tboXYk0.jpg
「Z/pqZ は (Z/pZ)×(Z/qZ) と同型」というのはこのことを表します。
例えば下図の赤マスは
https://i.imgur.com/ulP84EU.jpg
mod 7 で 4、mod 3 で 2 であるような数、すなわち 11 を表します。

Z/pqZ の図で数を 2 倍すると、右上のマスに移ります。
ただし、各ブロックで左右の端、上下の端はそれぞれつながっています。
https://i.imgur.com/bvi0vDc.jpg
図は一部のみ示していますが、どの矢印も 2 倍を表しています。

**前786** ◆5A/gU5yzeU · 2018/05/28(月) 00:38:11.51

ここから>>92の出力の話。
19n+1 版で、プログラムに 7 を入力して、A'={3,5,6} とした状況を考えます。
B は Z/133Z において、
「 19 の倍数でも 7 の倍数でもなく、mod 7 で 3,5,6 出ない数」
を考えるので、Z/133Z の下図の部分だけを見れば十分です。
https://i.imgur.com/TH0hekY.jpg

グループ分けを考えると、2 倍すると右上に進むことから
図のように 3 つのグループに分かれます。
https://i.imgur.com/twmrZQa.jpg
縦のマス数 18 が 3 の倍数であることに注意。

次に {3,5,6} に 19 をかけて 1 を足すと
3*19+1=58≡2 (mod 7)
5*19+1=96≡5 (mod 7)
6*19+1=115≡3 (mod 7)
より 3 に対してのみ B のグループが対応します。
58≡1 (mod 19)、58≡2 (mod 7) より
58 は図の位置になります。
https://i.imgur.com/Lr4sVXl.jpg
よって、緑グループのみ得られます。

**前786** ◆5A/gU5yzeU · 2018/05/28(月) 00:38:52.08

次の C は、Z/(7・19^2)Z において下図の部分を考えることになります
https://i.imgur.com/9mmsWTp.jpg
縦は 18・19 マスです。グループは 2 つ得られます。

緑マスの数に 19 をかけて 1 を足すわけですが、まず mod 7 だけで考えると
1*19+1=20≡6 (mod 7)
2*19+1=39≡4 (mod 7)
4*19+1=77≡0 (mod 7)
なので、緑マスの中でも mod 7 で 2 である数しか C のグループに対応し得ません。
対応するマスは mod 7 で 4 の列 (一番右の列) のどこかになります。

一方 mod 19 で考えると、ある数に 19 をかけて 1 を足すわけですから、
当然結果は mod 19 で 1 になります。
Z/(19^2)Z で 1 に 2 をかけていくと、mod 19 で 1 である数は 18 回に 1 回現れます。(2 が Z/19Z の原始根であることから)
したがって、緑マスの数に 19 をかけて 1 を足した数は、下から数えて 18k+1 (k∈N) 番目に現れます。

mod 7、mod 19 の話を合わせれば、
緑マスの数に 19 をかけて 1 を足した数は、青グループにしか対応しないことが分かります。
プログラムの出力でいえば、C のうち 1 つだけが得られた、という部分に当たります。

最後に C' の部分ですが、
青グループの数に 19 をかけて 1 を足すことを考えると、
C での議論と全く同じになり、黄グループの数に対応しないことが分かります。
したがって、出力は>>92の通りになります。

**１３２人目の素数さん** · 2018/05/28(月) 06:02:47.38

>>129 と >>132 から、なんとなく証明への道筋らしきものが見えてきた。
もちろん“道筋らしきもの”なので、完璧な証明に到達できるかどうかは別の話なのだが。

まず、ごく初歩的な話だが、「メルセンヌ数」の話をしておく。「メルセンヌ数」を「メルセンンヌ素数」だと思っているような人は
数学板にはいないだろうが、「素数であるメルセンヌ数」が「メルセンヌ素数」で
あって、メルセンヌ数は単なる「2^n - 1」の形をした数である。
　メルセンヌ数が素数であるかどうかは「リュカ検定（ルーカス・テスト）」に
よって比較的効率よく行えるので、「メルセンヌ素数は無限に存在するか？」
「（偶数の）完全数は無限に」という問題と関連して、コンピュータによる
探索が行なわれている。そうやって見つかった素数は桁数が大きいので
「現在知られている最大の素数」みたいな形で話題になる。

つぎに、任意の有限な数 n をビット列で表したときの、最初のオンビットから
最後のオンビットまでの部分を、“コラッツむし”と呼ぶ。

**１３２人目の素数さん** · 2018/05/28(月) 06:04:45.60

４で割って１余る（n ≡ 1(mod 3)）コラッツむし以外のコラッツむしは、
下位に「２個以上連続したオンビット部分」を持っている。ここで、m 個並んだ
オンビットがあるとして、そのうちの下位側の m - 1 個のビットを
「メルセンヌ部分」、残りを「本体」とする。このとき、本体部分に m - 1 回の
「3n + 2」操作を行なったものが、コラッツむしの“真の体長”だと
思うことにしよう。
つまり、n がメルセンヌ部分を持っているときは、メルセンヌむしは
“縮んでいる”わけだ。

3n + 1 操作を受けた“伸びた”コラッツむしの下位側には、0（二進数表記。
オフビット）が現れる。ただし、任意個の 0 は“ないのと一緒”なので、
コラッツむしの体長には含まれない。

そこで、「コラッツ予想が正しいかどうか？」は、「コラッツむしの“真の体長”が
際限なく伸びてゆく場合があるか？」という問題に帰着する。

そうなると、本体部分は「４で割って１余る素数」だ。これに 3n + 1 操作を
行なったときに、メルセンヌ部分がどう表れるかという話になる。この
メルセンヌ部分が際限なく表れると、コラッツむしの真の体長が伸びて、
メルセンヌ予想が破綻する。

**１３２人目の素数さん** · 2018/05/28(月) 06:06:43.64

じゃあ、「『メルセンヌ部分を持たないコラッツむし』が『メルセンヌ部分を
持つコラッツむし』に変態する頻度と、変態後の“真の体長”の変化は、
どのようなものか？」という話になる。

“真の体長”が伸びる可能性があるとすれば、それは操作 3n + 1 による。
このとき、3n + 1 操作が可能なのは n ≡ 2(mod 3) の場合だけだ。で、
これに 3n + 1 操作を行なうと、n' は n' ≡ 1(mod 3) になるので 3n + 1 操作は
「一回休み」になる。

2n 操作によって、mod 3 は 1 -> 2 -> 1 -> 2 と変化する。
また、メルセンヌ数の mod 3 は、桁数が多くなるごとに 1・２・１・２と
変わる。

つまるところ、「真の体長を伸ばすようなメルセンヌ部分が、どれだけ
出てくるか？」という話になる。

「山よりでかい猪は出ない」わけで、真の体長よりも“長い”メルセンヌ部分が
出ることはない。これを踏まえて、「コラッツむしの真の体長が無限に伸びる
ことがあるのか？」という話になる。このあたりが mod 3 と mod 4 の
絡み合いで組合せによって解決できて、「伸びるにしても限度がある」ことが
示されれば、メルセンヌ予想は肯定的に解かれたことになる。

こう考えるとわりと単純な話なので、数学の素人でも手を出しやすいような気が
する。もっとも、コラッツ問題自体が「素人にも手をだしやすいが、素人の手には
負えない」問題なんだから、解けるかどうかはまた別の問題なのだが。

**１３２人目の素数さん** · 2018/05/28(月) 08:14:16.23

一応、まとめてみる。

自然数 p と q を考えよう。

とりあえず、p は措いておいて q について考える。

2^q - 3 は、2 < q のときに、二進数で q - 1 桁になる。いちおう、
「q が 1 のとき、結果がマイナスになるのだが、ちゃんと考えてるか？」
とかいった話もあるが、ここでは正の数だけを考えることにする。

つぎに、メルセンヌ数 p^2 - 1 を考える。これは p - 1 桁の数になる。

これを結合したビット列を考えよう。それは (2^p - 1) + 2^p × (2^q - 3) であり、
桁数としては (p - 1)+(q - 1) 桁であるから、p + q - 2 となる。

このとき、「2^q - 3 に『三倍して２を足す』操作を p 回繰り返した結果に
コラッツ操作を施すことで、どれほどの桁数（これを n とする）になり、
最下位に何桁（これを m とする）のメルセンヌ数が出てくるか？」を
考える（m < n であることに注意）。

m と n を p と q の関数で表して、 n - m が q - 1 よりもどんどん大きく
なっていったら、コラッツ予想は「はずれ」だということになる。

おそらく、最悪のケースで見積もると、“爆発”（無限大に発散）すると思う。
そうでなかったら、コラッツ問題はとっくに解決しているはずだ。
だから、相当にややこしいテクニックを駆使して「最悪のケース」を避けて
「無限大には発散しない」ことが示せれば、コラッツ予想は肯定的に証明される
ことになる。

そんなにうまくゆくとも思えないし、可能だとしても相当に苦労するだろうとは
思うのだが、方向性としてはちょっと新しいように思うので、「難しい」とか
「ダメっぽい」とか「ここから先で行き詰まった」くらいの実績は残しておいても
いいと思う。
コラッツ予想に関する「やってみたけどダメだった」的な論文というのは
山ほどあるのだから、いまさら何本かのクズ論文が増えたところで
文句を言う奴もおるまい。

**128** · 2018/05/28(月) 08:25:18.74

>137
既知の情報だったようですね。失礼いたしました

>146
何かしらのお役に立てたのなら幸いです。

**１３２人目の素数さん** · 2018/05/28(月) 09:44:13.47

>>150 ＞＞128
> 既知の情報だったようですね。失礼いたしました
いやいや、２ちゃん（今は「５ちゃん」だが）でガイシュツは恥ではない。
お気にならさず。

> 何かしらのお役に立てたのなら幸いです。
本当に役に立った。ありがとう m(_ _)m

ついでながら、>>149 の
> 2^q - 3 は、2 < q のときに、二進数で q - 1 桁になる。
というのは、「５以上の４で割って１余る奇数」のうち、いちばん
みっしりビットが詰まったやつのことである。
このあたりのコンセプトの整理には、本スレに参加している諸氏の意見が
非常に役立った。併せて感謝申し上げる。ありがとうm(_ _)m

**１３２人目の素数さん** · 2018/05/28(月) 12:54:56.22

ようやく前786氏の言ってることがちょっとだけ理解できたような気がする。
「Z/pZ」（つーか、どうせ自然数なんだから「N/pN」で構わんと思うんだが、
それは「整数論」という括りでいうと「自然数に 0 が入っちゃまずいだろう」という
配慮があるんだろうと思う）というのは、単なる剰余系であって、
「何に関して閉じているか」っつーのは、また別の話なんだよな？

そもそも、「+1 する」という操作に対して p の剰余系 Z/pZ は閉じているので、
「Z/nZ（+1）」は閉じているわけだ。

で、n が p の原始根だとすると、Z/pN が「Z/nZ（×n）について閉じていて、
しかも網羅的である」っつー話なんだよな？

だけど、Z/pZ に対して、任意の i かなんかを持ってくると、Z/nZ（×i）というのは
、「全部廻れる」わけじゃないので、Z/pZ の部分群の和集合という形に
なるんだよな？

で、たぶん前786氏は、「そのあたりを、（Z/pZの）すべての p に対して
（すべての i に対して）ツブしていけば、どっかで何とかなりそうな気がする」と
いう気がするので、「i = 2」に関してツブしてゆこう、という話ではないかと思う。

オレは何かヘンなことを言っていると思ったら、ツッコミを入れてほしい。歓迎する。

**前786** ◆5A/gU5yzeU · 2018/05/28(月) 15:03:52.79

2 に注目しているのは、
コラッツ操作の「偶数を 2 で割る」
逆操作の「2 をかける」
から来ています。
証明を考えていくと自然とそうなりました。

>「Z/pZ」（つーか、どうせ自然数なんだから「N/pN」で構わんと思うんだが、
>それは「整数論」という括りでいうと「自然数に 0 が入っちゃまずいだろう」という
>配慮があるんだろうと思う）というのは、単なる剰余系であって、
>「何に関して閉じているか」っつーのは、また別の話なんだよな？
ここで何を気にされてるのかいまいちよく分かりませんが、
「閉じている」という表現は全体の一部分を見ているときに使う表現なので、この場合適切でないと思います。

例. 整数全体の中の奇数の集合は、積について閉じていて和について閉じていない。

「どういう演算を考えているか」を気にしているということでしょうか？

あと一応もう一つ言葉にツッコんでおきますと、
>だけど、Z/pZ に対して、任意の i かなんかを持ってくると、Z/nZ（×i）というのは
>、「全部廻れる」わけじゃないので、Z/pZ の部分群の和集合という形に
>なるんだよな？
この「部分群」もちょっと用法がおかしいです。
例えば Z/7Z を {0},{1,2,4},{3,5,6} に分ける、というような操作に関しての発言だと思いますが、
これを表現したければ「軌道」と言うのが適切かと思います（群論の言葉です）。

**前786** ◆5A/gU5yzeU · 2018/05/28(月) 15:04:43.97

2 に注目していることについては、
例えば次のような問題を考えれば納得できると思います。

問. どんな自然数からでも、コラッツ操作とコラッツ逆操作を繰り返すことで 9 の倍数に到達できるか？

**１３２人目の素数さん** · 2018/05/28(月) 15:27:05.72

スレの流れからいうと不規則発言なので、「そういうコトを言っている香具師がいる」
くらいに思ってほしい。

なんとなく問題の本質が見えてきたような気がするので、「コラッツ予想」
「コラッツ問題」に関して「他の研究者は、どんなアプローチを取っているんだろうか？」と
思って検索してみた。

　そうすると、「3n + 1 問題」の 3 を「一般の k に拡張したときに」とかいう話が
多いんだよね。

　「逃げちゃダメだ、逃げちゃダメだ、逃げちゃダメだ」と思う。そんなもん、
「3n + 1」を解決してから考えろ、と思う。

mod k からアプローチするのは、基本的に“あり”だと思う。だけど整数論
（群とか環とか体とか）に関していうと、あんまり道具としては使いやすくないので
、「果たして有効だろうか？」と思う。まぁ、数学の素人が言うこったから、
「ふぅーん、あんたはそう思うのね？」くらいの感じで聞き流してくれても
まったく問題がないのだが。

だいたい、「数学」っつーのは“無限”を相手にすることが多い。「実用的な範囲で、
どれくらい抑え込めるのか？」っつーのは、どっちかっていうと有限組合せ数学とか
の範囲の仕事なのだ。だから、純粋数学畑の人はあんまり興味を持たないと思うし、
数式処理システムとか実験数学とかいったものとかとは距離を置きたいと思うのが
当然だと思う。

あとは「整数論方面のほうからのアプローチがどこまで通じるか」という期待が
あるのだが、そっち方面の研究って、あんまり進んでないような気がする。
「有限束の数え上げ」とか「魔円陣（完全ゴロム環）」とかいった話題は、
もう十年以上も取りあげられていないような気がする。

てなワケで、燃料を投下してみた。敲いてくださって結構。かかってらっしゃい。
数学はまるでダメだが、伊達に長年ネットでのたくっていたワケでもないので、
口だけは達者だ。

**１３２人目の素数さん** · 2018/05/28(月) 15:54:28.71

>>153
おお、数学屋さんがマトモに応答してくれるとは光栄だ。これは皮肉ではない。
本当にそう思っている。

> 2 に注目しているのは、
> コラッツ操作の「偶数を 2 で割る」
> 逆操作の「2 をかける」
> から来ています。

私はビット列として考えているので、“コラッツむし”みたいな概念で「シフト演算」
あるいは「ヌルビットの除去」というイメージで捉えているのだ。このあたり、
プログラマという商売柄がある。そんなわけで、「だったら、コテハン（固定ハンドル）を
使って立場を明確にしろ」ということであれば、対応するつもりだ。

**１３２人目の素数さん** · 2018/05/28(月) 15:56:30.55

>>153 つづき
>>「Z/pZ」（つーか、どうせ自然数なんだから「N/pN」で構わんと思うんだが、
>> それは「整数論」という括りでいうと「自然数に 0 が入っちゃまずいだろう」という
>> 配慮があるんだろうと思う）というのは、単なる剰余系であって、
>> 「何に関して閉じているか」っつーのは、また別の話なんだよな？

> ここで何を気にされてるのかいまいちよく分かりませんが、
> 「閉じている」という表現は全体の一部分を見ているときに使う表現なので、
> この場合適切でないと思います。
>
> 例. 整数全体の中の奇数の集合は、積について閉じていて和について閉じていない。
>
> 「どういう演算を考えているか」を気にしているということでしょうか？

「群論」というと、整数論をちょっと齧った人間としては、まず「循環群」
（その集合の要素をすべて網羅すること）を連想してしまうのだよ。
だから、「2 をかける」という操作よりも、「3n + 1 という操作に関して、
その有限集合が閉じているか？」が気になってしまうのだ。そういう意味では、
「どういう演算を考えているか」が気になる。

**１３２人目の素数さん** · 2018/05/28(月) 15:57:44.90

>>153 さらにつづき
> あと一応もう一つ言葉にツッコんでおきますと、
>> だけど、Z/pZ に対して、任意の i かなんかを持ってくると、Z/nZ（×i）というのは、
>> 「全部廻れる」わけじゃないので、Z/pZ の部分群の和集合という形に
>> なるんだよな？
> この「部分群」もちょっと用法がおかしいです。
> 例えば Z/7Z を {0},{1,2,4},{3,5,6} に分ける、というような操作に関しての
> 発言だと思いますが、
> これを表現したければ「軌道」と言うのが適切かと思います（群論の言葉です）。

済まぬ m(_ _)m。「軌道」という言葉は別のサイトで使っちゃってたので、
あえて避けた部分がある。
「軌道」によって排他的（重なる要素がない）集合に分割される「群」の
部分集合、という意味で「部分群」という言葉を使っただけだ。

コラッツ集合を表す「木」という言葉も、「根本のほうで循環してるんだから、
『木』っておかしくねぇか？」みたいな議論は前スレでもあったと思うが、
「ビット列の中で、最初のオンビットから最後のオンビットまでを
“コラッツむし”と命名する」みたいなコンセプトで、「根っこが 1 ビットである
木構造」と捉えると、「木」と呼んでもしっくりくると思うのだが。

**１３２人目の素数さん** · 2018/05/28(月) 16:37:50.04

>>154
> 問）どんな自然数からでも、コラッツ操作とコラッツ逆操作を繰り返すことで
> 9 の倍数に到達できるか？

なんとなく意味は分かるのだが、どういう問題意識があるのかがピンとこない。
mod p の木に奇数 m があり、mod q の木に奇数 q があったとすると、（p と q が
互いに素だとして）Z/pqZ 上では「根である 1 まで下がって、また上がってくりゃ
いいだけの話じゃん？」と思う。

　「p と q の直近の（いちばん近い）共通の奇数 x があり、それぞれコラッツ操作に
よって x -> p と x -> q に至るルートを（効率よく）求める方法を（コラッツ操作と
コラッツ逆操作をそれぞれ用いることで）示せ」っつーんなら、「ひょっとしたら、
なんとかなるかも知れん（オレが出来るとは言わんが）」くらいのことは言えるが。

**前786** ◆5A/gU5yzeU · 2018/05/28(月) 17:29:14.11

>>159
私が考えているのは
「コラッツ予想は、初期値が n で割って k 余る数だけ考えれば十分である」
というのがどんな n, k についても成り立つか、という問題です。

それを証明するための一つの手段として、
「どんな自然数からでも、コラッツ操作とコラッツ逆操作を繰り返すことで n で割って k 余る数に到達できる」
を示そうと思っています。

ところで「mod p の木」とか「mod q の木」などと私は一度も言っていませんが、何の話でしょうか。
Z/pqZ 上では「根である 1 まで下がって、また上がってくりゃいいだけの話じゃん？」、というのも意味がよく分かりません。

Mb · 2018/05/28(月) 19:08:02.21

>>160
要するに、
> 「コラッツ予想は、初期値が n で割って k 余る数だけ考えれば十分である」
> というのがどんな n, k についても成り立つか
というのは、
「コラッツ予想は、x ≡ k(mod n) だけ考えれば十分であるというのが、
どんな n, k についても成り立つか？」っつーのと同じことを謂っているように
思うのだが、うちらは「そのあたりに関しては、mod 3 と mod 4 の絡み合いに
関係していそうなので、なんだかんだで場合分けがややこしいことになりそうだ」
という話をしているだけなのだ。

そこで、
> それを証明するための一つの手段として、
> 「どんな自然数からでも、コラッツ操作とコラッツ逆操作を繰り返すことで
> n で割って k 余る数に到達できる」
> を示そうと思っています。
というのが、「コラッツ操作」と「コラッツ逆操作」を混在させてしまうと、
なんとなく迷走してしまいそうで、心配しているだけだ。

その発想だと、「共通の“節点”であるどこか」を経由しないといかんような気が
するので、「根であるところの 1 へのルートをそれぞれについて求めて、
その差分を取る」みたいなアプローチが成功しそうに思う。

あくまで個人的な感想なのだが。

Mb · 2018/05/28(月) 19:28:33.47

>>160
> ところで「mod p の木」とか「mod q の木」などと私は一度も言っていませんが、
> 何の話でしょうか。

原始根は複数個ありうるので、巡回群（剰余系における、全部の要素を辿る乗数系）も
複数個ありうるのだが、「一部の要素」をフォローする（単一の）乗数と、「その他の
要素」をフォローする乗数（その他大勢）が、全体として Z/pZ を隈なく覆う、
という「グループとしての、木の集まり」というものを考えて、「その集まりを
考えたときに、木の本数が、ある一定数よりも大きくならない」ということを
謂っているんだろうと思っているのだ。

それを考えると、「どこかの木に属している」ということは、「他の木に属していない」
という意味になりそうな気がするわけで、そうした「排他的な木」としての
「mod p の木」とか「mod q の木」という概念はあっていいような気がするし、
それぞれの木が排他的に「すべての自然数」を所有しているとすると、
「グループとしての、木の集まり」がコラッツ問題をカバーしていることになり、
Z/(全部の木の基数の積)Z の存在を示すことができれば、コラッツ予想が肯定的に
証明できることになるような気がする。

**前786** ◆5A/gU5yzeU · 2018/05/28(月) 21:38:47.13

>>161
mod 3 と mod 4 の絡み合いでややこしくなるとか、コラッツ操作とコラッツ逆操作を混在させて迷走しそうとか
心配はありがたいのですが、既に多数の n や k について証明できているのは見ていただけてるでしょうか。
「なんとなく」の印象だけで話されても困ります。

>>162
>「一部の要素」をフォローする（単一の）乗数
原始根にならない元のことでしょうか。よく分かりません。
数学の言葉でお願いします。

>「その他の要素」をフォローする乗数（その他大勢）
ここはもっとよく分かりません。

>Z/pZ を隈なく覆う、という「グループとしての、木の集まり」
軌道のことでしょうか。

>「その集まりを考えたときに、木の本数が、ある一定数よりも大きくならない」ということを謂っている
なんのことでしょうか。

**righ1113** ◆OPKWA8uhcY · 2018/05/28(月) 22:20:56.19

>>142-145
説明ありがとうございます。完全に理解したとは言えないのですが……
このプログラムの実行には12時間以上かかったので、無駄にならなくて良かったです。

**１３２人目の素数さん** · 2018/05/28(月) 22:30:29.54

若干スレが荒れぎみですがこれも2chの華ですかね？

**前786** ◆5A/gU5yzeU · 2018/05/29(火) 08:17:04.68

>>164
よく粘りましたねｗ
逆に言えば、プログラムで数千、数万回計算して得られた結論がたった３レスで説明できた訳ですから、
この考え方をうまくプログラムに落としこめれば計算量を大幅に削減できる可能性も……

>>165
私の発言でそう思わせてしまったなら申し訳ありません。

**１３２人目の素数さん** · 2018/05/29(火) 14:20:35.00

「すべての自然数 N に対して、偶数は（素因数分解したときの 2 の乗数について
割ったら）奇数に帰着する。

「『４で割って３余る奇数』は、ビット列で表現したときに、下位のオンビット列
（一個以上のビット列が並んでいるビットパターン）」に帰着するので、
「４で割って３余る奇数」に帰着する。

そうすると、「４で割って１余る奇数」に帰着するすべての自然数が、3n + 1 操作に
対して、「４で割って１余る奇数」に帰着するかどうかが問題になるわけだから、
「ある『n ≡ 1(mod 4)の数が、(3n + 1)/2 操作によって、『n' ≡ 1(mod 4)の数』に
なるとき、n' が単調増加して無限大に発散するかどうか？」という話に帰着する。

そんなわけで、そのとき、2 で割ったときに、「『2 < n| 2^n - 1』が無限連鎖するか？」という話になる。

自分は数学屋ではないので、数式を追っかけて解決する自信がない。

数値実験で見当をつけようと思う。

ロジックに穴があったら指摘していただきたい。m(_ _)m

**righ1113** ◆OPKWA8uhcY · 2018/05/29(火) 18:52:19.94

>>167
最後がよく分からないです。

>　2 で割ったときに、「『2 < n| 2^n - 1』が無限連鎖するか？」
詳しい説明が欲しいです。
例えば、ビット列で言うとこう、とか
プログラム(アルゴリズム)で書くとこう、とか。

**１３２人目の素数さん** · 2018/05/29(火) 19:02:13.73

>>166
まあここまでが順調過ぎましたからね
今の方が本来の2chの姿に近いかも
あまりガッカリせずに気長に行きましょう

**１３２人目の素数さん** · 2018/05/29(火) 21:09:33.77

>>167
> 最後がよく分からないです。
>>　2 で割ったときに、「『2 < n| 2^n - 1』が無限連鎖するか？」
> 詳しい説明が欲しいです。

あ、ごめん。言葉が足りなかった。
最下位に「連続した２個以上のオンビットがある」というのが
n ≡ 3(mod 4)
ということなわけで、
その場合は「下位のメルセンヌ部分を除去したビット列に、
3n + 2 操作を行ないつづけることで、n ≡ 1(mod 4) に帰着する」
ということが謂える。
だから、「メルセンヌ部分を除いた本体が、増えるか減るか」が
肝心なところであって、「最下位に一個以上の 0 があって、本体の長さが
減る」のか、「最下位に二個以上の 1 が現れて、本体の長さが増える」のかが
問題になるわけだ。

その部分に着目すると、コラッツ操作の逆操作を考えたときに、かなり計算量が
減るように思うので、「コラッツ予想は 5 × 2^60 までは成り立つ」みたいな
ショボい話（IEEE の long よりも小さい）ではなくて、メルセンヌ素数的な
デカい数まで（たとえば 10^100 とかまで）コラッツ予想は成り立つことが、
“数値実験的に”ではなく、“数学的に”（といっても、コンピュータによる
実験的な検証が入っているので、数学的な厳密性に欠けているという点については
完璧ではないのだが）「コラッツ予想は成立する」と断言しちゃっていい、
みたいな話になると思うのだ。

**１３２人目の素数さん** · 2018/05/29(火) 21:10:17.02

少なくとも、「フツーにプログラムを動かしていたら、例外が見つかった」とか、
飛行機が堕ちて死ぬとか巨大彗星が堕ちてきて人類が滅亡するとか、そういった
確率の何百万分の１以下のところまで絞りこめれば、「実用的には、コラッツ問題は
解決した」（とはいえ、コラッツ問題の実用性というのが、あるとは思えないが）と
言っちゃっていいと思う。
暗号理論だって、「偶然、解読のための鍵が見つかっちゃう確率は 0 ではない」という
意味では完璧ではないわけで、「じゃあ、具体的には、コラッツ予想は、どこまでの
範囲で成り立つのか？」という限界を、「可能性がありそうな部分を、一個づつ
ブルート・フォース・アプローチによって潰してゆく」より効率のよさそうな方法で
ツブしてゆくというアプローチがありそうに思う。

で、その過程で、「なんか、こっから先にはなんにもなさそうな気がする」という
限界がうっすらと見えてきたら、そこから逆に「じゃあ、このあたりには何があるの？」とかいった見当がつくのかもしれない、と思う。

コラッツ予想はメルセンヌ素数 8,191 に絡んで、2^8191 - 1 あたりで組合せ論的には
頭打ちになると思う。実際にメルセンヌ数から出発してメルセンヌ数に落ちるケースは
127 かなんかが最高だったので、あとは「メルセンヌ数ではない数から出発して、
3n + 1 操作“のみ”によってメルセンヌ数に落ちる」ケースを潰してゆけば、
コラッツ予想が成立する限界点はもっと先まで確認できるように思うし、
ひょっとしたら（四色問題や有限群の分類みたいに）「この先は、組合せ論的にいって
ありえない」みたいなコトになるかもしれない（とはいえ、私は数学の専門家では
ないので、数学者の誰かが証明できたとしても、その証明を理解できる自信は
まったくないのだが(-_-!)）。

てなワケで、現在探索を続行中。

**１３２人目の素数さん** · 2018/05/29(火) 21:15:32.62

>>171
探索を実行中ってことはもうプログラムがあるってこと？
なんなら>>1みたいに晒してくれてもいいのよ？

**１３２人目の素数さん** · 2018/05/29(火) 21:38:00.75

>>168
ごちゃごちゃ長文を書いてしまって申し訳ない。m(_ _)m

要するに、「いままで、『n 以下までにはコラッツ予想の
反例はない』というのを示すのに O(n) の手間がかかって
いたのだが、それを O(lon(n)) に持ってくことができたら、
5*2^60 とかいうショボい話じゃなくて、 2^127 くらい
までは（できれば 2^4095 くらいまでは）持ってけねぇか？」
っつー話。

>>172
> 探索を実行中ってことはもうプログラムがあるってこと？
『Java の宿題ここで答えます』の回答者側の常連だったので、
「とりあえず動く」レベルのものはあるのだが、やっつけで
書いたもんだから（これが Hacker というものだ）あんまり
フツーのプログラマが見て分かりやすいモンじゃねぇんだよな(-_-!)
自前でやってる WebLog のほうに、近々さらすことにして、
ソーズはもうちょっと洗濯させてくれ m(_ _)m

**righ1113** ◆OPKWA8uhcY · 2018/05/29(火) 22:09:23.31

>>173
今ひとつ分からないので、自分はソースを待ちます。

**１３２人目の素数さん** · 2018/05/29(火) 22:34:19.60

やはり>>786が論理を構築し>>1がその論理をプログラムで実装するというのがこのスレのベストプラクティス。
なにかいいネタはないかな。

**righ1113** ◆OPKWA8uhcY · 2018/05/29(火) 22:53:33.64

>>175
>>111とか、どうですかね?

**１３２人目の素数さん** · 2018/05/29(火) 23:17:54.07

いまいちよくわかってないんだが>>111の①②③はそれぞれ別々に証明する必要があるってこと？
で①②③がいえれば④がいえるってこと？

**前786** ◆5A/gU5yzeU · 2018/05/29(火) 23:19:19.88

>>175
プログラムの結果を参考にして証明を進める、までできれば私としてはベストですね。
今は>>166で書いた案について考え中。

>>176
>>111の①はなんとかなるかもしれません。
「繰り返すと１つになる」というよりは「繰り返しても集合の個数が増えない」という論法になりそうです。
ちょうど>>166のアイデアにも関連します。
このあと軽く説明します。

**righ1113** ◆OPKWA8uhcY · 2018/05/29(火) 23:30:01.77

>>177
①と②は対偶関係なので、
①を証明する→③を証明する→④が言える
です。

**前786** ◆5A/gU5yzeU · 2018/05/29(火) 23:38:41.79

そもそも>>92の説明がなぜあれだけで済んだのかというと

・mod 7*19 で考えるところを、mod 7 と mod19 に分けた。

・mod 7*19^2 で考えるところを mod 7 と mod 19^2 に分け、
　さらに mod 19^2 で考えるところは実質 mod 19 で考えるだけで済んだ。

ということが効いているんじゃないかと思います。
それで、一つ目はおいといて二つ目の
　mod 19^2 で考えるところが mod 19 で済む
という部分がポイントで、
こういうのが許されるのはちょうど「C を繰り返して集合が増えないとき」になりそうなんです。

さらに、プログラムを進めていくとどこかで「繰り返しても集合が増えない」となることも証明できそうなので、
これを利用してプログラムの計算量を減らせそう、という考えです。

時間があるときにちゃんと考えようと思います。

**前786** ◆5A/gU5yzeU · 2018/05/29(火) 23:51:01.24

（実際のところ、>>154が分かる人がどのくらいるのかちょっと気になる）

**righ1113** ◆OPKWA8uhcY · 2018/05/30(水) 00:00:21.34

>>181
自分は分かっている……つもりです……

**１３２人目の素数さん** · 2018/05/30(水) 05:29:09.70

2倍の繰り返しで
1→2→4→8→16≡7→14≡5→10≡1
0→1
3の倍数が残るけど2で割り続けて奇数になったあと
3n→3n×3+1≡1

でおしまい

2倍は「好きなだけ遡れる」ところがポイントかね

**１３２人目の素数さん** · 2018/05/30(水) 07:45:42.08

13 だったらまだ理解できるんだがな。

1 → 2 → 4 → 8 → 16 ≡ 3 → 6 → 12 → 11 → 9
→ 18 ≡ 5 → 10 → 20 ≡ 7

つーても、これがコラッツ予想の解決とどう結びつくのかがわからんが。

**１３２人目の素数さん** · 2018/05/30(水) 07:46:53.88

あ、
×

**１３２人目の素数さん** · 2018/05/30(水) 07:48:45.57

あ、
× 12 → 11 → 9
〇 12 → 24 ≡ 11 → 22 ≡ 9
だった。

**１３２人目の素数さん** · 2018/05/30(水) 08:09:47.45

mod 7、三倍（原始根は 3）
1 → 3 → 9 ≡2 → 6 → 18 ≡ 4 → 12 ≡ 5 → 15 ≡ 1

mod 19、二倍（原始根は 2）
1 → 2 → 4 → 8 → 16 → 32 ≡ 13 → 26 ≡ 7 → 14 →
28 ≡ 9 → 18 → 36 ≡ 10 → 20 ≡ 1

あたりが関係してくるらしいのは見当がつくんだが、
3n + 1 で巡回することを考えてみたらいいのか、
それとも 3 で割って 2 余る数について逆操作の (2n - 1)/3 を
考えたらいいのか …… わからん。

**前786** ◆5A/gU5yzeU · 2018/05/30(水) 08:32:25.52

>>183
残念
Z/9Z において 0→1 (3倍して1を足す) は可逆でないので、これだと不十分です。

実際、この方針で例えば 16 から 9 の倍数を作ろうとすると、
2 を 2 回かけて 16→32→64
1 を引いて 3 で割って 64→21
で、9 の倍数になりません。

>>184
確かに私の予想が証明できてもすぐにはコラッツ予想に繋がりませんが、
まあ外堀を埋めるような感覚です。
それに、もし万が一私の予想に反例が見つかれば、その時点でコラッツ予想も不成立となるので、
そういう意味ではコラッツ予想を直接攻めていると言えなくもないかなと。

**１３２人目の素数さん** · 2018/05/30(水) 15:44:56.54

>> 174
> 今ひとつ分からないので、自分はソースを待ちます。
ただ待たせっぱなしにするのも気づまりなので、
「メルセンヌ数から 1 に落ちる途中でメルセンヌ数を経由する」
という例は挙げておこうと思う。

7 <- メルセンヌ素数の 2 番
31 <- メルセンヌ素数の 3 番
127 <- 1 メルセンヌ素数の 4 番

511: 7 を経由
2047: 127 を経由
4095: 127 を経由
8191: 127 を経由
16383: 127 を経由
131071 <- メルセンヌ素数の 6 番。経由せず。
262143: メルセンヌ素数の 7 番。経由せず。
524287: 7 を経由
1048575: 7 を経由
2097151: 31 を経由
4194303: 31 を経由

でもって、

2^61 - 1 -> 31
2^62 - 1 -> 31
2^63 - 1 -> 31
2^64 - 1 -> 31

とかいう話になっているので、「コラッツ予想は数値実験によって
5*2^60 まで正しいことが確認されている」とかいった WikiPedia の
記述は、このあたりに絡んでいるのかもしれないと思う。

**righ1113** ◆OPKWA8uhcY · 2018/05/30(水) 18:37:06.75

>>189
下位に2^n-1が出てくるだけじゃなくて、実際のメルセンヌ数も絡むの?!
ますます分からなくなる(>_<)

**１３２人目の素数さん** · 2018/05/30(水) 19:01:13.88

>>190
> 下位に2^n-1が出てくるだけじゃなくて、実際のメルセンヌ数も絡むの?!
> ますます分からなくなる(>_<)

だからコラッツ問題は面白いんじゃないですか (^_^)v

**１３２人目の素数さん** · 2018/05/30(水) 21:14:57.31

そういえば剰余コラッツ予想(前>>786の予想)の反例が見つかったと仮定して、
その反例から元のコラッツ予想の反例を求めることは簡単なの？

**前786** ◆5A/gU5yzeU · 2018/05/30(水) 23:24:08.24

>>192
（その名前使ってくれてありがとう）
これは簡単です。

剰余コラッツ予想の反例があるということは、
ある自然数 a,n,k が存在して
「a からコラッツ操作、コラッツ逆操作を繰り返しても、n で割って k 余る数に到達できない」
ということです。
このとき特に、a から k に到達することができません。

ここで、もし a,k が共にコラッツ操作で 1 になるとすると、
a→1→k のルートで a から k に到達できてしまい矛盾します。
したがって、a,k のいずれかがコラッツ予想の反例となります。

**１３２人目の素数さん** · 2018/05/30(水) 23:43:24.81

え、じゃあa,kのいずれかは5*2^60より大きくなきゃいけないってことか

**前786** ◆5A/gU5yzeU · 2018/05/31(木) 00:03:29.44

>>194
あ、ほんとだ
素で気づいてませんでした。

ちょっとこれは認識を改めないといけないかもしれない

**righ1113** ◆OPKWA8uhcY · 2018/05/31(木) 00:15:22.71

プログラムもそこまでとか、ムリだからねっ

**righ1113** ◆OPKWA8uhcY · 2018/05/31(木) 00:24:01.59

>>195
ちなみに今のプログラムで反例が見つかっても>>193に繋げられる?

**前786** ◆5A/gU5yzeU · 2018/05/31(木) 00:41:52.06

>>197
ちょっとまだ分かりません。
反例が見つかったら考えようと思っていました。

ちなみに今のプログラムは剰余コラッツ予想を完全に確かめられるものではない（>>101の話）ので、
5*2^60 以下でもプログラムでの反例が見つかる可能性はあります。

**righ1113** ◆OPKWA8uhcY · 2018/05/31(木) 00:46:19.98

弱い成果が得られるやつですよね。

**前786** ◆5A/gU5yzeU · 2018/05/31(木) 00:58:27.40

そうですそうです。