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

**１３２人目の素数さん** · 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

そうですそうです。

**１３２人目の素数さん** · 2018/06/02(土) 21:15:03.31

n ≡ 1 (mod 4) に 3n + 2 操作を（連続して）行なったときに
何が出てくるかと、
n ≡ 1 (mod 4)に 3n + 1 操作を行なったときに、
n ≡ 0 (mod 2) と 1 ≡ 3 (mod 4) がどんなふうに
出てくるかと、
四進法で 11111 …… がどんなふうに出てくるかで
（これはどっちかというと効率上の問題）、
どうやら 2^63 の壁は突破できそう。
ただ、アルゴリズムの効率がいまひとつなので計算機パワーに
頼っているのと、数学的に理解しやすい表現に落ちないんだよな ……
連分数による無理数の近似を行なおうとすると、φがいちばん
誤差が収束しづらいとか、そんな話になりそうなんだよな。
遠山啓先生の『初等整数論』の終わりのほうにもそんな話が
出てきてて、「うーん、オレが求めているのは、
そういう結果じゃないんだけどな」と思ってはいるんだが。

**１３２人目の素数さん** · 2018/06/07(木) 19:47:31.27

スレが止まってるが大丈夫か？

**righ1113** ◆OPKWA8uhcY · 2018/06/07(木) 21:30:24.45

特に進展がないのです……

**１３２人目の素数さん** · 2018/06/07(木) 21:38:46.18

>>202
「大丈夫だ。問題ない」… とは言えんな。
いまのところ２つのアプローチを考えている。
「下位のオンビット列を切り離して、3n + 2 操作を繰り返したあとに
残った 1(mod 4) に 3n + 1 操作を加えたときに
下位に何が（オンの連続かオフの連続か）出るか（そこで 0(mod 4) が
出るまではいいとしても）」、数学的に考えると「下位のオンビット列を
切り離す」操作をどう考えたらいいかとか、操作が複数になるので
理論的にややこしくなるという問題がある。
かといってそれを素直にビット列で考えてコンピュータで
処理しようと思うと、桁数が多くなる（2^63 を超えたあたり）と
31（2^5 - 1）とかが出てきて収拾がつかなくなりそうな
気がする。
数学的素養にしろコンピュータの性能にしろ、
「そんな装備で大丈夫か？」的な不安はある。

**１３２人目の素数さん** · 2018/06/08(金) 13:40:04.11

数学板でこれを言ったらボロクソに叩かれるのは承知しているが、
「1 ビットに収束するという制約を外して、セルオートマトンで表現する」
とかいった形で画像にしてみて、
その画像に FFT とかウェーブレット変換とかをかけて挙動を推測する、
とかいうアプローチはあるんじゃねぇ？
画像で表現したときに、「最終的にONな 1 ビットが移動するだけ」になるのは
（実験的には）確認されているんだから、画像的に逆三角形が「どん」という
感じで出現するかどうか、っつー話なわけだから。

**１３２人目の素数さん** · 2018/06/08(金) 20:05:54.99

アイディアを出すのは構わないが実装するのはきみだ

**１３２人目の素数さん** · 2018/06/08(金) 20:12:20.69

>>206
> アイディアを出すのは構わないが実装するのはきみだ
解ってる。問題は「他にできる奴がいねぇ」っつー点なんだわ。
やんなくていいから、せめてまともなツッコミくらい
入れてくれないと、気分が萎えるんだよ。

**１３２人目の素数さん** · 2018/06/08(金) 20:43:30.22

まともな突っ込みが欲しければもっとアイディアを具体化してくれ。
まだ突っ込み云々の段階じゃないだろ。

**１３２人目の素数さん** · 2018/06/08(金) 21:15:37.98

>>208
> まともな突っ込みが欲しければもっとアイディアを具体化してくれ。
わかった。要するにお前は
「下位に 0 または 1 が連続するパターンに、
3n + 1 の逆操作を（偶数を経由せずに）1(mod 4) に
至る数の性質を明らかにしろ」っつーコトだな？

そんなもん、簡単にできたら苦労しねぇよ orz

**１３２人目の素数さん** · 2018/06/08(金) 21:50:50.71

