コラッツ予想がとけたらいいな その2
■ このスレッドは過去ログ倉庫に格納されています
漏れは航空宇宙工学科出身なので 「可視化」っつーのは重要だとは思ってるんだけど、 カオス系のように「見えたからって、なんも解決せん」とか、 f^-1 ゆらぎのように「実際に計測してみたら、単なる 対数分布だった」(ラーメンの汁に浮いてる油滴なんかがそう)とか、 ハズレが多いのは分かってるんだが …… なんかしら別視点に期待する部分は あると思われ。 >>92 >>86 は B の段階で全て Nothing になったのだと勘違いしていました ちゃんと見てみます。 ああすみません。 >>78 の書き方が悪かったです。 可視化はいいけどどうやって可視化するかはアイディアあんのか? 3次元表示だけじゃ具体性に乏しい。 >>92 とりあえずこの出力結果は間違ってなさそうです。 詳細は後ほど。 出力結果が正しいことの説明もしたいところですが、その前に別の話を。 まず一応誤解のないように言っておきますが、 この結果から即座に「コラッツ予想の 19n+1 版は成り立たない」とは結論づけられません。 ここで「コラッツ予想の 19n+1 版」とはそもそもなんなのかを考えなければなりませんが、 ここでは 「木を同様に定義したとき、自然数全体の集合が一つの木となる」 というものだとします。 (先行研究は特に知りません。情報があれば教えてください。) 今回の結果の意義について述べるために、改めてコラッツ操作についてまとめます。 一般化して、奇数 k を固定して「奇数は k 倍して 1 を加える」というルールだとします。 操作1:奇数に k をかけて 1 を加える。 操作2:偶数を 2 で割る。 操作3:mod k で 1 であるような偶数から 1 を引いて k で割る。 操作4:数に 2 をかける。 操作1,2 を「コラッツ操作」、操作3,4 を「コラッツ逆操作」と呼ぶことにします。 どんな数から始めても、操作1〜4の繰り返しで目的の数にたどり着けるか、というのが(一般化された)コラッツ予想。 この「目的の数」を mod n で考えたものが私の予想です。 で、お気づきかもしれませんが、現在のアルゴリズムはコラッツ逆操作しか考えていません。 これが「コラッツ予想の 19n+1 版は成り立たない」とは結論づけらない理由です。 (コラッツ逆操作しか考えていない理由は、これだけでもさしあたってうまくいっていたことと、コラッツ操作まで考えると一気に複雑さが増すことということです) (逆操作だけというのはかなり制限しているように見えますが、実はそれほどでもありません。また今度話します。) 今回の結果についてですが、 まず出力結果にある C' は「mod 133(=7*19) で 2 のべきである数の集合」になります。(これもまた今度) このことから今回の結果を次のように述べることができます。 定理 コラッツ予想の 19n+1 版を考える。 このとき、mod 133 で 2 のべきである数からコラッツ逆操作を繰り返しても、 mod 133 で 2 のべきである数以外は得られない。 これはちょっと予想外でした。 3n+1 では今までコラッツ逆操作だけでうまくいってたけど、 そのうちコラッツ操作も考えなきゃいけなくなるかもしれない… >>96 n が 127 以下については、手で描いてみた(A4 の 5mm 方眼紙四枚とか)。 以前誰かが書いてたように、「場合分けが面倒臭いことに なって手に負えなくなる」という感じのある錯綜したケース (確かに127 以下はけっこうややこしい)を脱して ある程度規則性が見えてくるのは、ここより先 (255 とか 1023 とか 2047 とか)らしいんだよね。 そうすると、もう手描きだと追いつかなくなるのと、関係が錯綜して 見づらくなる(つーか、局所的な関係はわかるんだが、全体像が 把握できなくなる)ので、「2で割る」「3n + 1 して 2 で割る」 「その数の大きさ」みたいに次元を分けて空間的に散らばらせて、 ぐるっと見渡せれば何かわかるかな、と。 乱数の品質とかも、二次元空間にマッピングすると「あ、この アルゴリズムだと、品質悪いな」とか判ったりするじゃん? あんな感じ。 >>100-101 う〜む、そんなに単純ではないのですね。 ちなみに、 コラッツ予想の19n+1版において 7で割って ・0,1,2,4余る数→全ての木に現れる ・3,5,6余る数→一部の木にしか現れない これは言えるのでしょうか? >>103 それが言えちゃうとまさに「コラッツ予想の 19n+1 版は成り立たない」になっちゃいます。 ・0,1,2,4余る数→全ての木に現れる これはプログラムによって証明できていますが、 ・3,5,6余る数→一部の木にしか現れない こっちは証明できていません。 しかし実際問題として19n+1版の反例というのはそんなに簡単には見つからないものなんですか? >>106 bn+1版でbが大きくなると、遷移の上昇幅も大きくなるから、無限大に発散する可能性は高くなると思います。 適当にプログラムを走らせて、どんどん大きくなっていくようなら、この初期値は無限大に発散する可能性が高い、とは言えると思います。 「無限大に発散する!」という証明はかなり難しいと思います。 >>106 どうでしょうね…あまり考えたことはないので、難易度も分かりません。 「コラッツ逆操作だけ」というのがそれほど強い制限でないという話。 まず、コラッツ逆操作では操作 3 を行うか操作 4 を行うかで分岐が起こりますが、 コラッツ操作では分岐は起きません。 なので、例えばある数にコラッツ逆操作を行ってからコラッツ操作を行うと、元の数に戻ることになります。 予想を証明するには、 「ある数 a からコラッツ操作、コラッツ逆操作を繰り返してある数 b にたどり着けるか」 を考える必要がありますが、上記のことから 「ある数 a から何度かコラッツ操作を行い、その後何度かコラッツ逆操作を行うことである数 b にたどり着けるか」 という道筋だけ考えればいいということになります。 そうすると、コラッツ逆操作だけを考えるというのは大体、操作の後半だけを考えるということになります。 これが強い制限と思うかどうかは人それぞれですが、 実際にこれまでは多くの場合にうまくいっているので、大した制限じゃないのだろうと私は思っています。 ちなみにこれまで「コラッツ操作」の方を全く考えていない訳ではなく、 前スレ>>787 の 命題 T を木とし、k=1 or 2 とする。 このとき、ある a∈T が存在して a≡k (mod 3) となる。 や、前スレ>>851 の 補題 n を 5 以上の奇数とする。 任意の木には、3 の倍数でも n の倍数でもない数が含まれる。 (元々は奇数でなく素数としていたが、全く同じ証明で奇数の場合も示せる) ではコラッツ操作を用いています。 通常のコラッツ予想3x+1ですが、 @プログラムが無限走行→オールNothing出る (Cを繰り返すと集合が1つになる事が使えないか) AオールNothing出ない→プログラムは停止 B全てのnでオールNothing出ない(難しい?) C全てのnでプログラムは停止する というのを考えたのですが、 実際証明するとなると難しいですかね。 また邪魔なプログラマが通りますよ コラッツ逆問題(3n+1版。「1 から出発して、すべての自然数に 到達できるか」)について、「(有限な)すべての偶数は、2で割り続ける ことによって奇数に帰着するので、奇数についてだけ証明できれば足りる」 のは確か。 逆コラッツ操作は、 1)nを2倍する。 2)nを二倍して1を引いたものが3で割りきれるなら、それ(2n−1)を 3で割る。 が可能。 で、このとき、「nが3で割りきれる場合は、(1)の操作によって 『nを二倍して1を引いたものが3で割りきれる数』が出てこない」ことが 判っていて、nの偶奇によらず(1)の操作の結果は偶数になるので、けっきょく 奇数は出てこないことがわかる。 (2)に対応する正のコラッツ操作は、結果的に「nを二倍して1を引いたものが 3で割りきれない数」に「2n+1」操作を繰り返して「6で割って2余る偶数」に 至る“縦のルート”(有限長の上下のルート)を描くことであり、このとき(nの 偶奇によらず)3の倍数が出てきたときは逆コラッツ操作の (1)(“右へ向かうルート”。こちらは際限なく右に延長できる)は 考慮しなくていい。 なお、“縦のルート”は、最下位ビットが「2個以上の連続するオンビット」である 状態と関連している。 この制約条件のもとで、「1を出発点として、すべての奇数に到達できるか?」が、 コラッツの逆問題となる。 で、「最下位のオンビットが連続しない」数は、「4で割って1余るn」であり、 それが正のコラッツ操作(2)によって「6で割って2になる数」に変換されるはず だから、それを満たす数について考えればいい ―― ような気がする。 だけど、コラッツ予想に関する議論で「mod 12」って話が出てきたのを 見た記憶がオレにはないんだよな (-_-!)。 これって、オレが なにか盛大な勘違いをしているってぇコトなのか? >>112 >「nを二倍して1を引いたものが3で割りきれない数」に「2n+1」操作を繰り返して「6で割って2余る偶数」に至る“縦のルート” ここが分かりません。 具体的な一連の数とかありますか? >>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 詳細は のちほど。 つーか、「コラッツ操作」ということを考えたら、 「->」じゃなくて「<-」のほうが判りやすかったかも。 あ、「3n + 1」じゃなくて、「(3n + 1) / 2」で 表示してるのは、このスレを見てるような人だったら 察してくれるよね? 言うまでもないけど、 “☆”がついている値は、 「3の倍数なので、2 の冪乗を掛けても 『2n - 1 が 3 で割りきれる数にならんので、 下に延びる枝(3n + 1 操作の逆操作)がない枝』」 っちゅーことです。 >>114-116 >>112 は大体理解できました。mod12は分かりません。 > で、「最下位のオンビットが連続しない」数は、「4で割って1余るn」であり、 >それが正のコラッツ操作(2)によって「6で割って2になる数」に変換されるはず >だから、それを満たす数について考えればいい >―― ような気がする。 例えば17を見ると、4で割って1余る。 コラッツ操作(2)で26になって、6で割って2余る。 しかし17を2倍して1引いた数が3で割りきれてしまう。 コラッツ操作(2)に違反していると思うのだけど、こういう数はどう処理するの? >>113 ごめん。 >(2)に対応する正のコラッツ操作は、結果的に「nを二倍して1を引いたものが 3で割りきれない数」に「2n+1」操作を繰り返して「6で割って2余る偶数」に 至る“縦のルート”(有限長の上下のルート)を描くことであり、 っつーのは、 >(2)に対応する正のコラッツ操作は、結果的に「nを二倍して1を引いたものが 3で割りきれない数」に「(3n+1)/ 2」という操作(←ここ重要)を繰り返して「6で割って2余る偶数」に 至る“縦のルート”(有限長の上下のルート)を描くことであり、 という意味だ。 とりあえずツッコミは歓迎なのだが、いまは遠山 啓先生の『初等整数論』で 理論武装中なので、殲滅的攻撃は勘弁してくれいm(_ _)m。 >>118 すみません、つい熱くなってしまって…… >>117 > 例えば17を見ると、4で割って1余る。 > コラッツ操作(2)で26になって、6で割って2余る。 > しかし17を2倍して1引いた数が3で割りきれてしまう。 > コラッツ操作(2)に違反していると思うのだけど、こういう数はどう処理するの? 典型的な例を挙げたので分かりにくかったと思うが、 (26 ->)17 -> 11 -> 7 というのは確かにあって、 「必ず 3 の倍数で終わる」とかいう話ではないのだ。 つーか、「どのあたりで齟齬が生じているか」について、 数学屋さんと電算屋の間では分かりにくいのだ。 「素数には必ず原始根がある」というのは納得するにせよ、 「原始根って複数あるんじゃないの? そのあたりはどうなの」とか、 「そもそも『指数』という概念がよくわからん」とか、 「QRコードとか乱数生成とか、リクツは判らんでもないけど、 原始多項式うんぬんとか言われても、正直な話、小分かりがせんのよ」 みたいな感想がある。 そもそも「Z/pZ」っつーのが、「演算を定義せんと意味がねぇ」みたいな 話があって、よくわからん(加法なのか乗法なのかとか)。 せっかく大勢の人が見てくれているのだから、「数学的に厳密な記述」 ではない「わかりやすい説明」(まぁ、「『分かりやすい説明』は、 嘘の温床だ」という意見は確かにあるのだが)っつーのも 試みてくれんか。このスレで(見ているだけの奴もいるし、 書いている奴もいるわけだが)“解っている” 人間も 少なかろうと思うので。 >> 119 > すみません、つい熱くなってしまって…… いや、熱くなるのはまったく問題ないので、「こちらこそ、数学の門外漢が 半煮えの議論を持ち出してすまん m(_ _)m」とお詫びしたい。 とはいえ、実験数学が未解決問題の解決に貢献することもあるし、 「素人目線からの、視覚化だのなんだの」が有効なことが あるのだ。 数学屋さんには数式という武器があり、 電算屋にはプログラミング言語という武器がある。 (個人的に Wolfram は気に入らないが)Mathematica みたいに その間を繋ぐツールもある。 とりあえず「共通の土俵」っつーのを用意したいと思う。 >>122 > 具体的にプログラム言語は何使えんのよ? わしゃぁのう、年寄りじゃけん、本当はアセンブラしか解らんのじゃ。 じゃけんども、C とか LISP とかは、理屈がよう分るんじゃ。 Pascal は、P-system があったんで、Java んような「中間言語」とか 「仮想マシン」っちゅーたらコンセプトは分らんでもないんじゃ。 年取ったけん、IDE がなけりゃプログラムなんぞ書けんように なってしもうた。 そんなわけで、ようやく Java を使ってなんとかプログラムを 書いとるんじゃ。 ごめんつかぁさい。 中身のある話振ってくれるなら歓迎するけどね。 アイディアがあるなら具体的に頼む。 >>125 > アイディアがあるなら具体的に頼む。 ありがとう。 生煮えなので申し訳ないのだが、右(2の冪乗)から来る 値は、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。 逆にxn+1問題で無限大に発散する場合もあるxを探すというのは? コラッツ予想をセルオートマトンで可視化する事を試してみました。 ttps://dotup.org/uploda/dotup.org1543060.zip.html キーは3nplus1です。 大まかに4つのパターンを図示してみました。 1)完全にランダムなパターン 2)1のビットが長く続くパターン(2^n-1) 3)最下位ビットと最上位ビットの間が0のビットで隔てられてるパターン(2^n+1) 4)1のビットが長く続き、さらに離れて最上位ビットが存在するパターン((2^n+1)*2^m-1) 最下位ビットが0の行は赤に塗ってあります。 プログラムに間違いがあればすいませんが、結構興味深い遷移がみられました。 >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)となる。 とりあえず挙げられるのはこんなところでしょうか。 既知の情報でしたら申し訳ない。 整数をビット列とみなして考えるのは>>1 がかなりやってたから>>1 の意見を聞きたいね。 まあ、この程度の成果では驚きはないだろうけど。 結構きれいな絵だけどきれいなものだけ抜き出したの? よくわからんが全部きれいになるならもしかして凄いのかな? >131 綺麗なパターンが出る値を選んでます。 大抵は増えて減ってを繰り返すパターンになると思いますが、その出現に規則性が見られるように思えます。 まぁ勘違いかもしれないんですが orz >>129 「最下位ビットから2ビット以上1が連続した場合」については、 以下のようなことを考えたことがある。 「ここで、新たな操作を追加する。 (3)n' = 3n + 2 である。 たとえば "11101" のように、左に '1' が二個以上連続した部分(m 個)が あるとする。これを、m - 1 個の '1' と '1' に分ける。 "11101" だったら "11" と "101" だ。このとき、"11101" は、"**"と「 "101" に(3)の操作を 二回施した結果」で表される。 "11" -> "*" + "101" "111" -> "**" + "10001" "1101" -> "*" + "10001" "1111" -> "***" + "101011" "11001" -> "*" + "10111"」 その他の悪戦苦闘っぷりは http://animaleconomicus.blog106.fc2.com/blog-category-33.html を参照されたい。 逆コラッツ操作を行なうプログラムの中で、ずっと 「nを二倍して1を引いたものが3で割りきれたら3で割る」 とかいうロジックを使っていたのだが、よく考えたら 「nを3で割って2余る」(n ≡ 2(mod 3))でよかったことに、 いま気づいた。 2*(m + 2) - 1 = 2m + 4 - 1 = 2m + 3 なんだから、3|m(「m が 3 で割切れる」あるいは「m は 3 の倍数」。 遠山 啓さんの『初等整数論』のスタイルだと「3)m」)なら 当たりまえじゃん(だから数学は苦手なんだと(ry)。 そうすると、 1)nを3で割って2余るなら、二倍して1を引いてから2で割る。(それが終わったら、次にnを二倍して右を探す) 2)nを3で割って1余るなら、右に逃げる(nを二倍して右を探す)。 3)nが3で割りきれるなら、下には行けないし右側にも奇数へ向かう枝が出ないので、ひとつ前(根に近い数)に戻る。 という操作で再帰をかければ、「逆コラッツ操作で出てくる奇数の木を探索する」ことができるはずだ。 こうなったら奇数偶数関係ねぇじゃん。orz 個人的最近色々とデータをいじっているんだが、1になるまでの回数にちょっとした発見があるんだけど需要ある?? あとは逆コラッツとフィボナッチの関連性やn次のコラッツ、コラッツに群の導入などなど >>128-129 残念だけど目新しい情報はないかなあ。 >>135 > 個人的最近色々とデータをいじっているんだが、1になるまでの回数に > ちょっとした発見があるんだけど需要ある?? >>136 > あとは逆コラッツとフィボナッチの関連性や、n 次のコラッツ、コラッツに群の > 導入などなど ここは、たぶん「『需要ある??』とか、つまんねぇ遠慮なんかしてるんじゃねぇ! さっさと晒せよ!」 …… っつースレですから。燃料を投下していただければ、いくらでも。 スレがにぎわい始めましたね。 あとは>>786 の議論についていけるレベルの人が来てくれればいい感じなのですが。 >> 139 > あとは(前スレの)>>786の議論についていけるレベルの人が来てくれればいい感じなのですが。 つーても、数学板は敷居が高いのよ。 前スレの >>8 の > 最初に偶数はアウト(1に収束) > 4の倍数になったらアウト っつーのも、 ×「最初に偶数はアウト」 〇「最初に2の冪乗数はアウト」(つーか、2で割り続ければ奇数に帰着するので、 奇数について証明できればオッケー。てなワケで「4の倍数になったらアウト」と いうのも、ここに帰着) とかいったツッコミ(つーか、解説)を誰かしてくれよ、みたいな話にはなる。 むしろ、素人目線の解説を丁寧に してくれるヒトがいてくれると、もっと盛り上がる ような気がするのだが。 なんだか盛り上がってますが とりあえず>>92 の出力が正しいことの説明がやっと書けそうなので、投下してから見ます。 頭の中では図と数式だけしかないから大したことない議論に思えるけど ちゃんと書こうとするとどうも長くなってしまう… >>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 倍を表しています。 ここから>>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 よって、緑グループのみ得られます。 次の 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 の通りになります。 >>129 と >>132 から、なんとなく証明への道筋らしきものが見えてきた。 もちろん“道筋らしきもの”なので、完璧な証明に到達できるかどうかは別の話なのだが。 まず、ごく初歩的な話だが、「メルセンヌ数」の話をしておく。「メルセンヌ数」を「メルセンンヌ素数」だと思っているような人は 数学板にはいないだろうが、「素数であるメルセンヌ数」が「メルセンヌ素数」で あって、メルセンヌ数は単なる「2^n - 1」の形をした数である。 メルセンヌ数が素数であるかどうかは「リュカ検定(ルーカス・テスト)」に よって比較的効率よく行えるので、「メルセンヌ素数は無限に存在するか?」 「(偶数の)完全数は無限に」という問題と関連して、コンピュータによる 探索が行なわれている。そうやって見つかった素数は桁数が大きいので 「現在知られている最大の素数」みたいな形で話題になる。 つぎに、任意の有限な数 n をビット列で表したときの、最初のオンビットから 最後のオンビットまでの部分を、“コラッツむし”と呼ぶ。 4で割って1余る(n ≡ 1(mod 3))コラッツむし以外のコラッツむしは、 下位に「2個以上連続したオンビット部分」を持っている。ここで、m 個並んだ オンビットがあるとして、そのうちの下位側の m - 1 個のビットを 「メルセンヌ部分」、残りを「本体」とする。このとき、本体部分に m - 1 回の 「3n + 2」操作を行なったものが、コラッツむしの“真の体長”だと 思うことにしよう。 つまり、n が メルセンヌ部分を持っているときは、メルセンヌむしは “縮んでいる”わけだ。 3n + 1 操作を受けた“伸びた”コラッツむしの下位側には、0(二進数表記。 オフビット)が現れる。ただし、任意個の 0 は“ないのと一緒”なので、 コラッツむしの体長には含まれない。 そこで、「コラッツ予想が正しいかどうか?」は、「コラッツむしの“真の体長”が 際限なく伸びてゆく場合があるか?」という問題に帰着する。 そうなると、本体部分は「4で割って1余る素数」だ。これに 3n + 1 操作を 行なったときに、メルセンヌ部分がどう表れるかという話になる。この メルセンヌ部分が際限なく表れると、コラッツむしの真の体長が伸びて、 メルセンヌ予想が破綻する。 じゃあ、「『メルセンヌ部分を持たないコラッツむし』が『メルセンヌ部分を 持つコラッツむし』に変態する頻度と、変態後の“真の体長”の変化は、 どのようなものか?」という話になる。 “真の体長”が伸びる可能性があるとすれば、それは操作 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・2・1・2 と 変わる。 つまるところ、「真の体長を伸ばすようなメルセンヌ部分が、どれだけ 出てくるか?」という話になる。 「山よりでかい猪は出ない」わけで、真の体長よりも“長い”メルセンヌ部分が 出ることはない。これを踏まえて、「コラッツむしの真の体長が無限に伸びる ことがあるのか?」という話になる。このあたりが mod 3 と mod 4 の 絡み合いで組合せによって解決できて、「伸びるにしても限度がある」ことが 示されれば、メルセンヌ予想は肯定的に解かれたことになる。 こう考えると わりと単純な話なので、数学の素人でも手を出しやすいような気が する。もっとも、コラッツ問題自体が「素人にも手をだしやすいが、素人の手には 負えない」問題なんだから、解けるかどうかはまた別の問題なのだが。 一応、まとめてみる。 自然数 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 に『三倍して2を足す』操作を p 回繰り返した結果に コラッツ操作を施すことで、どれほどの桁数(これを n とする)になり、 最下位に何桁(これを m とする)のメルセンヌ数が出てくるか?」を 考える(m < n であることに注意)。 m と n を p と q の関数で表して、 n - m が q - 1 よりもどんどん大きく なっていったら、コラッツ予想は「はずれ」だということになる。 おそらく、最悪のケースで見積もると、“爆発”(無限大に発散)すると思う。 そうでなかったら、コラッツ問題はとっくに解決しているはずだ。 だから、相当に ややこしいテクニックを駆使して「最悪のケース」を避けて 「無限大には発散しない」ことが示せれば、コラッツ予想は肯定的に証明される ことになる。 そんなにうまくゆくとも思えないし、可能だとしても相当に苦労するだろうとは 思うのだが、方向性としては ちょっと新しいように思うので、「難しい」とか 「ダメっぽい」とか「ここから先で行き詰まった」くらいの実績は残しておいても いいと思う。 コラッツ予想に関する「やってみたけどダメだった」的な論文というのは 山ほどあるのだから、いまさら何本かのクズ論文が増えたところで 文句を言う奴もおるまい。 >137 既知の情報だったようですね。失礼いたしました >146 何かしらのお役に立てたのなら幸いです。 >>150 >>128 > 既知の情報だったようですね。失礼いたしました いやいや、2ちゃん(今は「5ちゃん」だが)でガイシュツは恥ではない。 お気にならさず。 > 何かしらのお役に立てたのなら幸いです。 本当に役に立った。ありがとう m(_ _)m ついでながら、>>149 の > 2^q - 3 は、2 < q のときに、二進数で q - 1 桁になる。 というのは、「5以上の4で割って1余る奇数」のうち、いちばん みっしりビットが詰まったやつのことである。 このあたりのコンセプトの整理には、本スレに参加している諸氏の意見が 非常に役立った。併せて感謝申し上げる。ありがとうm(_ _)m ようやく前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」に関してツブしてゆこう、という話ではないかと思う。 オレは何かヘンなことを言っていると思ったら、ツッコミを入れてほしい。歓迎する。 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} に分ける、というような操作に関しての発言だと思いますが、 これを表現したければ「軌道」と言うのが適切かと思います(群論の言葉です)。 2 に注目していることについては、 例えば次のような問題を考えれば納得できると思います。 問. どんな自然数からでも、コラッツ操作とコラッツ逆操作を繰り返すことで 9 の倍数に到達できるか? スレの流れからいうと不規則発言なので、「そういうコトを言っている香具師がいる」 くらいに思ってほしい。 なんとなく問題の本質が見えてきたような気がするので、「コラッツ予想」 「コラッツ問題」に関して「他の研究者は、どんなアプローチを取っているんだろうか?」と 思って検索してみた。 そうすると、「3n + 1 問題」の 3 を「一般の k に拡張したときに」とかいう話が 多いんだよね。 「逃げちゃダメだ、逃げちゃダメだ、逃げちゃダメだ」と思う。そんなもん、 「3n + 1」を解決してから考えろ、と思う。 mod k からアプローチするのは、基本的に“あり”だと思う。だけど整数論 (群とか環とか体とか)に関していうと、あんまり道具としては使いやすくないので 、「果たして有効だろうか?」と思う。まぁ、数学の素人が言う こったから、 「ふぅーん、あんたはそう思うのね?」くらいの感じで聞き流してくれても まったく問題がないのだが。 だいたい、「数学」っつーのは“無限”を相手にすることが多い。「実用的な範囲で、 どれくらい抑え込めるのか?」っつーのは、どっちかっていうと有限組合せ数学とか の範囲の仕事なのだ。だから、純粋数学畑の人はあんまり興味を持たないと思うし、 数式処理システムとか実験数学とかいったものとかとは距離を置きたいと思うのが 当然だと思う。 あとは「整数論方面のほうからのアプローチが どこまで通じるか」という期待が あるのだが、そっち方面の研究って、あんまり進んでないような気がする。 「有限束の数え上げ」とか「魔円陣(完全ゴロム環)」とかいった話題は、 もう十年以上も取りあげられていないような気がする。 てなワケで、燃料を投下してみた。敲いてくださって結構。かかってらっしゃい。 数学はまるでダメだが、伊達に長年ネットで のたくっていたワケでもないので、 口だけは達者だ。 >>153 おお、数学屋さんがマトモに応答してくれるとは光栄だ。これは皮肉ではない。 本当にそう思っている。 > 2 に注目しているのは、 > コラッツ操作の「偶数を 2 で割る」 > 逆操作の「2 をかける」 > から来ています。 私はビット列として考えているので、“コラッツむし”みたいな概念で「シフト演算」 あるいは「ヌルビットの除去」というイメージで捉えているのだ。このあたり、 プログラマという商売柄がある。そんなわけで、「だったら、コテハン(固定ハンドル)を 使って立場を明確にしろ」ということであれば、対応するつもりだ。 >>153 つづき >>「Z/pZ」(つーか、どうせ自然数なんだから「N/pN」で構わんと思うんだが、 >> それは「整数論」という括りでいうと「自然数に 0 が入っちゃまずいだろう」という >> 配慮があるんだろうと思う)というのは、単なる剰余系であって、 >> 「何に関して閉じているか」っつーのは、また別の話なんだよな? > ここで何を気にされてるのかいまいちよく分かりませんが、 > 「閉じている」という表現は全体の一部分を見ているときに使う表現なので、 > この場合適切でないと思います。 > > 例. 整数全体の中の奇数の集合は、積について閉じていて和について閉じていない。 > > 「どういう演算を考えているか」を気にしているということでしょうか? 「群論」というと、整数論をちょっと齧った人間としては、まず「循環群」 (その集合の要素をすべて網羅すること)を連想してしまうのだよ。 だから、「2 をかける」という操作よりも、「3n + 1 という操作に関して、 その有限集合が閉じているか?」が気になってしまうのだ。そういう意味では、 「どういう演算を考えているか」が気になる。 >>153 さらにつづき > あと一応もう一つ言葉にツッコんでおきますと、 >> だけど、Z/pZ に対して、任意の i かなんかを持ってくると、Z/nZ(×i)というのは、 >> 「全部廻れる」わけじゃないので、Z/pZ の部分群の和集合という形に >> なるんだよな? > この「部分群」もちょっと用法がおかしいです。 > 例えば Z/7Z を {0},{1,2,4},{3,5,6} に分ける、というような操作に関しての > 発言だと思いますが、 > これを表現したければ「軌道」と言うのが適切かと思います(群論の言葉です)。 済まぬ m(_ _)m。「軌道」という言葉は別のサイトで使っちゃってたので、 あえて避けた部分がある。 「軌道」によって排他的(重なる要素がない)集合に分割される「群」の 部分集合、という意味で「部分群」という言葉を使っただけだ。 コラッツ集合を表す「木」という言葉も、「根本のほうで循環してるんだから、 『木』っておかしくねぇか?」みたいな議論は前スレでもあったと思うが、 「ビット列の中で、最初のオンビットから最後のオンビットまでを “コラッツむし”と命名する」みたいなコンセプトで、「根っこが 1 ビットである 木構造」と捉えると、「木」と呼んでも しっくりくると思うのだが。 >>154 > 問)どんな自然数からでも、コラッツ操作とコラッツ逆操作を繰り返すことで > 9 の倍数に到達できるか? なんとなく意味は分かるのだが、どういう問題意識があるのかがピンとこない。 mod p の木に奇数 m があり、mod q の木に奇数 q があったとすると、(p と q が 互いに素だとして)Z/pqZ 上では「根である 1 まで下がって、また上がってくりゃ いいだけの話じゃん?」と思う。 「p と q の直近の(いちばん近い)共通の奇数 x があり、それぞれコラッツ操作に よって x -> p と x -> q に至るルートを(効率よく)求める方法を(コラッツ操作と コラッツ逆操作を それぞれ用いることで)示せ」っつーんなら、「ひょっとしたら、 なんとかなるかも知れん(オレが出来るとは言わんが)」くらいのことは言えるが。 >>159 私が考えているのは 「コラッツ予想は、初期値が n で割って k 余る数だけ考えれば十分である」 というのがどんな n, k についても成り立つか、という問題です。 それを証明するための一つの手段として、 「どんな自然数からでも、コラッツ操作とコラッツ逆操作を繰り返すことで n で割って k 余る数に到達できる」 を示そうと思っています。 ところで「mod p の木」とか 「mod q の木」などと私は一度も言っていませんが、何の話でしょうか。 Z/pqZ 上では「根である 1 まで下がって、また上がってくりゃいいだけの話じゃん?」、というのも意味がよく分かりません。 >>160 要するに、 > 「コラッツ予想は、初期値が n で割って k 余る数だけ考えれば十分である」 > というのがどんな n, k についても成り立つか というのは、 「コラッツ予想は、x ≡ k(mod n) だけ考えれば十分であるというのが、 どんな n, k についても成り立つか?」っつーのと同じことを謂っているように 思うのだが、うちらは「そのあたりに関しては、mod 3 と mod 4 の絡み合いに 関係していそうなので、なんだかんだで場合分けがややこしいことになりそうだ」 という話をしているだけなのだ。 そこで、 > それを証明するための一つの手段として、 > 「どんな自然数からでも、コラッツ操作とコラッツ逆操作を繰り返すことで > n で割って k 余る数に到達できる」 > を示そうと思っています。 というのが、「コラッツ操作」と「コラッツ逆操作」を混在させてしまうと、 なんとなく迷走してしまいそうで、心配しているだけだ。 その発想だと、「共通の“節点”であるどこか」を経由しないと いかんような気が するので、「根であるところの 1 へのルートをそれぞれについて求めて、 その差分を取る」みたいなアプローチが成功しそうに思う。 あくまで個人的な感想なのだが。 >>160 > ところで「mod p の木」とか 「mod q の木」などと私は一度も言っていませんが、 > 何の話でしょうか。 原始根は複数個ありうるので、巡回群(剰余系における、全部の要素を辿る乗数系)も 複数個ありうるのだが、「一部の要素」をフォローする(単一の)乗数と、「その他の 要素」をフォローする乗数(その他大勢)が、全体として Z/pZ を隈なく覆う、 という「グループとしての、木の集まり」というものを考えて、「その集まりを 考えたときに、木の本数が、ある一定数よりも大きくならない」ということを 謂っているんだろうと思っているのだ。 それを考えると、「どこかの木に属している」ということは、「他の木に属していない」 という意味になりそうな気がするわけで、そうした「排他的な木」としての 「mod p の木」とか 「mod q の木」という概念はあっていいような気がするし、 それぞれの木が排他的に「すべての自然数」を所有しているとすると、 「グループとしての、木の集まり」がコラッツ問題をカバーしていることになり、 Z/(全部の木の基数の積)Z の存在を示すことができれば、コラッツ予想が肯定的に 証明できることになるような気がする。 >>161 mod 3 と mod 4 の絡み合いでややこしくなるとか、コラッツ操作とコラッツ逆操作を混在させて迷走しそうとか 心配はありがたいのですが、既に多数の n や k について証明できているのは見ていただけてるでしょうか。 「なんとなく」の印象だけで話されても困ります。 >>162 >「一部の要素」をフォローする(単一の)乗数 原始根にならない元のことでしょうか。よく分かりません。 数学の言葉でお願いします。 >「その他の要素」をフォローする乗数(その他大勢) ここはもっとよく分かりません。 >Z/pZ を隈なく覆う、という「グループとしての、木の集まり」 軌道のことでしょうか。 >「その集まりを考えたときに、木の本数が、ある一定数よりも大きくならない」ということを謂っている なんのことでしょうか。 >>142-145 説明ありがとうございます。完全に理解したとは言えないのですが…… このプログラムの実行には12時間以上かかったので、無駄にならなくて良かったです。 若干スレが荒れぎみですがこれも2chの華ですかね? >>164 よく粘りましたねw 逆に言えば、プログラムで数千、数万回計算して得られた結論がたった3レスで説明できた訳ですから、 この考え方をうまくプログラムに落としこめれば計算量を大幅に削減できる可能性も…… >>165 私の発言でそう思わせてしまったなら申し訳ありません。 「すべての自然数 N に対して、偶数は(素因数分解したときの 2 の乗数について 割ったら)奇数に帰着する。 「『4で割って3余る奇数』は、ビット列で表現したときに、下位のオンビット列 (一個以上のビット列が並んでいるビットパターン)」に帰着するので、 「4で割って3余る奇数」に帰着する。 そうすると、「4で割って1余る奇数」に帰着するすべての自然数が、3n + 1 操作に 対して、「4で割って1余る奇数」に帰着するかどうかが問題になるわけだから、 「ある『n ≡ 1(mod 4)の数が、(3n + 1)/2 操作によって、『n' ≡ 1(mod 4)の数』に なるとき、n' が単調増加して無限大に発散するかどうか?」という話に帰着する。 そんなわけで、そのとき、2 で割ったときに、「『2 < n| 2^n - 1』が無限連鎖するか?」という話になる。 自分は数学屋ではないので、数式を追っかけて解決する自信がない。 数値実験で見当をつけようと思う。 ロジックに穴があったら指摘していただきたい。m(_ _)m >>167 最後がよく分からないです。 > 2 で割ったときに、「『2 < n| 2^n - 1』が無限連鎖するか?」 詳しい説明が欲しいです。 例えば、ビット列で言うとこう、とか プログラム(アルゴリズム)で書くとこう、とか。 >>166 まあここまでが順調過ぎましたからね 今の方が本来の2chの姿に近いかも あまりガッカリせずに気長に行きましょう >>167 > 最後がよく分からないです。 >> 2 で割ったときに、「『2 < n| 2^n - 1』が無限連鎖するか?」 > 詳しい説明が欲しいです。 あ、ごめん。言葉が足りなかった。 最下位に「連続した2個以上のオンビットがある」というのが n ≡ 3(mod 4) ということなわけで、 その場合は「下位のメルセンヌ部分を除去したビット列に、 3n + 2 操作を行ないつづけることで、n ≡ 1(mod 4) に帰着する」 ということが謂える。 だから、「メルセンヌ部分を除いた本体が、増えるか減るか」が 肝心なところであって、「最下位に一個以上の 0 があって、本体の長さが 減る」のか、「最下位に二個以上の 1 が現れて、本体の長さが増える」のかが 問題になるわけだ。 その部分に着目すると、コラッツ操作の逆操作を考えたときに、かなり計算量が 減るように思うので、「コラッツ予想は 5 × 2^60 までは成り立つ」みたいな ショボい話(IEEE の long よりも小さい)ではなくて、メルセンヌ素数的な デカい数まで(たとえば 10^100 とかまで)コラッツ予想は成り立つことが、 “数値実験的に”ではなく、“数学的に”(といっても、コンピュータによる 実験的な検証が入っているので、数学的な厳密性に欠けているという点については 完璧ではないのだが)「コラッツ予想は成立する」と断言しちゃっていい、 みたいな話になると思うのだ。 少なくとも、「フツーにプログラムを動かしていたら、例外が見つかった」とか、 飛行機が堕ちて死ぬとか巨大彗星が堕ちてきて人類が滅亡するとか、そういった 確率の何百万分の1以下のところまで絞りこめれば、「実用的には、コラッツ問題は 解決した」(とはいえ、コラッツ問題の実用性というのが、あるとは思えないが)と 言っちゃっていいと思う。 暗号理論だって、「偶然、解読のための鍵が見つかっちゃう確率は 0 ではない」という 意味では完璧ではないわけで、「じゃあ、具体的には、コラッツ予想は、どこまでの 範囲で成り立つのか?」という限界を、「可能性がありそうな部分を、一個づつ ブルート・フォース・アプローチによって潰してゆく」より効率のよさそうな方法で ツブしてゆくというアプローチがありそうに思う。 で、その過程で、「なんか、こっから先には なんにもなさそうな気がする」という 限界が うっすらと見えてきたら、そこから逆に「じゃあ、このあたりには何があるの?」とかいった見当がつくのかもしれない、と思う。 コラッツ予想はメルセンヌ素数 8,191 に絡んで、2^8191 - 1 あたりで組合せ論的には 頭打ちになると思う。実際にメルセンヌ数から出発してメルセンヌ数に落ちるケースは 127 かなんかが最高だったので、あとは「メルセンヌ数ではない数から出発して、 3n + 1 操作“のみ”によってメルセンヌ数に落ちる」ケースを潰してゆけば、 コラッツ予想が成立する限界点は もっと先まで確認できるように思うし、 ひょっとしたら(四色問題や有限群の分類みたいに)「この先は、組合せ論的にいって ありえない」みたいなコトになるかもしれない(とはいえ、私は数学の専門家では ないので、数学者の誰かが証明できたとしても、その証明を理解できる自信は まったくないのだが(-_-!))。 てなワケで、現在探索を続行中。 >>171 探索を実行中ってことはもうプログラムがあるってこと? なんなら>>1 みたいに晒してくれてもいいのよ? >>168 ごちゃごちゃ長文を書いてしまって申し訳ない。m(_ _)m 要するに、「いままで、『n 以下までにはコラッツ予想の 反例はない』というのを示すのに O(n) の手間がかかって いたのだが、それを O(lon(n)) に持ってくことができたら、 5*2^60 とかいう ショボい話じゃなくて、 2^127 くらい までは(できれば 2^4095 くらいまでは)持ってけねぇか?」 っつー話。 >>172 > 探索を実行中ってことはもうプログラムがあるってこと? 『Java の宿題ここで答えます』の回答者側の常連だったので、 「とりあえず動く」レベルのものはあるのだが、やっつけで 書いたもんだから(これが Hacker というものだ)あんまり フツーのプログラマが見て分かりやすいモンじゃねぇんだよな(-_-!) 自前でやってる WebLog のほうに、近々さらすことにして、 ソーズは もうちょっと洗濯させてくれ m(_ _)m >>173 今ひとつ分からないので、自分はソースを待ちます。 やはり>>786 が論理を構築し>>1 がその論理をプログラムで実装するというのがこのスレのベストプラクティス。 なにかいいネタはないかな。 いまいちよくわかってないんだが>>111 の@ABはそれぞれ別々に証明する必要があるってこと? で@ABがいえればCがいえるってこと? >>175 プログラムの結果を参考にして証明を進める、までできれば私としてはベストですね。 今は>>166 で書いた案について考え中。 >>176 >>111 の@はなんとかなるかもしれません。 「繰り返すと1つになる」というよりは「繰り返しても集合の個数が増えない」という論法になりそうです。 ちょうど>>166 のアイデアにも関連します。 このあと軽く説明します。 >>177 @とAは対偶関係なので、 @を証明する→Bを証明する→Cが言える です。 そもそも>>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 を繰り返して集合が増えないとき」になりそうなんです。 さらに、プログラムを進めていくとどこかで「繰り返しても集合が増えない」となることも証明できそうなので、 これを利用してプログラムの計算量を減らせそう、という考えです。 時間があるときにちゃんと考えようと思います。 (実際のところ、>>154 が分かる人がどのくらいるのかちょっと気になる) 2倍の繰り返しで 1→2→4→8→16≡7→14≡5→10≡1 0→1 3の倍数が残るけど2で割り続けて奇数になったあと 3n→3n×3+1≡1 でおしまい 2倍は「好きなだけ遡れる」ところがポイントかね 13 だったらまだ理解できるんだがな。 1 → 2 → 4 → 8 → 16 ≡ 3 → 6 → 12 → 11 → 9 → 18 ≡ 5 → 10 → 20 ≡ 7 つーても、これがコラッツ予想の解決とどう結びつくのかがわからんが。 あ、 × 12 → 11 → 9 〇 12 → 24 ≡ 11 → 22 ≡ 9 だった。 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 を 考えたらいいのか …… わからん。 >>183 残念 Z/9Z において 0→1 (3倍して1を足す) は可逆でないので、これだと不十分です。 実際、この方針で例えば 16 から 9 の倍数を作ろうとすると、 2 を 2 回かけて 16→32→64 1 を引いて 3 で割って 64→21 で、9 の倍数になりません。 >>184 確かに私の予想が証明できてもすぐにはコラッツ予想に繋がりませんが、 まあ外堀を埋めるような感覚です。 それに、もし万が一私の予想に反例が見つかれば、その時点でコラッツ予想も不成立となるので、 そういう意味ではコラッツ予想を直接攻めていると言えなくもないかなと。 >> 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 の 記述は、このあたりに絡んでいるのかもしれないと思う。 >>189 下位に2^n-1が出てくるだけじゃなくて、実際のメルセンヌ数も絡むの?! ますます分からなくなる(>_<) >>190 > 下位に2^n-1が出てくるだけじゃなくて、実際のメルセンヌ数も絡むの?! > ますます分からなくなる(>_<) だからコラッツ問題は面白いんじゃないですか (^_^)v そういえば剰余コラッツ予想(前>>786 の予想)の反例が見つかったと仮定して、 その反例から元のコラッツ予想の反例を求めることは簡単なの? ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.1 2024/04/28 Walang Kapalit ★ | Donguri System Team 5ちゃんねる