コラッツ予想がとけたらいいな その2
■ このスレッドは過去ログ倉庫に格納されています
なんだか盛り上がってますが
とりあえず>>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の通りになります。 ■ このスレッドは過去ログ倉庫に格納されています