>>209
> そんなもん、簡単にできたら苦労しねぇよ orz
いや待て。ちょっと待て。
> 「下位に 0 または 1 が連続するパターンに、
> 3n + 1 の逆操作を（偶数を経由せずに）1(mod 4) に
> 至る数の性質を明らかにしろ」
っつても、「偶数を経由せずに」じゃなくて、
「1(mod 4)を経由せずに」なんじゃねぇの？
（末尾が二進数で 00 とか 01 とか 11 だったら、
別のケースに帰着しちゃうんだから）
これだったら結構効率よく追っかけられそうな
気はするんだよな
頑張ってみる。サンクス。>>208

**１３２人目の素数さん** · 2018/06/09(土) 09:51:12.21

>>210
× 「偶数を経由せずに」じゃなくて、「1(mod 4)を経由せずに」
〇「偶数を経由せずに」じゃなくて、「1(mod 4)だけを経由して」

**righ1113** ◆OPKWA8uhcY · 2018/06/09(土) 19:25:47.19

プログラムを使って、
n=3037から6367までの素数396個、全て正常終了を確認しました。
オールNothing出ないですね……

**１３２人目の素数さん** · 2018/06/09(土) 19:32:18.47

ほほう。
>>1乙です。

**１３２人目の素数さん** · 2018/06/09(土) 19:39:31.39

ちなみに素数に絞ったのはなにか根拠があるんですか？
それともなんとなくですか？

**righ1113** ◆OPKWA8uhcY · 2018/06/09(土) 19:59:06.87

本当はむしろ合成数をやりたかったのです。
素数なら30分で終わるところが、合成数だと2時間かかったり。
ほんで素数にしました。

**１３２人目の素数さん** · 2018/06/09(土) 20:20:31.16

>>212
とりあえずコラッツ予想の反例が出なかった、という意味では
順当な結果だと思います。ともあれご苦労様ですm(_ _)m
そうすると、現時点で「コラッツ予想が成立する数の上限値」と
いうのは、どの程度なんでしょうか。
IEEE の 64 bit INT（＝Java の long）までは反例がない、
とかいった話ではあるんでしょうか。

**righ1113** ◆OPKWA8uhcY · 2018/06/09(土) 20:48:37.47

>>216
>>189の後半に
>「コラッツ予想は数値実験によって
>5*2^60 まで正しいことが確認されている」
>とかいった WikiPedia の記述
があるからそれだと思います。

**１３２人目の素数さん** · 2018/06/10(日) 02:56:21.72

>128ですが、また別のアプローチを試みてみたところ、少し面白い結果が得られたのでご報告。既知の情報だったら申し訳ないですが…

「ある奇数にコラッツ操作(3n+1→奇数になるまで2で割る)を試みた結果どんな数になるか」をまとめたところ、以下のような規則性があるのに気づきました。

操作後の数をＡとして、Ａを３で割った余りが
○1(1.7.13…)の場合：(Ａ*4-1)/3を初項として、以下(4n+1)と掛け合わせた数がＡとなる
(1←1.5.21.85…)(7←9.37.149.597…)

○2(5.11.17…)の場合：(Ａ*2-1)/3を初項として、以下(4n+1)と掛け合わせた数がＡとなる
(5←3.13.53.213…)(11←7.29.117.469…)
○0(3.9.15…)の場合：コラッツ操作でＡになる数は存在しない

一旦切ります。

**218** · 2018/06/10(日) 03:30:20.71

続きです。

で、余り0はほっといて、余り1と余り2をそれぞれまとめてみました。

1： 1. 5. 21. 85. 341. 1365…
7： 9. 37.149. 597. 2389. 9557…
13：17. 69.277.1109. 4437.17749…
19：25.101.405.1621. 6485.25941…
25：33.133.533.2133. 8533.34133…
31：41.165.661.2645.10581.42325…

5： 3.13. 53. 213. 853. 3413…
11： 7.29.117. 469.1877. 7509…
17：11.45.181. 725.2901.11605…
23：15.61.245. 981.3925.15701…
29：19.77.309.1237.4949.19797…
35：23.93.373.1493.5973.23893…

…縦と横を入れ替えると、全部等差数列になってるんですよね、これ。

もう少し続きます。

