コラッツ予想がとけたらいいな その2
■ このスレッドは過去ログ倉庫に格納されています
今は前スレ>>786氏の予想を検証しています。
自然数aに対し、集合T(a)を
T(a)={b∈N|aとbはコラッツ操作によって同じ数に到達する}
と定める。
T(a)の形の集合を木と呼ぶ。
コラッツ予想が真であることは、自然数全体が１つの木をなすことと同値である。
で、次のように予想した。
予想
Tを木とし、n,kを自然数とする。
このとき、あるa∈Tが存在してa≡k(mod n)が成り立つ。
あるn,kについて予想が正しければ、
「コラッツ予想はa≡k(mod n)を満たす自然数aが初期値の場合だけ調べればいい」 前スレ>>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,…
②素数かつ 2 が原始根かつ mod 3 で 1：13,19,37,61,67,…
③素数かつ 2 が原始根でない：7,17,23,31,41,43,47,71,73,79,89,97,…
④合成数：15,21,25,33,35,39,45,49,51,55,57,63,65,69,75,77,85,87,91,93,95,99,…
①は任意の k で証明済み。
②は n の倍数でない k で証明済み。
現行のプログラムでは、
・A' の候補は {0} のみ、
・B は 2 グループになり、A' と組ができる B は片方のみ
・C は 3 グループに分かれる
というところまでは確実。
その後どうなるか要検証。
③はまだよく分からない。
とりあえず A は {0} 以外に複数のグループに分かれる、というぐらい。
もっと細かく分類する必要がありそう。
④はもっと分からない。
これもさらなる分類が必要と思われる。 ■ このスレッドは過去ログ倉庫に格納されています
