コラッツ予想がとけたらいいな その2
■ このスレッドは過去ログ倉庫に格納されています
前スレ>>786 の予想は、以下の場合に証明できています。 以下、0≦k≦n-1 とします。 ・n=1,k=0 ・n=3^e, e∈N, k は任意 ・n が 5 以上の素数、Z/nZ において 2 が原始根、k≠0 ・n が 5 以上の素数、Z/nZ において 2 が原始根、n≡2 (mod 3), k=0 ・n は 83 以下の奇数, k は任意 (righ1113氏のプログラムによる検証) また、次が分かっています。 ・m∈N とする。もし n=3m の場合に任意の k で予想が正しければ、n=2m の場合も任意の k で予想は正しい。 これにより、n が偶数の場合は n が奇数の場合に帰着されます。 アルゴリズムのどこに無駄があったのかという話 (前スレ>>967 の出力結果を参照してください) 詳しい理屈は後で述べますが、例えば n=15 でいうと (3) のところは A3 と B1 の組を探す必要がありません。 さらに、A'=A3 としたときの C は [5,10,…] の方のグループは不要です。 新しい方のアルゴリズムでは、このあたりを除いています。 以下、詳しい理屈。 例えば n=15, k=5 の証明をしたいとします。 まずは普通に進めます。 〜〜〜〜〜〜〜〜〜 T を木とし、3 の倍数でない b∈T を任意に取る。 (i) b≡5,10 (mod 15) の場合 b≡5 (mod 15) または 2b≡5 (mod 15) なのでOK。 〜〜〜〜〜〜〜〜〜 次に b が 5 の倍数でない場合ですが、この場合 「偶数から 1 引いて 3 で割る」によって 5 か 10 を作るという方針で考えます。 逆に 5, 10 に 3 をかけて 1 を加えると、それぞれ 16, 31 になるので、 T が mod 45 で 16 か 31 である数を含めばよいことになります。 ここで、Z/45Z の 3 の倍数でも 5 の倍数でもない元をアルゴリズム (1) のようにグループ分けすると B0=[1,2,4,8,16,17,19,23,31,32,34,38],B2=[7,11,13,14,22,26,28,29,37,41,43,44] となります。 16,31 は B0 に属していることが分かります。 以上の操作は、アルゴリズムでいうところの A3=[5,10] と B の組をつくる という部分にあたります。結果として、(A3,B0) という組が得られます。 上で見た通り、A3 と B1 の組ができるかどうかはそもそも考える必要がありません。 ここに無駄がありました。 証明は次のように進みます。 〜〜〜〜〜〜〜〜〜〜 (ii) b が mod 45 で B0={1,2,4,8,16,17,19,23,31,32,34,38} に属する場合 b に何度か 2 をかけると mod 45 で 16 になるので、 そこから 1 を引いて 3 で割ることによって、mod 15 で 5 である元を得る。 〜〜〜〜〜〜〜〜〜〜 あとは mod45 で B2 に属する元について調べるのみです。 B2 の元は mod 135 では C1=[7,11,13,14,22,26,28,29,37,41,43,44,52,56,58,59,67,71,73,74,82,86,88,89,97,101,103,104,112,116,118,119,127,131,133,134] に含まるので、ある B0 の元に 3 をかけて 1 を加えて C1 に属せばOKです。 実際、2∈B0, 2*3+1=7∈C1 なので、証明が完了します。 ここの操作は、アルゴリズムでいうところの B2=[5,10] と C の組をつくるという部分にあたります。 ここでも B2 と C0 の組ができる必要はありませんが、アルゴリズムではそのような組を探してしまっています。 ちなみに証明の残りの部分は次のようになります。 〜〜〜〜〜〜〜〜〜〜 (iii) それ以外の場合 b に何度か 2 をかけると mod 135 で 7 になるので、 そこから 1 を引いて 3 で割ることによって、mod 45 で 2 である元を得る。 あとは(ii)に帰着される。□ 〜〜〜〜〜〜〜〜〜〜 新しいアルゴリズムでは、先に A' を決めておくことによって 必要なグループのみ扱うようにしています。 俺はあんまり素数についてのノウハウ知らないんだよね。 素数のノウハウあれば「n=q,n=qで予想が成り立つ」から「n=pqで予想が成り立つ」へ繋げるアイディアももっと湧くのかもしれない、等と思ったり。 とりあえず、目の前に大量のデータがあるわけだけど、 こういうのから何か法則を見出すのって、コツとかあるのかな とりあえず 5 以上の奇数を次のように分類してみる。 @素数かつ 2 が原始根かつ mod 3 で 2:5,11,29,53,59,83,… A素数かつ 2 が原始根かつ mod 3 で 1:13,19,37,61,67,… B素数かつ 2 が原始根でない:7,17,23,31,41,43,47,71,73,79,89,97,… C合成数:15,21,25,33,35,39,45,49,51,55,57,63,65,69,75,77,85,87,91,93,95,99,… @は任意の k で証明済み。 Aは n の倍数でない k で証明済み。 現行のプログラムでは、 ・A' の候補は {0} のみ、 ・B は 2 グループになり、A' と組ができる B は片方のみ ・C は 3 グループに分かれる というところまでは確実。 その後どうなるか要検証。 Bはまだよく分からない。 とりあえず A は {0} 以外に複数のグループに分かれる、というぐらい。 もっと細かく分類する必要がありそう。 Cはもっと分からない。 これもさらなる分類が必要と思われる。 ふーむ、まずは分類ですか。 まあいきなりきれいな法則は見つかりそうにないし、正しい方針かも。 プログラミングは3割ぐらい進みました。 あと2,3日には出来ると思います。 アルゴリズムも進化して、こちらもコーディングのやりやすさを感じています。 あ、3 の累乗は証明済みなので、>>11 では抜いてあります。 なんかこの予想に名前つけたいですね。 名前あったほうが議論しやすいですよね? >>786 なにか名前考えてもらえませんか? なんかこの予想が肯定的に解決するなら素因数分解が多項式時間でとけちゃうとか、重大な結果に繋がったりしないかな?w ジェバンニが一晩でやってくれました *Main> main 5以上の奇数nを入力してください 7 A : [[0],[1,2,4],[3,5,6]] [0] B : [[1,2,4,8,11,16],[5,10,13,17,19,20]] (4) tuple : [(0,Just 0)] 一度も現れなかったBi : [1] C : [[5,10,17,20,34,40],[13,19,26,38,41,52],[31,47,55,59,61,62]] (6) tuple : [(1,Nothing),(2,Nothing),(4,Just 1),(8,Nothing),(11,Just 0),(16,Nothing)] 一度も現れなかったCi : [2] C' : [[31,47,55,59,61,62,94,110,118,122,124,125,157,173,181,185,187,188]] (6)' tuple : [(5,Nothing),(10,Just 0),(17,Nothing),(20,Just 0),(34,Nothing),(40,Nothing),(13,Nothing),(19,Nothing),(26,Nothing),(38,Nothing),(41,Just 0),(52,Just 0)] 一度も現れなかったCi' : [] [1,2,4] B : [[5,10,13,17,19,20],[1,2,4,8,11,16]] (4) tuple : [(1,Just 1),(2,Nothing),(4,Just 0)] 一度も現れなかったBi : [] [3,5,6] B : [[1,2,4,8,11,16],[5,10,13,17,19,20]] (4) tuple : [(3,Just 1),(5,Just 0),(6,Just 1)] 一度も現れなかったBi : [] プログラムは正常終了しました。 *Main> >>18 はやいw 乙です。 (6) でいちいち全部出力すると後々大変なことになりそうな予感。 もちろんデータが多いのは利点でもあるけど、うーむ >>15 剰余コラッツ予想(Residue Collatz Conjecture)とかですかね。 英語で書くとそれっぽく見える不思議。 初代プログラムで121試したら一晩かけても答えでなかったのに2代目だと一瞬で出たんだが? そんなにパフォーマンス変わってる? それとも初代で1晩かかったのがおかしいの? >>22 かなりの高速化に成功しています。 あと実は、初代ではn=85などでうまくいかない不具合がありました。二代目では直っています。 ここのところスレとして毎日なにかしらの成果が挙がってる感じですが そろそろ停滞しはじめてもおかしくない時期ですかね? なにか壁がありそうな予感。 >>22 >>23 初代プログラムでは、上に書いた通り本来探す必要のない組を探す必要がありました。 なので多分、その「本来探す必要のない組」の中に「どう頑張っても得られない組」が混ざっていたんだと思います。 出力結果を見せていただければはっきりすると思いますが、 まあ旧版の話なのでそこまで調べる必要も無いですかね。 こういうことが起こる可能性があるということは早くから気づいていて、 実はその解消のため作ったのが二代目です。 なので、初代に不具合があったと聞いてむしろ安心しました。 そうでないと二代目を作った意味がないのでw それにしても、体感できるほど速度が上がるというのは想定以上ですね。 もしよければ、また出力結果をまとめてアップしてくれると嬉しいです。 うーんまだアルゴリズムをしっかり理解できてないな。 まずはそこからか… >>20 Nothing消します?重要でない情報なら。 >>28 今のは今ので残しておいて、別バージョンとして例えば (4) では得られた B のみ、(6) では得られた C のみ という風に出力するのは作れるでしょうか。 アルゴリズムを進めるにはその情報だけで十分なので。 それで、大量の n を調べるときは別バージョン、 個別の n を調べるときは今のという風に使い分けていければ一番良いと思います。 >>29 なるほど良いアイデアですね。 ではそのように。 大量実行バージョン作りました。ノーマルとの違いは2点です。 ・(4)では得られたBのみ、(6)では得られたCのみ出力 ・初期値nをコマンドライン引数で入れる > CollatzMod02Bigdata 85 のように使います。 ログは5から99、101から199まで取ってみました。 両方とも5分以内で実行できました。 https://github.com/righ1113/CollatzMod/tree/master/%E4%BA%8C%E4%BB%A3%E7%9B%AE >>31 乙です。 とりあえずざっと見たところ、ほとんどの処理が C' までで終わってますね。 C'' で検索すると 合わせて 4 つしか出てこない (73, 85, 127, 133)。 C''' まで出てくることはあるんだろうか。 よく見たら想定した挙動とちょっと違うような… 「3 の倍数でも n の倍数でもなく、mod n で見た時 A' に属さない」の 「mod n で見た時 A' に属さない」の部分が上手く判定できてないかもしれない。 例えば前スレ>>989 の例を見ると、 A'={1,2,4} としたとき B は {5,10,13,17,19,20} だけ出力されるとなっていますが >>18 では B : [[5,10,13,17,19,20],[1,2,4,8,11,16]] と二組出力されています。 ちょっと見てみてもらえませんか? これが直ればさらに速度も上がると思います。 >>33 これが正しい出力ですかね。 *Main> main 5以上の奇数nを入力してください 7 A : [[0],[1,2,4],[3,5,6]] [0] B : [[1,2,4,8,11,16],[5,10,13,17,19,20]] (4) tuple : [(0,Just 0)] 一度も現れなかったBi : [1] C : [[5,10,17,20,34,40],[13,19,26,38,41,52],[31,47,55,59,61,62]] (6) tuple : [(1,Nothing),(2,Nothing),(4,Just 1),(8,Nothing),(11,Just 0),(16,Nothing)] 一度も現れなかったCi : [2] C' : [[31,47,55,59,61,62,94,110,118,122,124,125,157,173,181,185,187,188]] (6)' tuple : [(5,Nothing),(10,Just 0),(17,Nothing),(20,Just 0),(34,Nothing),(40,Nothing),(13,Nothing),(19,Nothing),(26,Nothing),(38,Nothing),(41,Just 0),(52,Just 0)] 一度も現れなかったCi' : [] [1,2,4] B : [[5,10,13,17,19,20]] (4) tuple : [(1,Nothing),(2,Nothing),(4,Just 0)] 一度も現れなかったBi : [] [3,5,6] B : [[1,2,4,8,11,16]] (4) tuple : [(3,Nothing),(5,Just 0),(6,Nothing)] 一度も現れなかったBi : [] プログラムは正常終了しました。 >>34 これなら想定通りです。 てっきり「mod n で見た時 A' に属さない」を入れたおかげで早くなったのだと思っていたんですが。 そうじゃなかったんですね。 >>35 初代が遅かった原因は、自分のコーディングのまずさにあったと思っています。 プログラム、アップロードしました。失礼しました。 1つ実行するのに20分ぐらいかかったので、 ここいらへんが限界のようです。 >>37 やっぱ出ましたか。 こうなると理論上はいくらでも長くなりそう。 455=5*7*13 (Z/5Z)*, (Z/7Z)*, (Z/13Z)* それぞれで 2 の位数は 4, 3, 12 (Z/455Z)* での 2 の位数はその最小公倍数である 12 n がたくさんの素因数を持てば持つほど、また、2 の位数が小さければ小さいほど最初の Z/nZ の分割が多くなるので わりと納得の結果です。 証明がちょっと進んだけど 余白が……ではなく時間が足りない。 ほう、ちょっとづつだとしても毎日前進してるというのは凄いですな。 アイディアだけでも先行で聞かせてほしい。 とりあえず状況の整理だけ n が素数 p である場合を考える。 (Z/pZ)* において 2 が生成する部分群の指数ごとに素数を分類する。 (高校数学の言葉でいえば、2^n≡1 (mod p) となる最小の正の n に対し、(p-1)/n で定まる値が指数である。) 5 以上 200 以下の素数は次の通り。 指数 1 だけは、さらに mod 3 で分けておく。 指数1, mod 3 で 2 5,11,29,53,59,83,101,107,149,173,179,197 指数1, mod 3 で 1 13,19,37,61,67,131,139,163,181 指数2 7,17,23,41,47,71,79,97,103,137,167,191,193,199 指数3 43,109,157 指数4 113 指数6 31 指数8 73,89 指数10 151 指数18 127 概ね指数が大きいほどアルゴリズムの計算量が増えることが見て取れる。 今回は、指数 2 の場合に部分的に予想が証明できた。 ほほう、>>786 は群論の知識があるのか。 俺にはないorz. でもまあ着実に外堀が埋まっていってる感じですかね? 群論的な観点でいえば合成数の場合を素数の場合に帰着する望みはありそうなんですか? >>46 n と m が互いに素であるとき Z/mnZ は (Z/mZ)×(Z/nZ) に同型なので 何かしら関連付けることはできるかもしれませんが、 完全に帰着させるのは難しそうというのが正直なところ。 これには根拠がありまして、プログラムの出力結果を見ると 例えば n=35 にかかった計算量は n=5 と n=7 の計算量の合計よりかなり多いということが見て取れます。 そうすると、n=35 を n=5 と n=7 に帰着させるのは苦しいんじゃないかなあと思うわけです。 >>47 ふーむそうなのか。 ありがとうございます。 先は長そうですな。 このままだと、場合分けが延々と広がって収拾がつかなくなる、 といういつもの感じになりそうな雰囲気がぷんぷんしますけどね。 とりあえず示せたのはこちら。 定理 >>43 において指数が 2 であり、かつ p≡3 (mod 4) のとき、 k=1,2,…,p-1 に対して予想が成り立つ。 証明は後日。 mod 4 ですか? 意外な数字がでてきましたね。 まあ、証明を楽しみに待ちます。 途中まで。 p は 5 以上の素数で Z/pZ において 2 の生成する部分群の指数が 2 であり、p≡3 (mod 4) と仮定する。 乗法群 (Z/pZ)* において、2 で生成される部分群を A1 とし、 A1 に属さない元の全体を A2 とおく。 指数が 2 という仮定より |A1|=|A2|=(p-1)/2。 補題1 (1) A1 は (Z/pZ)* における平方数全体の集合に一致する。 (2) A2 は (Z/pZ)* において λ*(平方数) の形で表せる元全体の集合に一致する。ただし λ は平方数でない任意の (Z/pZ)* の元。 証明 (1) Z/pZ の原始根の一つを α とする。 ある d で α^d≡2 (mod p) となる。 両辺を (p-1)/2 乗すると α^(d(p-1)/2)≡1 (mod p) α の位数は p-1 だから、d(p-1)/2 は p-1 の倍数。 よって d は偶数。α^d≡2 (mod p) より 2 は平方数である。 A1 の元は 2 の累乗なので全て平方数。 A1 の要素数は (p-1)/2、(Z/pZ)* の平方数の個数も (p-1)/2 なので、 A1 は平方数全体に等しい。 (2) Z/pZ の原始根の一つを α とする。 A1 は α の偶数乗全体なので、A2 は α の奇数乗全体。 λは平方数でないので、αの奇数乗。 よって λ*(平方数) もαの奇数乗。 したがって、λ*(平方数) の形の元は A2 に属する。 λ*(平方数) の形で表せる元は (p-1)/2 個。A2 の要素数も (p-1)/2 なので、 A2 はλ*(平方数) の形で表せる元全体に等しい。□ 次に (Z/3pZ)* におけるグループ分けを考える。 そのために 2 の位数を考える。 (Z/3pZ)* は (Z/3Z)*×(Z/pZ)* に同型で、 (Z/3Z)*, (Z/pZ)* それぞれにおいて 2 の位数は 2, (p-1)/2。 p≡3 (mod 4) より (p-1)/2 は奇数。 よって、(Z/3pZ)* における 2 の位数は 2, (p-1)/2 の最小公倍数である p-1。 一方、(Z/3pZ)* の要素の個数は 2(p-1)。 (Z/3pZ)* において 2 で生成される部分群を B1 とし B1 以外の元全体を B2 とおくと、|B1|=|B2|=p-1。 補題2 3 の倍数でも p の倍数でもない整数 b に対し、 (1) b が mod 3p で B1 に属する ⇔ b が mod p で A1 に属する (2) b が mod 3p で B2 に属する ⇔ b が mod p で A2 に属する 証明 (1)のみ示せば十分である。 まず b が mod 3p で B1 に属するとすると、ある d で b≡2^d (mod 3p) と書ける。このとき b≡2^d (mod p) も成り立つので、b は mod p で A1 に属する。 したがって ⇒ が成り立つ。 ここで、射影 π:(Z/3pZ)* → (Z/pZ)* を考える。πは全射。 さらに (Z/3pZ)*, (Z/pZ)* の要素数がそれぞれ 2(p-1), p-1 であることから、πは2対1写像。 ⇒ が成り立つことから π(B1)⊂A1 が成り立つが、要素数を比較して π(B1)=A1 を得る。 したがって ⇔ が成り立つ。□ 補題3 λを平方数でない (Z/pZ)* の元とする。 x,y についての 4 つの方程式 (a) x^2+1≡y^2 (mod p) (b) x^2+1≡λy^2 (mod p) (c) λx^2+1≡y^2 (mod p) (d) λx^2+1≡λy^2 (mod p) が、(Z/pZ)* に解を持てば、n=p, k=1,…,p-1 の場合に予想が成り立つ。 証明 ・k が mod p で A1 に属する場合 T を木とし、3 の倍数でも p の倍数でもない b∈T を任意に取る。 b は mod p で A1 か A2 のいずれかに属するが、A1 の場合は b*2^d≡k (mod p) となる d が存在するのでOK。 b が mod p で A2 に属するとする。b は mod 3p で B2 に属する。 このときは、 「ある c∈A1 が存在して 3c+1∈B2」 …(*) が成り立てば予想が成り立つ。 補題1,2 より、条件(*)は 3x^2+1≡λy^2 (mod p) を満たす x,y∈(Z/pZ)* が存在することと同値。 この方程式は、3 が Z/pZ で平方数なら x^2+1≡λy^2 (mod p) と同値であり、3 が Z/pZ で平方数でなければ λx^2+1≡λy^2 (mod p) と同値である。 ・k が mod p で A2 に属する場合 上の場合において、A1 と A2, B1 と B2 を入れ替えれば同様に議論でき、 「ある c∈A2 が存在して 3c+1∈B1」 …(**) が成り立てば予想が成り立つ。 補題1,2 より、条件(**)は 3λx^2+1≡y^2 (mod p) を満たす x,y∈(Z/pZ)* が存在することと同値。 この方程式は、3 が Z/pZ で平方数なら λx^2+1≡y^2 (mod p) と同値であり、3 が Z/pZ で平方数でなければ x^2+1≡λy^2 (mod p) と同値である。□ あとは方程式 (a)〜(d) の解の存在を示せばよい。 とりあえずここまで。 前にもあったけど、こうやって代数方程式に帰着できたのは個人的に面白いと思った。 ところで流れと関係ない質問ですが、 プログラムの3のところを5に変えたら、 5x+1問題を論じている事になりますか? >>53 の続き 補題4 λを平方数でない (Z/pZ)* の元とする。 x,y についての 4 つの方程式 (a) x^2+1≡y^2 (mod p) (b) x^2+1≡λy^2 (mod p) (c) λx^2+1≡y^2 (mod p) (d) λx^2+1≡λy^2 (mod p) は、(Z/pZ)* に解を持つ。 証明 以下、≡ を = で書くことにし、「mod p」は省略する。 まず (a) を考える。方程式は y^2-x^2=1 (y+x)(y-x)=1 と変形できる。y+x=t とおくと、t≠0 で y-x=1/t である。 y+x=t y-x=1/t を x,y について解くと、x=(t^2-1)/(2t), y=(t^2+1)/(2t) 逆に t∈(Z/pZ)* が与えられたとき、t^2-1≠0, t^2+1≠0 であれば、上のように x,y を定めれば (a) の解になる。 t^2-1=0 となる t は t=±1 の2個。 t^2+1=0 となる t は存在しない (p≡3 (mod 4) より)。 よって、(a) は p-3 個の解を持つ。 次の方程式に移る前に、(a) の解に現れる x が何通りかを見ておく。 (x,y)=(x0,y0) をひとつの解とすると (x,y)=(x0,-y0) も解であり、 x0 を固定したとき対応する y は ±y0 しかない (y について 2 次方程式だから)。 よって、p-3 個の解には同じ x が2回ずつ現れるので、 x は (p-3)/2 通り。 (b) x^2+1=λy^2 について考える。 (a) の解に現れる x は (p-3)/2 通りであった。 これはすなわち、x^2+1 が 0 でない平方数となるような x は (p-3)/2 通りあるということに他ならない。 x^2+1 は 0 にならないので、残りの (p-1)-(p-3)/2=(p+1)/2 個の x に対しては x^2+1 は平方数でない数になる。 このとき x^2+1∈A2, したがって補題1より、ある y で x^2+1=λy^2 が成り立つ。 これは (b) の解である。 ((b) の解が p+1 個であることも分かる) (c)も(b)と同様に考えられる。 (a) の解に現れる y は、x と同様に (p-3)/2 通り。 したがって、y^2-1 が 0 でない平方数となるような y は (p-3)/2 通りある。 y^2-1 は y=±1 のとき 0 になるので、これも除いて残りの (p-1)-2-(p-3)/2=(p-3)/2個の y に対しては y^2-1 は平方数でない数になる。 あとは (b) と同様に λx^2+1=y^2 の解を得る。 ((c) の解は p-3 個ある) (d)は(a)と同様に計算できる。方程式は y^2-x^2=1/λ (y+x)(y-x)=1/λ と変形できる。y+x=t とおくと、t≠0 で y-x=1/(λt) である。 y+x=t y-x=1/(λt) を x,y について解くと、x=(λt^2-1)/(2λt), y=(λt^2+1)/(2t) 逆に t∈(Z/pZ)* が与えられたとき、λt^2-1≠0, λt^2+1≠0 であれば、上のように x,y を定めれば (d) の解になる。 λt^2-1=0 となる t は存在しない (λが平方数でないから)。 λt^2+1=0 となる t は 2 個 (-1,λが共に平方数でないから、-1/λ は平方数)。 よって、(d) は p-3 個の解を持つ。□ 補題3,4によって以下が示された。 定理 p が 5 以上の素数で、Z/pZ において 2 の生成する部分群の指数が 2 であり、p≡3 (mod 4) であるとき、 n=p, k=1,…p-1 の場合に予想が成り立つ。 あ、あと訂正。 >>43 で「指数1, mod 3 で 1」の欄に 131 があるけど、 131 は「指数1, mod 3 で 2」の欄でした。 ぬおー複雑すぎてついていくのがしんどいorz 平方数がどうとかいうのは群論でも普通によく使われるテクニックなんですか? >>60 群論というより、どちらかというと整数論ですかね。 少なくとも自分はよく使います。 >>1 は理解できてる? 基本このスレには3人しかいないから俺がだめなら>>1 しかいない。。。 とりあえず、この場合の平方数というのは 可換体 K の乗法群 K* の部分集合 {x2 | x ∈ K} (直積集合と紛れるおそれのないときには これを (K*)2 などと表す)の元を平方数や平方元と呼ぶことがある。(wikipediaより) であってますかね? >>64 あってます。 Z/pZ の場合は「平方剰余」という呼ばれ方をすることが多いですが、 私は「平方数」の方が慣れているのでそうしました。 誠に申し訳ないが乗法群の説明がwikiじゃよくわからんorz. むかし学校で習ったような気もするがあまりに昔の話で記憶が霞んでるorz. とりあえずこのページ見つけたけどこれでいい? https://math-note.xyz/algebra/basis-of-algebra/ >>66 >>51 で扱っているものは「環の乗法群」あるいは「体の乗法群」というもので そこには載ってないですね… 乗法群とは、「積に関して逆元を持つ要素を集めた群」です (群がよく分からなければ集合と読み替えてください)。 Z/nZ の場合、これは 0 から n-1 のうちで n と互いに素な数だけを集めたものになります。 したがって、 Z/pZ の乗法群は {1,2,...,p-1} Z/3pZ の乗法群は 3 の倍数でも p の倍数でもない元全体の集合 となります。 >>67 おお、ありがとうございます。 群に関して解説しているお勧めページありましたら教えてください。 あ〜すいません。 群じゃなくて環、体なんですかね? 有名ですけどこの辺りとか 物理のかぎしっぽ - 代数学 http://hooktail.org/misc/index.php?%C2%E5%BF%F4%B3%D8 群、環、体について基本的なことが載っています。 Z/nZ の話に絞れば、例えば Excel VBA 数学教室 - 数学辞典 - 整数論入門講座 http://excelmath.atelierkobato.com/kosiki/elementary-number/ この辺りも詳しそうです。 ざっと見たところ、上記のサイトには >>52 で用いた直積の話 ((Z/3pZ)* は (Z/3Z)*×(Z/pZ)* に同型) が載ってなさそうです。 探したらこれに載ってました。 http://nakano.math.gakushuin.ac.jp/ ~shin/html-files/Algebra_Introduction/2016/08.pdf (学習院大学の講義資料) 講義資料一覧はこちらから見られるようです。 http://nakano.math.gakushuin.ac.jp/ ~shin/html-files/Algebra_Introduction/ 私が勉強追いつくのは結構時間かかると思うのでスレは自由に進めてくださいねw >>73 まあこちらもそんなに大きな進展はないですけどね。 >>11 のAの場合 (n=p、p は 5 以上の素数、Z/pZ で 2 が原始根、p≡1 (mod 3)) で k=0 だけ抜けてるのをやはり何とかしたいので考え中。 まだ証明はできてませんが、この場合ほとんどの p ではアルゴリズムが C で終わりそうです。 実際、200 以下の出力では n=13 を除いて全ての場合でアルゴリズムが C で終わっています。 一旦理屈をすっ飛ばしますが、 n=p、p は 5 以上の素数、Z/pZ で 2 が原始根、p≡1 (mod 3) で k=0 のとき、 とりあえず以下の方法で検証できることが分かりました。 (1) 縦2マス横 (p-1)/2 マスのマス目を考え、図のように3色で塗り分ける。 https://i.imgur.com/D3N6fXO.jpg (2) Z/pZ における数列 {a[n]} を a[1]=(2p+1)/3 a[n+1]=4a[n]+1 (n≧2) で定義し、図のようにマス目に添える。 https://i.imgur.com/3goOSBZ.jpg ※ {a[n]} の一般項は ((2p+2)4^(n-1)-1)/3 である。 ※ a[n+(p-1)/2] ≡ a[n] (mod p) が成り立ち、周期的な数列となる。 (3) a[i] が Z/pZ で平方数であればその列の下側のマスに印をつける。 そうでなければ上側のマスに印をつける。 https://i.imgur.com/5H1VKGX.jpg (4) 3色とも少なくとも1つのマスに印がついていれば予想が成り立つ。 あ、>>75 の(4)は「予想が成り立つ」より「アルゴリズムが C で終わる」の方が適切です。 n=13 の場合、次のような結果になります。 https://i.imgur.com/4grIMIw.jpg 黄色マスに印がつかないので、アルゴリズムは C で終わりません。 プログラムでイレギュラーを見つけました。 プログラムの3を19に変えてn=7で、 --- (4) A' の各元 a に対し、3a+1 がどの Bi に属すかを見る。(どの Bi にも属さないこともある) --- で全ての3a+1が属さないのです。 プログラム上ではオールNothingになります。 詳しい説明は今晩します。 正確にはこうです。 プログラムの3を19に変えてn=7で、 --- (4) A' の各元 a に対し、19a+1 がどの Bi に属すかを見る。(どの Bi にも属さないこともある) --- で全ての19a+1が属さないのです。 プログラム上ではオールNothingになります。 整数論関係で盛り上がっているところで申し訳ないのだが、 二進数表記で ON ビットが二個以上連結すると、 上(偶数に向かうシークエンス)というのが、 ON ビット n に対して n - 1 個連続する。 2の倍数を XY 座標の の X に取るとすると、 偶数は、「2で割る」操作のどっかでシークエンスに引っかかる (つーか、奇数になる)。 コラッツ操作がカオティックな挙動をするというのは、 「3n+1の結果が奇数でありつづける」(つまり、下位のビットが ON でありつづける)と、「2で割り続ける」と、「偶数は割り続けると、 どこかで奇数になる」という、周期3のループに引っかかっている せいではないかという気がしてきた。 「3n+1」で無限大に発散することはありえない (メルセンヌ数との関連で、それは自明)。 つーことは、「下位がオンビットの値(奇数)で受けとめきれない」 偶数があるかどうか、みたいな話になりそうな気がする。 >>79 > 「3n+1」で無限大に発散することはありえない >(メルセンヌ数との関連で、それは自明)。 詳しく知りたいです。 >>80 メルセンヌ数(2^n - 1)は、たぶん奇数である。 とはいえ、2^0 - 1 は 1 - 1 なので、「0 は偶数だ」という反論はあると思う。 これくらいのネタを振っておかないと、数学関係では馬鹿にされるので、とりあえず。 すべての「“メルセンヌ数”ではない、4 で割って 3 余る奇数(n mod 4 = 3)、かつ 11 (1 + 2 + 8)以上の自然数」は、 (2^p - 1) + 2^p + (2^( p + 2) × q) で表される。なんでかというと、二進法で表したときに、「二個以上の 1 と 0 のあと(つーか、上位)に、 0 のみではないビット列が並んでいる」からだ。 そこに、「三倍して1を足す( 3n + 1 )操作」を繰り返すと、「2^p + (2^( p + 2) × q)」の部分に「三倍して2を足す」操作を p 回繰り返すのと同じことになる。 その間、「2^p + (2^( p + 2) × q)」の桁数が増えた結果、そのビット列に p 個以上の 1 が現れて、元の p よりも数が増えると、これは発散してしまう恐れがある。 実際に、それらしい例はある。 31 の場合、31 - 47 - 71 - 107 - 161 の列から 319 - 479 - 719 - 1079 - 1619 - 2029 を経る場合がある。 ただ、これが「無限に連鎖するか?」という話になると、「メルセンヌ素数は無限に存在するか?」みたいな話になるので、「今のところ、わからん」と言うしかない。 とりあえず、「すべての自然数が、コラッツ操作によって p と q の網(木)に引っかかるか?」を考えている。 ただ、「三倍して1を足す( 3n + 1 )操作」の回数は、 p を超えることはないことが判っている。 × > そのビット列に p 個以上の 1 が現れて 〇 > そのビット列に p 個以上連続した 1 が現れて あかん。 >> 4 で割って 3 余る奇数(n mod 4 = 3) は余計だった。すまぬ。 >>77 >>78 これ気になるんで詳細待ってます。 正常に動いていれば Nothing 以外も出てくるはずですが… >>87 さいですか。 まあ、気長に待ちますんでお気になさらず。 また通りすがりのプログラマが覗きにきました。お邪魔します。 「奇数 →(奇数 →)6で割って2余る偶数 → 奇数」 というループに乗っていないのは1だけ。 「奇数 → 偶数」というルートを通らないのは2の冪乗数だけ。 それ以外で、“ループではない”「奇数 → 6で割って2余る偶数 → 奇数」という “ルート”に乗って“いる”のは2の冪乗のうち「6で割って2余る偶数」だけ。 つまり、ここから先は、上記の条件に引っかからない「6で割って2余る偶数」と 「奇数」だけを考えればいい。 ここからは、単純に上記の条件に引っかからない「6で割って2余る偶数」と 「奇数」だけを考えればいいような気がする。 このあたりから始めて、「コラッツ操作を根っこのほうから逆に辿って、 枝がどう伸びているか」を逆に辿ってみようとしているのだが、 辿ってみた結果を どう整理したらいいのかが、正直わからん。484 と 485 とか、 変なところでニアピンしてる奴がいるんだよなぁ(どっちも3ステップ後に 182 を通る)。 これは三次元表示とかを考えたほうがいいのかね? 映像として見ることで、 なんかしらの法則性が見えてくるということも あるわけだし。 >>89 「6で割って2余る数 」か「奇数 」かたっぽだけ調べれば良いような気がします。 画像表示はカオティックなものしか得られずにう〜ん……という感じです。 >>90 確かにカオスって「断面」で見るからそういう感じはするんだよね orz つーても一次元で見ても傾向がわからんような気が。 >>88 お待たせしました。プログラムとログです。 https://github.com/righ1113/CollatzMod/tree/master/%E3%82%B3%E3%83%A9%E3%83%83%E3%83%84bx%2B1 19x+1でn=7は、 A : [[0],[1,2,4],[3,5,6]] です。最初の二つは問題ないです。 最後がC'でオールNothingとなり、C''でカラになります。ここで止めました。 どこかプログラムがバグってるんですかね。 自分はてっきり、これが無限走行へ至る道かと思ったのですが。 漏れは航空宇宙工学科出身なので 「可視化」っつーのは重要だとは思ってるんだけど、 カオス系のように「見えたからって、なんも解決せん」とか、 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余る数→一部の木にしか現れない これは言えるのでしょうか? ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.1 2024/04/28 Walang Kapalit ★ | Donguri System Team 5ちゃんねる