**218** · 2018/06/10(日) 03:41:04.40

続きです。長くなってしまって申し訳ない。

3.7.11.5.19.23　初項3　公差4
1.9.17.25.33.41　初項1　公差8
13.29.45.61.77.93　初項13　公差16
5.37.69.101.133.165　初項5　公差32
53.117.181.245.309.373　初項53　公差64
21.149.277.405.533.661　初項21　公差128
213.469.725.981.1237.1493　初項213　公差256
85.597.1109.1621.2133.2645　初項85　公差512
853.1877.2901.3925.4949.5973　初項853　公差1024
341.2389.4437.6485.8533.10581　初項341　公差2048
3413.7509.11605.15701.19797.23893　初項3413　公差4096
1365.9557.17749.25941.34133.42325　初項1365　公差8192

…。

1+2=3
3+2=5
5+8=13
13+8=21
21+32=53
53+32=85
85+128=213
213+128=341
341+512=853
853+512=1365
1365+2048=3413

なんていう分布を見ると、「それぞれの項目が重なり合わないように敷き詰められている」ように思えてなりません。素人なんではっきり証明できる力はないのですがorz

以上、気づいた点のご報告でした。
スレ汚し失礼いたしました。

**１３２人目の素数さん** · 2018/06/10(日) 08:07:49.10

初項2x+1 (x:整数)
漸化式 a_(n+1)=4 a_n+1
で与えられる数列の各項はコラッツ予想の操作で合流する

(2x+1)×3+1=6x+4
(4(2x+1)+1)×3+1=24x+16=4(6x+4)

一般項a_n=((6x+4)/3)^n-1/3

**１３２人目の素数さん** · 2018/06/10(日) 08:29:53.23

重ならないように、というのは、
×4+1した隙間の奇数が次々に出てくるのかな

**１３２人目の素数さん** · 2018/06/10(日) 09:11:07.49

>>202
> 「それぞれの項目が重なり合わないように敷き詰められている」ように思えてなりません。
コラッツ予想は、言い方を変えると「４で割って３余るすべての奇数は、
『３倍して１を足す』『２で割る』という二つの操作によって、
１を根とした二分木上に一意に配置される」ということだから、
その認識は正しいと思います。

> 素人なんではっきり証明できる力はないのですがorz
まぁまぁ、そうおっしゃらずに。数学者は数学的な道具の取り扱いに長けているので、
つい自分の使い慣れた道具で扱おうとして、結果的に灯下探索症候群に
陥ることもあるようですから、素人目線も重要ですよ。
行列を使って永らく未解決だった問題が、連分数や図的解法（古代メソポタミアでは
普通に使われていましたが、二十一世紀に再評価されるまで、ほとんど博物館の
展示物扱いでした）であっさり解けちゃった例もありますし。
ヘヴィサイドの演算子法みたいに、「とにかく解けるんだからいいじゃないか」と
いうのに後から数学的なリクツがついてきた、という例もあるので。

**１３２人目の素数さん** · 2018/06/10(日) 09:27:08.31

>>218 の指摘は、「二分木上に一意に配置される」という観点からいうと、
ある「４で割って1 余る奇数」を d （odd の d です。o だとゼロと紛らわしい
ので）としたとき、「d が d≡0(mod 3)のときには、そこより先に（次の数 d' が
出てくるような）枝はない」「d が d≡1(mod 3)のときには、奇数枝が出ないので、
あるとすれば偶数枝の先に d' がある」「d が d≡2(mod 3)のときには奇数枝も
出るので、奇数枝と偶数枝の両方の先に d' （とか d'' とか）がある可能性がある」という
話になるんじゃないか、と思います。ですから、非常に納得のゆく視点です。
等差級数うんぬんの話というのは、そこから自然に導かれる帰結なのでは
ないでしょうか。

**１３２人目の素数さん** · 2018/06/10(日) 09:38:45.60

>>224
ごめんなさい。「奇数枝」というのは、「(3n + 1) / 2 操作によって
奇数に至るルート」なので、途中で偶数を経由しています。したがって、
「3n + 1 操作」ベースで考えると、「それは偶数枝として一般的に
扱ったほうが適切なんじゃねぇんの？」という批判は（たぶん）
あるかと思います。

