コラッツ予想がとけたらいいな
■ このスレッドは過去ログ倉庫に格納されています
525 名前:132人目の素数さん[sage] 投稿日:2012/09/03(月) 18:24:27.22 http://d.hatena.ne.jp/righ1113/ コラッツ予想について、証明を考えてみました。 ご指摘ご意見ご感想など、ぜひよろしくお願いします。 >>765 すみませんよく分からないです…… じっくり考えてみます。 8x+3(n=2)→12x+5(n=1)=4(3x+1)+1→3(3x+1)+1 ^^^^^^^^^^^^^^^^^^^^ ここでは小さくなっているが、 ^^^^^^^^^^ この最初の数より小さくなっていない、でしょうか。 理解しました。 ◆◆◆■■■■ 15→127 □◆◆■■■□■ 23→95 □□◆■■□□□■ 35→71 □□□■□■□■■ 53 □□□□□□□■□■ 5 □□□□□□□□□□■ 1 新しいコラッツパターンを考えました。 ◆を追加します。 すると、nの大小=x_sの大小が言えるので、 smaller(n+1)ならば、smaller(n+2) が言えると思うのですが、どうでしょうか。 2x+1→6x+4→3x+2 2x+0→1x+0 をセットの操作として考える xの係数は奇数なのでxの偶奇で次の偶奇が定まる xを2x+1、2x+0で置換してもう1セット操作する xの係数は奇数(というか3の冪)となるのでやはり次の偶奇はxの偶奇で定まる あとは帰納法で「下位nビットがnセット操作分の変化を定める」のがわかる 下位ビット固定は固定した分しか定まらないのでうまくいかない印象 コラッツパターン2にしたら、 4x+1が小さくならなくなってしまいました。無念。 構成を大幅に変えました。 コラッツパターン2も変えました。 コラッツ問題の解決の役に立つかどうかはわからんが、思いついたので投下。 f:N→N f(x)=x/2 (x:even) f(x)=(3x+1)/2 (x:odd) g:N×N→Z g(x, n)=#{0<=i<n| f^i(x):odd} とする。 このとき、0<k<=n に対し、 f^nは{x∈N|g(x, n)=k}上、広義単調増加である。 (i.e. x<y ⇒f^n(x)<=f^n(y)) 例1. g(x, 3)=1 2→1→2→1 4→2→1→2 5→8→4→2 10→5→8→4 例2. g(x, 3)=2 1→2→1→2 3→5→8→4 6→3→5→8 9→14→7→11 以下、超略証。 (n=1) f(2x+1)=3x+2 f(2x+0)=1x+0 (n=2) f^2(4x+1)=3x+1 f^2(4x+2)=3x+2 (n>2) k<=n に対し{x∈N|g(x, n)=k}は周期2^nを持ち、 f^n(x+2^n)=f^n(x)+3^k を満たす。 ここから異なる周期間の単調性が、 n=2からは周期の中での単調性が示せる。 (格子状の道の最短経路の曲がり方を一つづつ変えて行くように) >>774 >(格子状の道の最短経路の曲がり方を一つづつ変えて行くように) ここがだめ(全順序にならん)なので不成立。 一定の条件のもとで、近い数は近くなる、くらいしか言えてないか。 1つ予想を立ててみた。 自然数全体の集合を N とする。 まず木を定義する。 定義 自然数 a に対し、集合 T(a) を T(a) = {b∈N | a と b はコラッツ操作によって同じ数に到達する} と定める。 T(a) の形の集合を木と呼ぶ。 コラッツ予想が真であることは、自然数全体が1つの木をなすことと同値である。 で、次のように予想した。 予想 T を木とし、n, k を自然数とする。 このとき、ある a∈T が存在して a≡k (mod n) が成り立つ。 コラッツ予想が正しければ、T は N に一致するので、明らかにこの予想は成り立つ。 逆にいえば、予想が成り立たないような T, n, k が存在する場合、コラッツ予想も偽であることになる。 基本的な操作を補題としてまとめておく。 補題 T を木とする。このとき以下が成り立つ。 (1) a∈T かつ a が偶数 ⇒ a/2∈T (2) a∈T かつ a が奇数 ⇒ 3a+1∈T (3) a∈T ⇒ 2a∈T (4) a∈T かつ a が偶数かつ a≡1 (mod 3) ⇒ (a-1)/3 ∈ T 2つの自然数 a,b が同じ木に属することは、(1)〜(4) の繰り返しによって 一方から他方に移ることができることと同値。 さて、例えば n=1,2 の場合は予想は明らか。 n=3, k=1 or 2 の場合も難しくはないが、証明を述べておく。 命題 T を木とし、k=1 or 2 とする。 このとき、ある a∈T が存在して a≡k (mod 3) となる。 証明 任意に b∈T をとる。 b が 3 の倍数でない場合、b, 2b のいずれかが mod 3 で k に等しくなる。 2b∈T なのでOK。 b が 3 の倍数の場合、b=2^i*c (c は奇数) となるように非負整数 i, 自然数 c をとれば、 c∈T, c は奇数かつ 3 の倍数となる。 さらに 3c+1∈T であり、3c+1≡1 (mod 3) となる。 よって、上の場合に帰着されてOK。□ まだいろいろと書けることはあるけど、反応を見ながらということで。 考え方として、 いくつもの木を考えるのですか? それとも1を含む木T1のみに注目するのですか? 全ての木を考えます。 それが1つなのか複数なのかは分かりませんが。 これを書こうと思って忘れていた。 コラッツ予想は初期値が奇数の場合だけ調べればいい、というのは明らかだが >>786 の予想が正しければそれを一般化できる。 すなわち、ある n, k について予想が正しければ、 「コラッツ予想は a≡k (mod n) を満たす自然数 a が初期値の場合だけ調べればいい」 と言える。 >>791 >>792 よろしくお願いします。 modに関しては2と3には何かあるかもしれないが例えば5はどうか?といわれるとちょと疑問 今の時点ではね グラフ理論に「木」があるから名前は変えた方がいいかもね グラフ理論といえば、コラッツ操作による有向グラフとしてなんかできないかなー、 と昔考えたけど、グラフ理論で扱われるのは有限頂点のグラフだった…… いや、まさにグラフ理論の木のつもりで書いたんじゃないか? というか「木」は数学では同値類になるか。 自分が書くならこんな感じ。 関数 f:N→N を f(x)=x/2 (x:偶数) f(x)=3x+1 (x:奇数)とする x,y∈Nに対し, x〜y⇔∃i,j∈N, f^i(x)=f^j(y) は同値関係となる。 イメージは1を根とする木かな。 わからなくもないけど ・頂点が無限 ・1→4→2→1のループがある なのでなおさら木とは呼びづらい。 確かに「木」だと誤解を招いてしまうかもしれませんね。 「束」のように複数の意味で使われる例もありますが… 良い名称を思いついたら変えようと思います。 うーん、やっぱり木が一番しっくりくる。 もうしばらく様子を見ます。 同値類を用いた定義も承知していますが、 一応高校数学の範囲で理解できるよう上のように定義しました。 あと、グラフ理論では無限個の頂点や辺を持つグラフも扱っていたと思います。 予想についての結果をひとつ追加。 命題 任意の木は 3 の倍数を含む。 証明 T を木とし、任意に b∈T をとる。 b が 3 の倍数の場合、示すことはない。 b が 3 の倍数でない場合、 b は mod 9 で 1,2,4,5,7,8 のいずれか。 ここで、Z/9Z において 2 は原始根であるので、 b*2^d≡1 (mod 9) を満たす d∈N が存在する。 b*2^d∈T かつ b*2^d は偶数で b*2^d≡1 (mod 3) なので、 c=(b*2^d-1)/3 とおくと c∈T である。 さらに b*2^d-1≡0 (mod 9) より c=(b*2^d-1)/3≡0 (mod 3) なので、T は 3 の倍数を含む。 □ ふーむ。 例えば同様の議論で他の倍数も通用したりするの? >>801 n=3^e, e∈N の形のときは同様に議論できます。これから書きます。 それ以外の場合、Z/3nZ において 2 が原始根になりえないので、全く同じ議論でというわけにはいきません。 n=4,8,16,… の場合は議論するまでもなく成り立ちますが… ちなみに、ある n に対して n の倍数が木に含まれるかという問題は>>786 の予想において k=0 の場合ですが、 n が奇数のとき、これは k が他の値の場合よりも難しいと思います。 n=3 の場合もそうでしたが、n=5 あたりを考えてみても分かります。 これもそのうち書こうと思います。 n=3^e, e∈N の場合を考える。 補題 任意の 2 以上の整数 e に対して 4^(3^(e-2)) ≡ 1+3^(e-1) (mod 3^e) 証明 e=2 のときは (左辺)=(右辺)=4 よりOK。 ある e で成り立つとすると、 4^(3^(e-2)) = 1+3^(e-1)+3^e*m, m∈Z と表せる。このとき、 4^(3^(e-1)) = (1+3^(e-1)+3^e*m))^3 ≡ 1+3^e (mod 3^(e+1)) より、e+1 でも成り立つ。□ (続く) 補題 e を 2 以上の整数とする。 このとき、Z/(3^e)Z において 2 は原始根である。 証明 2 の位数を d とおく。 2^d≡1 (mod 3^e) より 2^d≡1 (mod 3) したがって、d は偶数である。 また、d は φ(3^e)=2*3^(e-1) の約数である。 ここで、前補題より 2^(2*3^(e-2)) = 4^(3^(e-2)) ≡ 1+3^(e-1) ≠ 1 (mod 3^e) (≠は「≡でない」を表すとする) なので、d=2*3^(e-1) となるしかない。 したがって、2 は原始根である。□ 定理 T を木、e を 2 以上の整数、k を 任意の自然数とする。 このとき、ある a∈T が存在して a≡k (mod 3^e) が成り立つ。 証明 ・ k が 3 の倍数でない場合 3 の倍数でない b∈T を任意に取る。 2 が Z/(3^e)Z の原始根であることから、 b*2^d≡k (mod 3^e) を満たす d∈N が存在する。 a=b*2^d とすればよい。 ・ k が 3 の倍数である場合 3 の倍数でない b∈T を任意に取る。 2 が Z/(3^(e+1))Z の原始根であることから、 b*2^d≡3k+1 (mod 3^(e+1)) を満たす d∈N が存在する。 このとき、a=(b*2^d-1)/3 とおくと、 a∈T かつ a≡k (mod 3^e) となる。□ mod 5とか mod 7について何か出すのは難しいかもしれないけど 3^n-1についてとかなら何か出せるんだろうか? >>804 「何か出す」の意味がよく分かりませんが mod 5, mod 7 の場合は任意の k について予想が成り立つことが分かっています。 3^n-1 の場合は特に考えたことはないんですが、何かアイデアがあれば教えてください。 やはり先に分かっていることについて一通り書いた方がいいですね。 以下、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=7, 13, 17, k は任意 また、次が分かっています。 ・m∈N とする。もし n=3m の場合に任意の k で予想が正しければ、n=2m の場合も任意の k で予想は正しい。 これにより、n が偶数の場合は n が奇数の場合に帰着されます。 偶数から奇数への帰着について先に書いておきます。 定理 m∈N とする。もし n=3m の場合に任意の k で予想が正しければ、n=2m の場合も任意の k で予想は正しい。 証明 T を木とし、n=2m とする。 k が奇数の場合に証明できれば、奇数に 2 をかけていくことで k が偶数の場合も証明できる。 k を奇数とする。 仮定より、ある b∈T が存在して b≡(3k+1)/2 (mod 3m) となる。このとき、 2b≡3k+1 (mod 6m) であり、2b∈T, 2b は偶数かつ 2b≡1 (mod 3)。 よって a=(2b-1)/3 とおくと a∈T かつ a≡k (mod 2m) □ >>803 の結果と合わせれば、 n=2^d*3^e の形の場合、任意の k で予想が正しいことになります。 また、私見ですが、n が偶数の場合はこの定理によって奇数の場合に帰着させる以外の手はなさそうに思います。 他の方法がありそうならご一報ください。 そういうわけで、今後は n が奇数の場合のみ考えようと思います。 >>1 に聞いてみたいが>>786 の実力はどれくらい期待できる? >>808 いえ、それほどでも 個別の n, k について考えるだけならそれほどハードルは高くないと思いますので、 一緒に考えてくれる方がいたら嬉しいなと思います。 さしあたって次の目標は n=15, 19 あたりです。 予想 T を木とし、n, k を自然数とする。 このとき、ある a∈T が存在して a≡k (mod n) が成り立つ。 ↑まだこれのイメージがわいてない段階だから一緒に考えるっつってもあんま期待すんなよw まあ問題のとらえ方というか予想の立て方が、普通の人より高いところに目線があるんだろなって雰囲気は感じる。 予想がなかなかイメージ湧かないな〜 プロローグでプログラムを組もうとしたときのような困難さを感じるorz. とりあえず、プログラム組んで虱潰しで潰していけばn=15とかもなにがしかの結果が出るのだろうか? そんな甘くない? 例えば>>1 なら>>786 の予想を理解して、しらみつぶしで探索するようなプログラムを、書けそう?書けなさそう? プログラムでやろうと思ったら結局、原始根である必要があるんだろうか? うーん。わからん。 x(2^n)-1→x(3^n)-1 (x,nは自然数) がわかってるから、2か3が原始根ならどうとでもなる気が >>818 プログラムはド素人です。 上で言ったのは、「イメージがわかない」というのをどうにかできないかなーということです。 この予想に至った経緯を図を交えて述べてみます。 そんな大層なものではないですが。 まず、木のイメージは次の図のような感じです。 https://i.imgur.com/iwwClSE.jpg ここで、「3倍して1を足す」は斜めの線、「2で割る」は縦線で表しています。 縦の並びは (a)全て3の倍数 (b)3n+1, 3n+2 の形の数が交互に現れる の2通りに分類されます。 (a)の場合はこれ以上分岐しません。 (b)の場合は 3n+1 の形の偶数から分岐があります。 図のようなイメージです。 https://i.imgur.com/EWvMJyK.jpg そして、これは経験的に知っていたんですが、 3n+1 の形の偶数から分岐した先は3回に1回だけ3の倍数になります。 https://i.imgur.com/sg3KFl2.jpg (これをちゃんと証明したのが>>800 です) このことから、 「どんな数からでも上手くさかのぼれば3の倍数に到達する」 ⇒「コラッツ予想は初期値が3の倍数の場合だけ調べれば十分」 ということを考えたことがありました。 それとは別に ・初期値が奇数の場合だけ調べれば十分 ・初期値が 4n+3 の形の場合だけ調べれば十分 とかはよく見る話だと思います。 それで、この間ふと「これって一般化できないかな」と思ったのです。 すなわち「コラッツ予想は、初期値が n で割って k 余る数場合だけ調べれば十分」は成り立つのかと。 で、これを証明するにはどうすればいいかを考えた結果、 >>786 の予想に落ち着きました。 「コラッツ予想は初期値が3の倍数の場合だけ調べれば十分」 これはこのスレでも>>132 で言及されているね 「コラッツ予想は、初期値が n で割って k 余る数場合だけ調べれば十分」 こっちのほうがアイディアはわかりやすいな ん、「コラッツ予想は、初期値が n で割って k 余る数場合だけ調べれば十分」と>>786 の予想が頭の中で微妙にすっきり繋がらないな もうちょっと時間くれ てことは例えば「コラッツの予想は5の倍数だけ調べれば十分」も証明済みってことか へ〜〜 個別のnやkに対してどういう戦略で証明を進めていくのか説明してくれたらもしかしたらプログラムでしらみつぶし探索できるかもしれないな。 やや楽観的すぎるかもしれないが。 多分、>>1 が実装してくれるww >>819 確かに使えそうですが…いまいち使い方が思いつきません。 もし具体的なアイデアがあればお願いします。 >>825 ではお言葉に甘えて。 余談ですが、コラッツ予想の証明の方針として、 「1以外のどんな自然数もコラッツ操作によって自身より小さい数になる」 を示すというのが(多分)よく取られます。 例えば偶数や 4n+1 の形の奇数は自身より小さい数になることがすぐに分かるので、 「初期値が 4n+3 の形の場合に調べれば十分」 ということがわかります。 そして、この方針は>>786 の予想とは全く別物だと私は思っています。 上の論法では任意の木に 4n+3 の形の数が含まれることは(多分)説明できていませんし、 逆に「任意の木に○○が含まれる」ということから「○○以外の数は自身より小さくなる」という話に繋げることもできないと思います。 このように、 「初期値が n で割って k 余る数の場合だけ調べれば十分」 を証明する方法は1つとは限りません。 >>786 の予想はあくまでそのうちの一つの手段です。 たとえ>>786 の予想の証明を諦めたとしても 「初期値が n で割って k 余る数の場合だけ調べれば十分」を諦めたことにはなりませんので、 そこらへん混同しないようお願いします。 次は n=5 の場合の証明を書こうと思います。 ・n=5, k=1,2,3,4 の場合 定理 T を木とし、k を 1,2,3,4 のいずれかとする。 このとき、ある a∈T が存在して a≡k (mod 5) となる。 証明 b∈T を任意にとる。 b が 5 の倍数でなければ、 Z/5Z において 2 が原始根であることから、 b*2^d≡k (mod 5) となる d∈N が存在する。b*2^d∈T なのでOK。 b が 5 の倍数のときは、 奇数になるまで b を 2 で割って得られる奇数を b' とする。 b' も 5 の倍数で、b'∈T である。 さらに b' は奇数だから 3b'+1∈T 3b'+1≡1 (mod 5) なので、上の場合に帰着される。□ ・n=5, k=0 の場合 まずは証明を書きますが、ちょっと天下り的なのであとで補足を書きます。 定理 任意の木は 5 の倍数を含む。 証明 3 の倍数でない b∈T を任意に取る。 (>>787 の命題によってこのような仮定が許される) (1) b が 5 の倍数の場合 この場合は示すことはない。 (2) b≡1,2,4,8 (mod 15) の場合 Z/15Z において 1 に 2 をかけていくと 1→2→4→8→1→… となって循環する。したがって、 b*2^d≡1 (mod 15) を満たす d∈N が存在する。b*2^d は>>787 の補題(4)の仮定を満たすので、 (b*2^d-1)/3∈T であり、さらに (b*2^d-1)/3≡0 (mod 5) なので T が 5 の倍数を含むことが示された。 (3) それ以外の場合 0 から 14 のうち 3 の倍数, 5 の倍数, 1,2,4,8 を除くので、残りは b≡7,11,13,14 (mod 15) の場合である。 b は mod 45 では 7,11,13,14,22,26,28,29,37,41,43,44 のいずれか。ここで、7 に 2 をかけていくと 7→14→28→11→22→44→43→41→37→29→13→26→7→… となり、上記の全ての数を通って循環する。(群論の知識があれば直接計算しなくても分かります) したがって、 b*2^d≡7 (mod 45) を満たす d∈N が存在する。b*2^d は>>787 の補題(4)の仮定を満たすので、 (b*2^d-1)/3∈T であり、さらに (b*2^d-1)/3≡2 (mod 15) なので、(2) の場合に帰着される。□ ・3 の倍数でない b をとったことについて あとで>>787 補題(4)(以下、単に(4)と書く)を使うためです。 5 の倍数を構成するには (2) か (4) を使う必要がありますが、 (2) を使って構成するのは難しそうでした。 ・≡7 (mod 45) を選んだことについて (4)によって直接 5 の倍数を作ることができないので、 一旦 mod 15 で 1,2,4,8 のいずれかとなるような数を作ることを目指しています。 そのために、7,11,…,44 のそれぞれから 1 を引いて 3 で割ってみて 1,2,4,8 のいずれかになるかどうかを確かめました。 その結果 (7-1)/3=2 が見つかったので、7 としました。 他にも (13-1)/3=4 なので ≡13 (mod 45) に変えても証明できます。 むむう。 この感じだとプログラム化はかなり難易度高いかなぁ ふと思ったのですけど、プログラムとして ・T(1)を列挙 ・a∈T(1)がa≡k mod nかを調べる (kとnには具体的な数を入れる) とかやっても意味ないですよね…… プログラム化は難しいと思うけど、 奇数kについて R_1(k)={奇数m|ある整数r≧0について3m+1=k・2^r} R_n+1(k)=∪_[m∈R_n(k)] R_1(m) という操作でできる集合R_n(k)を考えると、 n→∞におけるR_n(1)の極限R(1)がすべての奇数の集合と一致するかどうか、という問題はコラッツ予想と同じにならないかな? 証明が完成するまでmodに何回3をかけたかに注目したら何か出てくるかな? >>837 うーん、そうですね… k が既に 1 に到達することが分かっている数の場合、 a=k と取れてしまうわけですから調べる意味がなくなります。 wikipediaによると、5*2^60 までは 1 に到達することが分かっているそうなので、 k を 5*2^60 より大きくしないといけないことになりますが… >>838 今のところそうですね。 まあ、やってみたら自然とそうなったという感じです。 プログラム組めるとデータ量が圧倒的に違うからなんとかしたいなあ >>786 がプログラム組めないのが痛いなあ 可能な限りシステマチックな手順に証明手順を落とし込めないですか? n が素数の場合に限りましたが、なんとか手順をまとめてみました。 以下の操作が終了すれば、n=p の場合に任意の k で予想が成り立つことになるはずです。 プログラムに関しては素人なので、おかしいところ、実装が難しいところ等あるかもしれません。 例を併記して述べますが、あとで操作だけをまとめたものも書きます。 p を 5 以上の素数とする。 以下の例は、p=7 の場合である。 (1) Z/pZ において、2 を何回かかけることによって移りあう元を同じグループとして A1,A2,… とグループ分けする。 例 Z/7Z において A1={0} A2={1,2,4} A3={3,5,6} (2) Z/3pZ において、3 の倍数でも p の倍数でもない数について同様に B1,B2,… とグループ分けする。 例 Z/21Z において B1={1,2,4,8,11,16} B2={5,10,13,17,19,20} (3) Z/pZ の各元 a に対し、a がどの Ai に属すか、3a+1 がどの Bj に属すかを見る。(どの Bj にも属さないこともある) 各 a に対して得られた組 (Ai,Bj) を記録していく。組が被った場合、改めて記録しなくてもよい。 例 a=0 に対しては 0∈A1,3*0+1=1∈B1 なので、組 (A1,B1) を得る。 全て調べると、(A1,B1),(A2,B1),(A2,B2),(A3,B1),(A3,B2) を得る。 (4) A1,A2,… のうち、全ての Bj との組が得られていないものがあれば、それをひとつ選び、A'とする。 以下の操作を全て終えた後、まだ選んでない A' の候補があれば A' を取り換えてまたここからやり直す。 A' の候補が残っていなければ操作を終了する。 例 得られていない組は (A1,B2) だけなので、A'=A1 とする。 (5) Z/9pZ において、条件 「mod 3p で見た時、組 (A',Bj) が得られていないような Bj に属する」 を満たす数全体を考え、この数たちを (1), (2) と同様にグループ分けし、C1,C2,… とする。 例 組 (A',Bj) が得られていないような Bj は B2 しかない。 mod 21 で B2 に属するような Z/63Z の元を列挙すると {5,10,13,17,19,20,26,31,34,38,40,41,47,52,55,59,61,62} となり、これをグループ分けすると C1={5,10,17,20,34,40} C2={13,19,26,38,41,52} C3={31,47,55,59,61,62} を得る。 (6) 組 (A',Bj) が得られているような Bj 全てと、C1,C2,… に対して (3) と同じことを行う。 例 組 (A',Bj) が得られているような Bj は B1 のみ。 B1 の元 a に対し、3a+1 が C1,C2,C3 に属するかを見ていく。 (B1,C1),(B1,C2) を得る。 (7) (4) の「A1,A2,…」を「組 (A',Bj) が得られているような Bj 全て」に、 Bj を Cj に、A' を B' に取り換えて同じことをする。 さらに (5),(6) の A,B,C をそれぞれ B,C,D に、p を 3p に取り換えて同じことをする。 例 組 (B1, C3) のみ得られていないので、B'=B1 とする。 組 (B',Cj) が得られていないような Cj は C3 しかない。 mod 63 で C3 に属するような Z/189Z の元を列挙すると {31,47,55,59,61,62,94,110,118,122,124,125,157,173,181,185,187,188} となり、これをグループ分けすると D1={31,47,55,59,61,62,94,110,118,122,124,125,157,173,181,185,187,188} という一つのみのグループを得る。 組 (B',Cj) が得られているような Cj は C1, C2 の二つ。 (3) と同様に調べると、組 (C1,D1),(C2,D1) を得る。 (8) (7) と同様に、さらに再帰的に繰り返す。 例 C' の候補がないので、(8)を終了する。 (7)に戻るが、B' の候補が残っていないので(7)を終了する。 (4)に戻るが、A' の候補が残っていないので全ての操作を終了する。 操作だけをまとめます p を 5 以上の素数とする。 (1) Z/pZ において、2 を何回かかけることによって移りあう元を同じグループとして A1,A2,… とグループ分けする。 (2) Z/3pZ において、3 の倍数でも p の倍数でもない数について同様に B1,B2,… とグループ分けする。 (3) Z/pZ の各元 a に対し、a がどの Ai に属すか、3a+1 がどの Bj に属すかを見る。(どの Bj にも属さないこともある) 各 a に対して得られた組 (Ai,Bj) を記録していく。組が被った場合、改めて記録しなくてもよい。 (4) A1,A2,… のうち、全ての Bj との組が得られていないものがあれば、それをひとつ選び、A'とする。 以下の操作を全て終えた後、まだ選んでない A' の候補があれば A' を取り換えてまたここからやり直す。 A' の候補が残っていなければ操作を終了する。 (5) Z/9pZ において、条件 「mod 3p で見た時、組 (A',Bj) が得られていないような Bj に属する」 を満たす数全体を考え、この数たちを (1), (2) と同様にグループ分けし、C1,C2,… とする。 (6) 組 (A',Bj) が得られているような Bj 全てと、C1,C2,… に対して (3) と同じことを行う。 (7) (4) の「A1,A2,…」を「組 (A',Bj) が得られているような Bj 全て」に、 Bj を Cj に、A' を B' に取り換えて同じことをする。 さらに (5),(6) の A,B,C をそれぞれ B,C,D に、p を 3p に取り換えて同じことをする。 (8) (7) と同様に、さらに再帰的に繰り返す。 おおお凄い あんたプログラムの才能あるよ まあ数学できる人はプログラムできても不思議じゃないけど あとは>>1 に任せたっwww すいません、(7) 以降に無駄があったので次のように修正します。 (7) (6) で得られた組に全ての Ci が現れれば操作を終了する((4)に戻る)。 一度も現れなかった Ci があれば、 Z/27pZ において、条件 「mod 9p で見た時、(6)の組に一度も現れなかった Ci に属する」 を満たす数全体を考え、この数たちを (1), (2) と同様にグループ分けし、D1,D2,… とする。 (8) (6)の組に現れた Cj 全てと D1,D2,… に対して (3) と同じことを行う。 (9) (7)(8) の C,D をそれぞれ D,E に、p を 3p に、(6) を (8) に変えて同じこと行う。 以降、同様に繰り返す。 例に変化はありません。 (7) 以降は再帰ではなく単なる繰り返しになります。 いくつか補足をば。 このアルゴリズムの正当性を説明するには、次の補題が必要です。 補題 p を 5 以上の素数とする。 任意の木には、3 の倍数でも p の倍数でもない数が含まれる。 証明 T を木とし、3 の倍数でない数 b∈T を任意に取る。 b が p の倍数でなければ示すことはない。 b が p の倍数であるとき、 奇数になるまで b を 2 で割って得られる奇数を b' とおくと 3b'+1∈T であり、3b'+1 は 3 の倍数でも p の倍数でもない。□ 上で書いた例を元に、 n=7 でどのように証明ができるのかをざっと説明します。 T を木とし、3 の倍数でも 7 の倍数でもない b∈T を任意に取る。 b は mod 21 で B1,B2 のいずれかに含まれる。 B1 であれば Z/7Z の全ての数を構成できる。 B2 であれば Z/7Z の 0 以外の全ての数を構成できる。 b∈B2 のときは、b は mod 63 で C1,C2,C3 のいずれかに含まれる。 C1,C2 であれば、B1 に含まれる数を構成できる。 b∈C3 のときは、b は mod 189 で D1 に含まれる。 よって C1 または C2 に含まれる数を構成できる。 大体こんな流れです。 あと、特定の k のみについて検証したければ (1)の出力を k が含まれるグループのみにして下さい。 >>1 なら実装出来そう? >>1 が無理ならプログラム板にでもいって助っ人を探してくるけど おっさすが 頑張れー 工数はどれくらいかな 1週間位? できればプログラムは計算過程を出力して >>786 が検証できるようにして欲しいな ちなみにこのアルゴリズム素数限定らしいですが 合成数を入力したらどうなるんですかね 無限ループ? >>1 も>>852 もありがとうございます。 >>857 素数に限ったのは>>851 の補題があるから…と思っていたのですが、 よく考えたらこれ p が素数じゃなくても奇数なら成り立ちますね。 アルゴリズムの方も、素数に限らず奇数なら大丈夫な気がしてきました。 偶数を入れてしまうと、2倍写像が可逆にならないことにより 仮にプログラムがうまく動いたとしても証明になりません。 今日は(3)までできました。Haskellでやっています。 *CollatzMod> main 素数pを入力してください 7 Z/pZ : [0,1,2,3,4,5,6] A : [[0],[1,2,4],[3,5,6]] Z/3pZ : [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] B : [[1,2,4,8,11,16],[5,10,13,17,19,20]] (3) tuple : [([0],Just [1,2,4,8,11,16]),([1,2,4],Just [1,2,4,8,11,16]),([1,2,4],Nothing),([3,5,6],Just [5,10,13,17,19,20]),([1,2,4],Just [5,10,13,17,19,20]),([3,5,6],Just [1,2,4,8,11,16])] *CollatzMod> n=19を手計算でやろうとしたら結構大変で中断w 根性なくてすまん しかし>>786 もプログラム覚えたらいいのに メキメキ上達すると思いますよ? 便利だし >>859 おお、なんか感動した。 ありがとう、続きもなにとぞよろしく頼みます。 >>862 いや、難しさを共有できるだけでもありがたいです。 n=19 の場合は 2 が原始根になるので A は A1={0}, A2={0以外} の2つ、B も2つで得られない組は1つのみ、 それから C が3つ、という感じになるはずですがどうだったでしょうか。 2 が原始根かつ p≡1 (mod 3) のときは必ずこうなります。 ですが、この後それぞれの C を含む組が得られるか、という部分について一般的な理論がまだできていません。 プログラムを通じてその辺のヒントが得られればいいなと思っています。 >>863 いや、やろうとしたことはあるんですが、 プログラミングができる環境を得る方法がよく分からなくて断念した経験がありまして。 また試してみようかな PCが一台あれば、無償アプリのどれかを使ってなんとかなりそうに思う >>1 のプログラム作成の進捗具合はどうですかね? そろそろ本格的に難しい部分に差し掛かって手が止まってもおかしくないですが >>1 をみくびりすぎかな? ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.1 2024/04/28 Walang Kapalit ★ | Donguri System Team 5ちゃんねる