**１３２人目の素数さん** · 2018/06/10(日) 11:33:20.33

1
2
4←1
8
16←5
32
64←21
128
256←85
512
…

5
10←3
20
40←13
80
160←53
320
640←213
1280
…

**１３２人目の素数さん** · 2018/06/10(日) 11:48:45.88

一般化するとこんな感じで枝分かれを繰り返してくわけだが

6n+1
12n+2
24n+4←8n+1
48n+8
96n+16←16n+5
192n+32
384n+64←128n+13
…

6n+5
12n+10←4n+3 「奇数枝」はここかな？
24n+20
48n+40←16n+13
96n+80
192n+160←64n+53
…

**１３２人目の素数さん** · 2018/06/10(日) 13:29:24.03

>>227
> 12n+10←4n+3 「奇数枝」はここかな？
よく分からんが、たぶんそうだと思う。
>>114 の再録になるが、
> 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/06/10(日) 13:37:00.64

あ、念のため。
このスレに集っている方々にとっては常識だろうけれど、
‘☆’がついてるのは、三の倍数（n ≡ 0 (mod 3)）の場合な？
「偉そうに」とか「上から目線」とか、そう思われるのは
不本意なので。

**righ1113** ◆OPKWA8uhcY · 2018/06/10(日) 15:13:02.69

>>218
自分も昔似たような事を考えていました。
http://d.hatena.ne.jp/righ1113/touch/20120424/1335240503#1335240503
でも後が続かないのですよね……

同じ事を考えた方がいたのは嬉しいです。

**１３２人目の素数さん** · 2018/06/10(日) 16:52:17.37

>>230
> 同じ事を考えた方がいたのは嬉しいです。
つーか、似たようなことを考えてる輩（やから）が
このスレに集まってるんだろうがよ（笑）。

**218** · 2018/06/11(月) 07:22:40.87

>222

>220を初項の小さい順に並べ直してみると、
1.9.17.25.33.41…a
3.7.11.15.19.23…b
5.37.69.101.133.165…c
13.29.45.61.77.93…d
21.149.277.405.533.661…e
53.117.181.245.309.373…f

a___a___a___a___a___a___a___a___a
_b_b_b_b_b_b_b_b_b_b_b_b_b_b_b_b_
__c_______________c______________
______d_______d_______d_______d__
__________e______________________
__________________________f______

と、フラクタル的な配置が出現しているように思います。
言い換えれば、全ての奇数がこの配置のどこかに格納される事が証明できれば、「とんでもなく大きな数で例外が現れる」可能性を除去できるのではないかと考えたんですが、いかがでしょうか？

あとは、この数列が例外なくコラッツ操作後1に繋がる(1.5.21.85.341.1365…)の数列に帰結する事が証明できれば、コラッツ予想を証明したと言えるのではないかと。
(「そんなんできねーよw」と自分では思ってたんですが、>221が糸口になりそう？)

頓珍漢な事を言ってたら申し訳ないです。

**１３２人目の素数さん** · 2018/06/11(月) 08:14:51.55

>>232
いや、発想としては順当だろうと思う。>>205 も発想としては同じだろう。
下向きの三角形というのは、一次元セルオートマトンではしょっちゅう
出てくるパターンだし、タガヤサンミナシ（イモガイの一種）の模様にも
あるような普遍的なパターンなので、シェルピンスキーの三角形みたいに
大きな三角形が「ずどん」と出るケースをうまく避けられれば
証明に結びつくと思う。
…… つーか、そのネタはウラムも思いついていて、ノイマンあたりと一緒に
追いかけてたかもしれない。それでコラッツ→ウラム→ノイマン→角谷と
伝わって、ここでこうして議論されているという話はありうる。

**１３２人目の素数さん** · 2018/06/11(月) 08:16:22.58

×シェルピンスキーの三角形
〇シェルピンスキーのギャスケット

**１３２人目の素数さん** · 2018/06/11(月) 08:42:28.48

あと、厳密な（解析的な）解決には結びつきそうもないが、
セルオートマトン → チューリング → 二重勾配 → 形態形成
→ フィボナッチ螺旋 → 互除法 → 連分数みたいなルートは
なんとなく臭い、と思う。「二重勾配」あたりに位置するのが、
「ビットシフト」と「算術演算」（2n + n + 1 ＝ 3n + 1）
であり（こっちが速い過程）、結果的に起きるキャリー（繰上り）の
連鎖とビットパターンの分布の相互作用（こっちが遅い過程）
ではないかと。そのあたりが話をややこしくしているように思う。

**１３２人目の素数さん** · 2018/06/12(火) 07:21:50.27

オートマトンといえば昔考えた、
×3+1を計算する有限オートマトン

文字: 0,1,空白
先頭が下位の2進数、後は空白のテープを考える

状態: 0(×3+0), 1(×3+1, 初期状態), 2(×3+2), 3(停止).
遷移表:(移動は常に右)
遷移|0　|1　|空
s0|0/s0|1/s1|空/s3|
s1|1/s0|0/s2|1/s3|
s2|0/s1|1/s2|0/s1|

例:7×3+1=22
s1: [1]11空空空
s2: 0[1]1空空空
s2: 01[1]空空空
s2: 011[空]空空
s1: 0110[空]空
s3: 01101[空]

停止せずに折り返して先頭の0を空白に置き換えるように改造すればコラッツ問題を再現するけど、停止しなくなる

1…10と0…01が状態s1を保つので、これでうまく分類できないかなぁ、まで考えた

**１３２人目の素数さん** · 2018/06/12(火) 13:08:59.15

>>236
> まで考えた
Java の開発環境があるなら、前にも「それなりに頑張ってるんだけど」
的な話をしたので、 Java のソース貼るけど？
ただ、ム板（プログラム技術板）でも「ソース貼られると
読んでて邪魔だ」と言われて嫌われて、
「どっかいけ」みたいな感じで追い出されたのだが。
『★★ Java の宿題ここで答えます Part 74 ★★』とかに
“出題”してくれれば、名目が立つんだが。

**１３２人目の素数さん** · 2018/06/12(火) 19:25:58.43

>>1みたいにgithub使えばよろし
まあ、無理にとは言わんが

**１３２人目の素数さん** · 2018/06/12(火) 21:30:52.62

>>238
> github使えばよろし
> まあ、無理にとは言わんが
WikiPedia によれば、GitHub は
> 2018年にマイクロソフトによる買収が発表されている
そうだ。
ゲイツが死んで三十年くらい経ったら考えてみてもいい。

**１３２人目の素数さん** · 2018/06/12(火) 21:33:17.05

もしかして言語がJavaなのもアンチゲイツのせいなのか？ｗ

**１３２人目の素数さん** · 2018/06/13(水) 09:31:54.51

>>240
Eclipse を使ってるのもアンチゲイツのせいだw
Eclipse の原型は OS/2 で動いてた VisualAge C/C++ なんだぜ。

**１３２人目の素数さん** · 2018/06/13(水) 19:07:29.31

ところで、このスレはコンピュータ使いが多いと思うんだが、

・計算器で限界に挑戦するなら C 言語
・プログラマが本業だったら、仕事にも使える Java
・研究とかも含めて、ロジックとかそっちの方にも視野を
向けてるんだったら Lisp 系
・教育のほうに向いているんなら N-BASIC とか Mathematica とか

みたいな言語ごとの棲み分けみたいなのがありそうに思うんだが、
お前ら何（＝どんな言語）使ってる？

**１３２人目の素数さん** · 2018/06/13(水) 20:27:07.06

そういやコラッツてプッシュダウンオートマトンとかで実装できるの？

**１３２人目の素数さん** · 2018/06/13(水) 21:21:20.83

>>243
なんかしら Wolfram がチューリングマシンをどうこうして、
どっかの学生が証明したのなんだの、という話が
二三日前の新聞にあったような。

　　　　　　　　　　　　　　　　　　　ggrks 、とセルフつっこみ。

**righ1113** ◆OPKWA8uhcY · 2018/06/13(水) 21:27:55.75

>>243
チューリングマシンなら、あるんだがなあ。
https://m.youtube.com/watch?v=t9nbkS-5bv8#

**１３２人目の素数さん** · 2018/06/13(水) 21:33:44.48

そりゃチューリングマシンはあるだろうさ