18/05/10 22:12:02.92 ogyKPvh0.net
今は前スレ>>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が初期値の場合だけ調べればいい」
3:１３２人目の素数さん
18/05/10 22:17:20.64 vsrY1r+A.net
>>1乙
4:前786
18/05/10 23:48:07.63 Ws8+Hi53.net
前スレ>>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 が奇数の場合に帰着されます。
5:前786
18/05/10 23:53:50.84 Ws8+Hi53.net
あれ、コピペが抜けてた。
>>1乙
6:１３２人目の素数さん
18/05/11 00:02:28.46 lDGPA2LH.net
自己満足しました
7:前786
18/05/11 20:23:02.52 OFsS5uwl.net
アルゴリズムのどこに無駄があったのかという話
（前スレ>>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 の組ができるかどうかはそもそも考える必要がありません。
ここに無駄がありました。
8:前786
18/05/11 20:23:37.57 OFsS5uwl.net
証明は次のように進みます。
～～～～～～～～～～
(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' を決めておくことによって
必要なグループのみ扱うようにしています。
9:１３２人目の素数さん
18/05/11 20:56:06.22 b0n49LZW.net
俺はあんまり素数についてのノウハウ知らないんだよね。
素数のノウハウあれば「n=q,n=qで予想が成り立つ」から「n=pqで予想が成り立つ」へ繋げるアイディアももっと湧くのかもしれない、等と思ったり。
10:１３２人目の素数さん
18/05/11 21:47:49.08 b0n49LZW.net
とりあえず、目の前に大量のデータがあるわけだけど、
こういうのから何か法則を見出すのって、コツとかあるのかな
11:前786
18/05/11 23:35:34.41 OFsS5uwl.net
とりあえず 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} 以外に複数のグループに分かれる、というぐらい。
もっと細かく分類する必要がありそう。
④はもっと分からない。
これもさらなる分類が必要と思われる。
12:１３２人目の素数さん
18/05/11 23:57:27.27 b0n49LZW.net
ふーむ、まずは分類ですか。
まあいきなりきれいな法則は見つかりそうにないし、正しい方針かも。
13:righ1113
18/05/11 23:58:26.25 SBH2/eHc.net
プログラミングは3割ぐらい進みました。
あと2,3日には出来ると思います。
アルゴリズムも進化して、こちらもコーディングのやりやすさを感じています。
14:前786
18/05/12 01:03:18.42 xLUYWUsP.net
あ、3 の累乗は証明済みなので、>>11では抜いてあります。
15:１３２人目の素数さん
18/05/12 01:06:51.91 fD/walWV.net
なんかこの予想に名前つけたいですね。
名前あったほうが議論しやすいですよね？
>>786なにか名前考えてもらえませんか？
16:１３２人目の素数さん
18/05/12 01:19:48.51 fD/walWV.net
なんかこの予想が肯定的に解決するなら素因数分解が多項式時間でとけちゃうとか、重大な結果に繋がったりしないかな？ｗ
17:１３２人目の素数さん
18/05/12 02:27:14.92 fD/walWV.net
離散対数問題とか絡んできそうな気が若干する
18:righ1113
18/05/12 04:55:29.69 +tHVZn3R.net
ジェバンニが一晩でやってくれました
*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>
19:１３２人目の素数さん
18/05/12 09:10:52.54 fD/walWV.net
おお、乙です。
20:前786
18/05/12 10:47:03.59 xLUYWUsP.net
>>18
はやいｗ
乙です。
(6) でいちいち全部出力すると後々大変なことになりそうな予感。
もちろんデータが多いのは利点でもあるけど、うーむ
21:前786
18/05/12 10:55:50.38 xLUYWUsP.net
>>15
剰余コラッツ予想(Residue Collatz Conjecture)とかですかね。
英語で書くとそれっぽく見える不思議。
22:１３２人目の素数さん
18/05/12 16:47:33.40 fD/walWV.net
初代プログラムで121試したら一晩かけても答えでなかったのに２代目だと一瞬で出たんだが？
そんなにパフォーマンス変わってる？
それとも初代で１晩かかったのがおかしいの？
23:righ1113
18/05/12 17:25:28.39 jylFM2dv.net
>>22
かなりの高速化に成功しています。
あと実は、初代ではn=85などでうまくいかない不具合がありました。二代目では直っています。
24:１３２人目の素数さん
18/05/12 17:56:15.06 fD/walWV.net
ほう、そいつは素晴らしい
25:１３２人目の素数さん
18/05/12 18:02:57.93 fD/walWV.net
ここのところスレとして毎日なにかしらの成果が挙がってる感じですが
そろそろ停滞しはじめてもおかしくない時期ですかね？
なにか壁がありそうな予感。
26:前786
18/05/12 19:04:42.48 xLUYWUsP.net
>>22>>23
初代プログラムでは、上に書いた通り本来探す必要のない組を探す必要がありました。
なので多分、その「本来探す必要のない組」の中に「どう頑張っても得られない組」が混ざっていたんだと思います。
出力結果を見せていただければはっきりすると思いますが、
まあ旧版の話なのでそこまで調べる必要も無いですかね。
こういうことが起こる可能性があるということは早くから気づいていて、
実はその解消のため作ったのが二代目です。
なので、初代に不具合があったと聞いてむしろ安心しました。
そうでないと二代目を作った意味がないのでｗ
それにしても、体感できるほど速度が上がるというのは想定以上ですね。
もしよければ、また出力結果をまとめてアップしてくれると嬉しいです。
27:１３２人目の素数さん
18/05/12 19:19:24.68 fD/walWV.net
うーんまだアルゴリズムをしっかり理解できてないな。
まずはそこからか…
28:righ1113
18/05/12 19:24:14.47 jylFM2dv.net
>>20
Nothing消します？重要でない情報なら。
29:前786
18/05/12 21:48:00.59 xLUYWUsP.net
>>28
今のは今ので残しておいて、別バージョンとして例えば
(4) では得られた B のみ、(6) では得られた C のみ
という風に出力するのは作れるでしょうか。
アルゴリズムを進めるにはその情報だけで十分なので。
それで、大量の n を調べるときは別バージョン、
個別の n を調べるときは今のという風に使い分けていければ一番良いと思います。
30:righ1113
18/05/12 23:42:46.59 Qz4XKKj5.net
>>29なるほど良いアイデアですね。
ではそのように。
31:righ1113
18/05/13 13:22:27.62 Nz2Y2iKL.net
大量実行バージョン作りました。ノーマルとの違いは2点です。
・(4)では得られたBのみ、(6)では得られたCのみ出力
・初期値nをコマンドライン引数で入れる
> CollatzMod02Bigdata 85 のように使います。
ログは5から99、101から199まで取ってみました。
両方とも5分以内で実行できました。
URLﾘﾝｸ(github.com)
32:前786
18/05/13 14:48:12.95 0JEK0/oR.net
>>31
乙です。
とりあえずざっと見たところ、ほとんどの処理が C' までで終わってますね。
C'' で検索すると 合わせて 4 つしか出てこない (73, 85, 127, 133)。
C''' まで出てくることはある�
33:ｾろうか。
34:前786
18/05/13 16:45:43.20 0JEK0/oR.net
よく見たら想定した挙動とちょっと違うような…
「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]]
と二組出力されています。
ちょっと見てみてもらえませんか？
これが直ればさらに速度も上がると思います。
35:righ1113
18/05/13 17:37:11.27 Nz2Y2iKL.net
>>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 : []
プログラムは正常終了しました。
36:前786
18/05/13 17:57:57.52 0JEK0/oR.net
>>34
これなら想定通りです。
てっきり「mod n で見た時 A' に属さない」を入れたおかげで早くなったのだと思っていたんですが。
そうじゃなかったんですね。
37:righ1113
18/05/13 18:08:42.61 Nz2Y2iKL.net
>>35
初代が遅かった原因は、自分のコーディングのまずさにあったと思っています。
プログラム、アップロードしました。失礼しました。
38:righ1113
18/05/13 20:06:20.61 Nz2Y2iKL.net
>>32
n=455でC'''が出てきました。
大量出力でしたが、ログを取りました。
URLﾘﾝｸ(github.com)
39:１３２人目の素数さん
18/05/13 20:33:55.94 EEZthzcB.net
そんなデカい数まで走らせられるのか
凄いな
40:righ1113
18/05/13 21:01:46.58 pZHBmlYZ.net
1つ実行するのに20分ぐらいかかったので、
ここいらへんが限界のようです。
41:前786
18/05/13 22:47:57.50 0JEK0/oR.net
>>37
やっぱ出ましたか。
こうなると理論上はいくらでも長くなりそう。
455=5*7*13
(Z/5Z)*, (Z/7Z)*, (Z/13Z)* それぞれで 2 の位数は 4, 3, 12
(Z/455Z)* での 2 の位数はその最小公倍数である 12
n がたくさんの素因数を持てば持つほど、また、2 の位数が小さければ小さいほど最初の Z/nZ の分割が多くなるので
わりと納得の結果です。
42:１３２人目の素数さん
18/05/14 11:23:30.91 llu/JFDye
これってどうよ。URLﾘﾝｸ(animaleconomicus.blog106.fc2.com)
43:前786
18/05/15 23:42:53.44 zc4kBs+0.net
証明がちょっと進んだけど
余白が……ではなく時間が足りない。
44:１３２人目の素数さん
18/05/16 00:14:21.05 Ux+htuCY.net
ほう、ちょっとづつだとしても毎日前進してるというのは凄いですな。
アイディアだけでも先行で聞かせてほしい。
45:前786
18/05/16 00:15:54.58 /MdEF5MU.net
とりあえず状況の整理だけ
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 の場合に部分的に予想が証明できた。
46:１３２人目の素数さん
18/05/16 00:22:01.01 Ux+htuCY.net
ほほう、>>786は群論の知識があるのか。
俺にはないorz.
47:１３２人目の素数さん
18/05/16 00:24:30.33 Ux+htuCY.net
でもまあ着実に外堀が埋まっていってる感じですかね？
48:１３２人目の素数さん
18/05/16 20:58:53.07 Ux+htuCY.net
群論的な観点でいえば合成数の場合を素数の場合に帰着する望みはありそうなんですか？
49:前786
18/05/16 23:09:35.30 /MdEF5MU.net
>>47
n と m が互いに素であるとき Z/mnZ は (Z/mZ)×(Z/nZ) に同型なので
何かしら関連付けることはできるかもしれませんが、
完全に帰着させるのは難しそうというのが正直なところ。
これには根拠がありまして、プログラムの出力結果を見ると
例えば n=35 にかかった計算量は
n=5 と n=7 の計算量の合計よりかなり多いということが見て取れます。
そうすると、n=35 を n=5 と n=7 に帰着させるのは苦しいんじゃないかなあと思うわけです。
50:１３２人目の素数さん
18/05/16 23:17:00.63 Ux+htuCY.net
>>48
ふーむそうなのか。
ありがとうございます。
先は長そうですな。
51:前786
18/05/16 23:32:04.61 /MdEF5MU.net
このままだと、場合分けが延々と広がって収拾がつかなくなる、
といういつもの感じになりそうな雰囲気がぷんぷんしますけどね。
とりあえず示せたのはこちら。
定理
>>44において指数が 2 であり、かつ p≡3 (mod 4) のとき、
k=1,2,…,p-1 に対して予想が成り立つ。
証明は後日。
52:１３２人目の素数さん
18/05/16 23:38:41.29 Ux+htuCY.net
mod 4 ですか？ 意外な数字がでてきましたね。
まあ、証明を楽しみに待ちます。
53:１３２人目の素数さん
18/05/22 10:07:26.93 WVNRebn9V
>>51
> mod 4 ですか？ 意外な数字がでてきましたね。
n mod 4 が 3 の場合に帰着するので、わりと順当な話だろうと思われる。
任意の偶数が「２で割りつづけると奇数に到達する」というのも自明。
問題なのは、「任意の奇数を『３倍して１を足す』と、１２で割って８余る偶数」
に到達するという上に向かうルートがあるのだが、
その一番下の奇数の性質とか、ルートの長さとか場所とかの分布が
なかなか追いきれないという点だ。
54:前786
18/05/20 00:54:51.37 Cf9ohYZi.net
途中まで。
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 はλ*(平方数) の形で表せる元全体に等しい。□
55:前786
18/05/20 00:55:45.58 Cf9ohYZi.net
次に (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 を得る。
したがって ⇔ が成り立つ。□
56:前786
18/05/20 00:56:31.04 Cf9ohYZi.net
補題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)
と同値である。□
57:前786
18/05/20 00:58:06.31 Cf9ohYZi.net
あとは方程式 (a)～(d) の解の存在を示せばよい。
とりあえずここまで。
前にもあったけど、こうやって代数方程式に帰着できたのは個人的に面白いと思った。
58:righ1113
18/05/20 03:49:10.15 lv8XOQh3.net
ところで流れと関係ない質問ですが、
プログラムの3のところを5に変えたら、
5x+1問題を論じている事になりますか？
59:前786
18/05/20 09:48:45.09 Cf9ohYZi.net
>>57
なると思います。
60:前786
18/05/20 16:32:50.23 Cf9ohYZi.net
>>55の続き
補題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 通り。
61:前786
18/05/20 16:33:24.36 Cf9ohYZi.net
(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 の場合に予想が成り立つ。
62:前786
18/05/20 16:36:22.12 Cf9ohYZi.net
あ、あと訂正。
>>44で「指数1, mod 3 で 1」の欄に 131 があるけど、
131 は「指数1, mod 3 で 2」の欄でした。
63:１３２人目の素数さん
18/05/20 17:38:06.32 faL44BH0.net
ぬおー複雑すぎてついていくのがしんどいorz
平方数がどうとかいうのは群論でも普通によく使われるテクニックなんですか？
64:前786
18/05/20 18:16:56.14 Cf9ohYZi.net
>>62
群論というより、どちらかというと整数論ですかね。
少なくとも自分はよく使います。
65:１３２人目の素数さん
18/05/20 22:31:52.19 faL44BH0.net
>>1は理解できてる？
基本このスレには3人しかいないから俺がだめなら>>1しかいない。。。
66:righ1113
18/05/21 01:21:10.42 zGYj2oYV.net
>>64
いや～4割ぐらいっすねー
67:１３２人目の素数さん
18/05/21 20:37:31.44 4VRAtjed.net
とりあえず、この場合の平方数というのは
可換体 K の乗法群 K* の部分集合 {x2 | x ∈ K} （直積集合と紛れるおそれのないときには
これを (K*)2 などと表す）の元を平方数や平方元と呼ぶことがある。（wikipediaより）
であってますかね？
68:前786
18/05/21 21:02:18.85 VLLcdro9.net
>>66
あってます。
Z/pZ の場合は「平方剰余」という呼ばれ方をすることが多いですが、
私は「平方数」の方が慣れているのでそうしました。
69:１３２人目の素数さん
18/05/21 21:25:13.58 4VRAtjed.net
誠に申し訳ないが乗法群の説明がwikiじゃよくわからんorz.
むかし学校で習ったような気もするがあまりに昔の話で記憶が霞んでるorz.
とりあえずこのページ見つけたけどこれでいい？
URLﾘﾝｸ(math-note.xyz)
70:前786
18/05/21 21:59:04.76 VLLcdro9.net
>>68
>>53で扱っているものは「環の乗法群」あるいは「体の乗法群」というもので
そこには載ってないですね…
乗法群とは、「積に関して逆元を持つ要素を集めた群」です (群がよく分からなければ集合と読み替えてください)。
Z/nZ の場合、これは 0 から n-1 のうちで n と互いに素な数だけを集めたものになります。
したがって、
Z/pZ の乗法群は {1,2,...,p-1}
Z/3pZ の乗法群は 3 の倍数でも p の倍数でもない元全体の集合
となります。
71:１３２人目の素数さん
18/05/21 22:24:15.94 4VRAtjed.net
>>69
おお、ありがとうございます。
群に関して解説しているお勧めページありましたら教えてください。
72:１３２人目の素数さん
18/05/21 22:54:59.90 4VRAtjed.net
あ～すいません。
群じゃなくて環、体なんですかね？
73:前786
18/05/21 23:20:03.77 VLLcdro9.net
有名ですけどこの辺りとか
物理のかぎしっぽ - 代数学
URLﾘﾝｸ(hooktail.org)
群、環、体について基本的なことが載っています。
Z/nZ の話に絞れば、例えば
Excel VBA 数学教室 - 数学辞典 - 整数論入門講座
URLﾘﾝｸ(excelmath.atelierkobato.com)
この辺りも詳しそうです。
74:前786
18/05/21 23:34:55.13 VLLcdro9.net
ざっと見たところ、上記のサイトには
>>54で用いた直積の話 ((Z/3pZ)* は (Z/3Z)*×(Z/pZ)* に同型) が載ってなさそうです。
探したらこれに載ってました。
URLﾘﾝｸ(nakano.math.gakushuin.ac.jp)
(学習院大学の講義資料)
講義資料一覧はこちらから見られるようです。
URLﾘﾝｸ(nakano.math.gakushuin.ac.jp)
75:１３２人目の素数さん
18/05/21 23:45:47.55 4VRAtjed.net
ありがとうございます。
1から勉強だなこりゃ
76:１３２人目の素数さん
18/05/22 20:15:30.49 GnlOeguJ.net
私が勉強追いつくのは結構時間かかると思うのでスレは自由に進めてくださいねｗ
77:前786
18/05/22 23:49:30.33 kTVPAnQh.net
>>75
まあこちらもそんなに大きな進展はないですけどね。
>>11の②の場合 (n=p、p は 5 以上の素数、Z/pZ で 2 が原始根、p≡1 (mod 3)) で
k=0 だけ抜けてるのをやはり何とかしたいので考え中。
まだ証明はできてませんが、この場合ほとんどの p ではアルゴリズムが C で終わりそうです。
実際、200 以下の出力では n=13 を除いて全ての場合でアルゴリズムが C で終わっています。
78:前786
18/05/23 00:52:33.04 KVhZBaB6.net
一旦理屈をすっ飛ばしますが、
n=p、p は 5 以上の素数、Z/pZ で 2 が原始根、p≡1 (mod 3) で k=0 のとき、
とりあえず以下の方法で検証できることが分かりました。
(1) 縦２マス横 (p-1)/2 マスのマス目を考え、図のように３色で塗り分ける。
URLﾘﾝｸ(i.imgur.com)
(2) Z/pZ における数列 {a[n]} を
a[1]=(2p+1)/3
a[n+1]=4a[n]+1 (n≧2)
で定義し、図のようにマス目に添える。
URLﾘﾝｸ(i.imgur.com)
※ {a[n]} の一般項は ((2p+2)4^(n-1)-1)/3 である。
※ a[n+(p-1)/2] ≡ a[n] (mod p) が成り立ち、周期的な数列となる。
(3) a[i] が Z/pZ で平方数であればその列の下側のマスに印をつける。
そうでなければ上側のマスに印をつける。
URLﾘﾝｸ(i.imgur.com)
(4) ３色とも少なくとも１つのマスに印がついていれば予想が成り立つ。
79:前786
18/05/23 00:56:44.28 KVhZBaB6.net
あ、>>77の(4)は「予想が成り立つ」より「アルゴリズムが C で終わる」の方が適切です。
n=13 の場合、次のような結果になります。
URLﾘﾝｸ(i.imgur.com)
黄色マスに印がつかないので、アルゴリズムは C で終わりません。
80:righ1113
18/05/23 01:21:25.86 1DxWfvsk.net
プログラムでイレギュラーを見つけました。
プログラムの3を19に変えてn=7で、
---
(4) A' の各元 a に対し、3a+1 がどの Bi に属すかを見る。（どの Bi にも属さないこともある）
---
で全ての3a+1が属さないのです。
プログラム上ではオールNothingになります。
詳しい説明は今晩します。
81:righ1113
18/05/23 01:31:18.18 1DxWfvsk.net
正確にはこうです。
プログラムの3を19に変えてn=7で、
---
(4) A' の各元 a に対し、19a+1 がどの Bi に属すかを見る。（どの Bi にも属さないこともある）
---
で全ての19a+1が属さないのです。
プログラム上ではオールNothingになります。
82:１３２人目の素数さん
18/05/23 12:01:38.73 m0d+bsHd.net
整数論関係で盛り上がっているところで申し訳ないのだが、
二進数表記で ON ビットが二個以上連結すると、
上（偶数に向かうシークエンス）というのが、
ON ビット n に対して n - 1 個連続する。
２の倍数を XY 座標の の X に取るとすると、
偶数は、「２で割る」操作のどっかでシークエンスに引っかかる
（つーか、奇数になる）。
コラッツ操作がカオティックな挙動をするというのは、
「３ｎ＋１の結果が奇数でありつづける」（つまり、下位のビットが
ON でありつづける）と、「２で割り続ける」と、「偶数は割り続けると、
どこかで奇数になる」という、周期３のループに引っかかっている
せいではないかという気がしてきた。
「３ｎ＋１」で無限大に発散することはありえない
（メルセンヌ数との関連で、それは自明）。
つーことは、「下位がオンビットの値（奇数）で受けとめきれない」
偶数があるかどうか、みたいな話になりそうな気がする。
83:righ1113
18/05/23 19:18:42.10 l+nV4t+w.net
>>81
> 「３ｎ＋１」で無限大に発散することはありえない
>（メルセンヌ数との関連で、それは自明）。
詳しく知りたいです。
84:１３２人目の素数さん
18/05/23 20:35:47.24 m0d+bsHd.net
>>82
メルセンヌ数（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 のみではないビット列が並んでいる」からだ。
そこに、「三倍して１を足す（ 3n + 1 ）操作」を繰り返すと、「2^p + (2^( p + 2) × q)」の部分に「三倍して２を足す」操作を p 回繰り返すのと同じことになる。
その間、「2^p + (2^( p + 2) × q)」の桁数が増えた結果、そのビット列に p 個以上の 1 が現れて、元の p よりも数が増えると、これは発散してしまう恐れがある。
実際に、それらしい例はある。 31 の場合、31 - 47 - 71 - 107 - 161 の列から 319 - 479 - 719 - 1079 - 1619 - 2029 を経る場合がある。
ただ、これが「無限に連鎖するか？」という話になると、「メルセンヌ素数は無限に存在するか？」みたいな話になるので、「今のところ、わからん」と言うしかない。
とりあえず、「すべての自然数が、コラッツ操作によって p と q の網（木）に引っかかるか？」を考えている。
ただ、「三倍して１を足す（ 3n + 1 ）操作」の回数は、 p を超えることはないことが判っている。
85:１３２人目の素数さん
18/05/23 20:40:42.01 m0d+bsHd.net
× > そのビット列に p 個以上の 1 が現れて
〇 > そのビット列に p 個以上連続した 1 が現れて
86:１３２人目の素数さん
18/05/23 20:43:34.27 m0d+bsHd.net
あかん。
>> 4 で割って 3 余る奇数（n mod 4 = 3）
は余計だった。すまぬ。
87:righ1113
18/05/23 21:07:48.22 l+nV4t+w.net
>>83
なるほど。下位の連続した1のビットに注目しているのですね。
自分もコラッツパターンで考えていました。
URLﾘﾝｸ(d.hatena.ne.jp)
88:１３２人目の素数さん
18/05/23 21:36:38.24 amwAZ2U3.net
お、新人さんかい？
89:前786
18/05/24 00:50:30.75 COzmyM7A.net
>>79>>80
これ気になるんで詳細待ってます。
正常に動いていれば Nothing 以外も出てくるはずですが…
90:righ1113
18/05/24 01:01:12.08 BvJJodRF.net
>>88
すいません今晩はムリでした(>_<)
91:前786
18/05/24 01:22:11.96 COzmyM7A.net
>>89
さいですか。
まあ、気長に待ちますんでお気になさらず。
92:１３２人目の素数さん
18/05/24 10:37:42.13 hntPmxCh.net
また通りすがりのプログラマが覗きにきました。お邪魔します。
「奇数 →（奇数 →）６で割って２余る偶数 → 奇数」
というループに乗っていないのは１だけ。
「奇数 → 偶数」というルートを通らないのは２の冪乗数だけ。
それ以外で、“ループ�
93:ﾅはない”「奇数 → ６で割って２余る偶数 → 奇数」という “ルート”に乗って“いる”のは２の冪乗のうち「６で割って２余る偶数」だけ。 つまり、ここから先は、上記の条件に引っかからない「６で割って２余る偶数」と 「奇数」だけを考えればいい。 ここからは、単純に上記の条件に引っかからない「６で割って２余る偶数」と 「奇数」だけを考えればいいような気がする。 このあたりから始めて、「コラッツ操作を根っこのほうから逆に辿って、 枝がどう伸びているか」を逆に辿ってみようとしているのだが、 辿ってみた結果を どう整理したらいいのかが、正直わからん。484 と 485 とか、 変なところでニアピンしてる奴がいるんだよなぁ（どっちも３ステップ後に 182 を通る）。 これは三次元表示とかを考えたほうがいいのかね？ 映像として見ることで、 なんかしらの法則性が見えてくるということも あるわけだし。
94:righ1113
18/05/24 17:50:33.60 Ht7/ViD0.net
>>91
「6で割って2余る数 」か「奇数 」かたっぽだけ調べれば良いような気がします。
画像表示はカオティックなものしか得られずにう～ん……という感じです。
95:１３２人目の素数さん
18/05/24 19:31:53.90 hntPmxCh.net
>>92
確かにカオスって「断面」で見るからそういう感じはするんだよね orz
つーても一次元で見ても傾向がわからんような気が。
96:righ1113
18/05/24 19:35:11.39 x3TjQ3yB.net
>>90
お待たせしました。プログラムとログです。
URLﾘﾝｸ(github.com)
19x+1でn=7は、
A : [[0],[1,2,4],[3,5,6]]
です。最初の二つは問題ないです。
最後がC'でオールNothingとなり、C''でカラになります。ここで止めました。
どこかプログラムがバグってるんですかね。
自分はてっきり、これが無限走行へ至る道かと思ったのですが。
97:１３２人目の素数さん
18/05/24 19:40:13.49 hntPmxCh.net
漏れは航空宇宙工学科出身なので
「可視化」っつーのは重要だとは思ってるんだけど、
カオス系のように「見えたからって、なんも解決せん」とか、
f^-1 ゆらぎのように「実際に計測してみたら、単なる
対数分布だった」（ラーメンの汁に浮いてる油滴なんかがそう）とか、
ハズレが多いのは分かってるんだが ……
なんかしら別視点に期待する部分は あると思われ。
98:前786
18/05/24 20:30:26.05 COzmyM7A.net
>>94
>>88は B の段階で全て Nothing になったのだと勘違いしていました
ちゃんと見てみます。
99:righ1113
18/05/24 20:34:17.94 x3TjQ3yB.net
ああすみません。
>>80の書き方が悪かったです。
100:１３２人目の素数さん
18/05/24 20:52:34.74 c3neDLsf.net
可視化はいいけどどうやって可視化するかはアイディアあんのか？
３次元表示だけじゃ具体性に乏しい。
101:前786
18/05/24 21:45:42.25 COzmyM7A.net
>>94
とりあえずこの出力結果は間違ってなさそうです。
詳細は後ほど。
102:righ1113
18/05/24 22:08:44.37 x3TjQ3yB.net
おお~~
103:１３２人目の素数さん
18/05/24 22:53:57.29 c3neDLsf.net
>>99
新展開ですか？
104:前786
18/05/25 00:00:11.96 cjcsGDRA.net
出力結果が正しいことの説明もしたいところですが、その前に別の話を。
まず一応誤解のないように言っておきますが、
この結果から即座に「コラッツ予想の 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 で考えたものが私の予想です。
105:前786
18/05/25 00:01:05.77 cjcsGDRA.net
で、お気づきかもしれませんが、現在のアルゴリズムはコラッツ逆操作しか考えていません。
これが「コラッツ予想の 19n+1 版は成り立たない」とは結論づけらない理由です。
（コラッツ逆操作しか考えていない理由は、これだけでもさしあたってうまくいっていたことと、コラッツ操作まで考えると一気に複雑さが増すことということです）
（逆操作だけというのはかなり制限しているように見えますが、実はそれほどでもありません。また今度話します。）
今回の結果についてですが、
まず出力結果にある C' は「mod 133(=7*19) で 2 のべきである数の集合」になります。（これもまた今度）
このことから今回の結果を次のように述べることができます。
定理
コラッツ予想の 19n+1 版を考える。
このとき、mod 133 で 2 のべきである数からコラッツ逆操作を繰り返しても、
mod 133 で 2 のべきである数以外は得られない。
これはちょっと予想外でした。
3n+1 では今までコラッツ逆操作だけでうまくいってたけど、
そのうちコラッツ操作も考えなきゃいけなくなるかもしれない…
106:１３２人目の素数さん
18/05/25 05:24:49.37 FB8NYZZI.net
>>98
n が 127 以下については、手で描いてみた（A4 の 5mm 方眼紙四枚とか）。
以前誰かが書いてたように、「場合分けが面倒臭いことに
なって手に負えなくなる」という感じのある錯綜したケース
（確かに127 以下はけっこうややこしい）を脱して
ある程度規則性が見えてくるのは、ここより先
（255 とか 1023 とか 2047 とか）らしいんだよね。
そうすると、もう手描きだと追いつかなくなるのと、関係が錯綜して
見づらくなる（つーか、局所的な関係はわかるんだが、全体像が
把握できなくなる）ので、「２で割る」「３n + 1 して 2 で割る」
「その数の大きさ」みたいに次元を分けて空間的に散らばらせて、
ぐるっと見渡せれば何かわかるかな、と。
乱数の品質とかも、二次元空間にマッピングすると「あ、この
アルゴリズムだと、品質悪いな」とか判ったりするじゃん？
あんな感じ。
107:righ1113
18/05/25 22:16:46.77 cO+AwSH2.net
>>102-103
う～む、そんなに単純ではないのですね。
ちなみに、
コラッツ予想の19n+1版において
7で割って
・0,1,2,4余る数→全ての木に現れる
・3,5,6余る数→一部の木にしか現れない
これは言えるのでしょうか？
108:前786
18/05/25 23:19:00.95 cjcsGDRA.net
>>105
それが言えちゃうとまさに「コラッツ予想の 19n+1 版は成り立たない」になっちゃいます。
・0,1,2,4余る数→全ての木に現れる
これはプログラムによって証明できていますが、
・3,5,6余る数→一部の木にしか現れない
こっちは証明できていません。
109:righ1113
18/05/25 23:32:11.70 cO+AwSH2.net
なるほど～失礼しましたー
110:１３２人目の素数さん
18/05/25 23:45:29.86 IeZ+TUSP.net
しかし実際問題として19n+1版の反例というのはそんなに簡単には見つからないものなんですか？
111:righ1113
18/05/26 00:04:16.67 n+Y56waB.net
>>108
bn+1版でbが大きくなると、遷移の上昇幅も大きくなるから、無限大に発散する可能性は高くなると思います。
適当にプログラムを走らせて、どんどん大きくなっていくようなら、この初期値は無限大に発散する可能性が高い、とは言えると思います。
「無限大に発散する!」という証明はかなり難しいと思います。
112:前786
18/05/26 00:08:59.09 PVjl5sK1.net
>>108
どう�
113:ﾅしょうね…あまり考えたことはないので、難易度も分かりません。
114:前786
18/05/26 00:55:24.03 PVjl5sK1.net
「コラッツ逆操作だけ」というのがそれほど強い制限でないという話。
まず、コラッツ逆操作では操作 3 を行うか操作 4 を行うかで分岐が起こりますが、
コラッツ操作では分岐は起きません。
なので、例えばある数にコラッツ逆操作を行ってからコラッツ操作を行うと、元の数に戻ることになります。
予想を証明するには、
「ある数 a からコラッツ操作、コラッツ逆操作を繰り返してある数 b にたどり着けるか」
を考える必要がありますが、上記のことから
「ある数 a から何度かコラッツ操作を行い、その後何度かコラッツ逆操作を行うことである数 b にたどり着けるか」
という道筋だけ考えればいいということになります。
そうすると、コラッツ逆操作だけを考えるというのは大体、操作の後半だけを考えるということになります。
これが強い制限と思うかどうかは人それぞれですが、
実際にこれまでは多くの場合にうまくいっているので、大した制限じゃないのだろうと私は思っています。
115:前786
18/05/26 00:55:45.59 PVjl5sK1.net
ちなみにこれまで「コラッツ操作」の方を全く考えていない訳ではなく、
前スレ>>787の
命題
T を木とし、k=1 or 2 とする。
このとき、ある a∈T が存在して a≡k (mod 3) となる。
や、前スレ>>851の
補題
n を 5 以上の奇数とする。
任意の木には、3 の倍数でも n の倍数でもない数が含まれる。
（元々は奇数でなく素数としていたが、全く同じ証明で奇数の場合も示せる）
ではコラッツ操作を用いています。
116:righ1113
18/05/26 05:32:28.98 c0tJyFtX.net
通常のコラッツ予想3x+1ですが、
①プログラムが無限走行→オールNothing出る
(Cを繰り返すと集合が1つになる事が使えないか)
②オールNothing出ない→プログラムは停止
③全てのnでオールNothing出ない(難しい?)
④全てのnでプログラムは停止する
というのを考えたのですが、
実際証明するとなると難しいですかね。
117:１３２人目の素数さん
18/05/26 06:33:58.67 SzRdqnm/.net
また邪魔なプログラマが通りますよ
コラッツ逆問題（３ｎ＋１版。「1 から出発して、すべての自然数に
到達できるか」）について、「（有限な）すべての偶数は、２で割り続ける
ことによって奇数に帰着するので、奇数についてだけ証明できれば足りる」
のは確か。
逆コラッツ操作は、
１）ｎを２倍する。
２）ｎを二倍して１を引いたものが３で割りきれるなら、それ（２ｎ－１）を
３で割る。
が可能。
で、このとき、「ｎが３で割りきれる場合は、（１）の操作によって
『ｎを二倍して１を引いたものが３で割りきれる数』が出てこない」ことが
判っていて、ｎの偶奇によらず（１）の操作の結果は偶数になるので、けっきょく
奇数は出てこないことがわかる。
（２）に対応する正のコラッツ操作は、結果的に「ｎを二倍して１を引いたものが
３で割りきれない数」に「２ｎ＋１」操作を繰り返して「６で割って２余る偶数」に
至る“縦のルート”（有限長の上下のルート）を描くことであり、このとき（ｎの
偶奇によらず）３の倍数が出てきたときは逆コラッツ操作の
（１）（“右へ向かうルート”。こちらは際限なく右に延長できる）は
考慮しなくていい。
なお、“縦のルート”は、最下位ビットが「２個以上の連続するオンビット」である
状態と関連している。
この制約条件のもとで、「１を出発点として、すべての奇数に到達できるか？」が、
コラッツの逆問題となる。
で、「最下位のオンビットが連続しない」数は、「４で割って１余るｎ」であり、
それが正のコラッツ操作（２）によって「６で割って２になる数」に変換されるはず
だから、それを満たす数について考えればいい ― ような気がする。
だけど、コラッツ予想に関する議論で「mod 12」って話が出てきたのを
見た記憶がオレにはないんだよな (-_-!)。
これって、オレが なにか盛大な勘違いをしているってぇコトなのか？
118:righ1113
18/05/26 15:26:37.54 R0apbE/z.net
>>114
>「ｎを二倍して１を引いたものが３で割りきれない数」に「２ｎ＋１」操作を繰り返して「６で割って２余る偶数」に至る“縦のルート”
ここが分かりません。
具体的な一連の数とかありますか?
119:１３２人目の素数さん
18/05/26 17:07:34.51 SzRdqnm/.net
>>115
とりあえずこんな感じかな？
120: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 詳細は のちほど。
121:１３２人目の素数さん
18/05/26 17:11:05.80 SzRdqnm/.net
つーか、「コラッツ操作」ということを考えたら、
「->」じゃなくて「<-」のほうが判りやすかったかも。
あ、「3n + 1」じゃなくて、「(3n + 1) / 2」で
表示してるのは、このスレを見てるような人だったら
察してくれるよね？
122:１３２人目の素数さん
18/05/26 17:16:10.29 SzRdqnm/.net
言うまでもないけど、
“☆”がついている値は、
「３の倍数なので、2 の冪乗を掛けても
『2n - 1 が 3 で割りきれる数にならんので、
下に延びる枝（3n + 1 操作の逆操作）がない枝』」
っちゅーことです。
123:righ1113
18/05/26 17:54:29.76 R0apbE/z.net
>>116-118
>>114は大体理解できました。mod12は分かりません。
> で、「最下位のオンビットが連続しない」数は、「４で割って１余るｎ」であり、
>それが正のコラッツ操作（２）によって「６で割って２になる数」に変換されるはず
>だから、それを満たす数について考えればいい >― ような気がする。
例えば17を見ると、4で割って1余る。
コラッツ操作(2)で26になって、6で割って2余る。
しかし17を2倍して1引いた数が3で割りきれてしまう。
コラッツ操作(2)に違反していると思うのだけど、こういう数はどう処理するの?
124:１３２人目の素数さん
18/05/26 18:02:39.81 SzRdqnm/.net
>>115
ごめん。
>（２）に対応する正のコラッツ操作は、結果的に「ｎを二倍して１を引いたものが
３で割りきれない数」に「２ｎ＋１」操作を繰り返して「６で割って２余る偶数」に
至る“縦のルート”（有限長の上下のルート）を描くことであり、
っつーのは、
>（２）に対応する正のコラッツ操作は、結果的に「ｎを二倍して１を引いたものが
３で割りきれない数」に「（３ｎ＋１）／ 2」という操作（←ここ重要）を繰り返して「６で割って２余る偶数」に
至る“縦のルート”（有限長の上下のルート）を描くことであり、
という意味だ。
とりあえずツッコミは歓迎なのだが、いまは遠山 啓先生の『初等整数論』で
理論武装中なので、殲滅的攻撃は勘弁してくれいm(_ _)m。
125:righ1113
18/05/26 18:19:59.67 R0apbE/z.net
>>120
すみません、つい熱くなってしまって……
126:１３２人目の素数さん
18/05/26 18:20:36.68 SzRdqnm/.net
>>119
> 例えば17を見ると、4で割って1余る。
> コラッツ操作(2)で26になって、6で割って2余る。
> しかし17を2倍して1引いた数が3で割りきれてしまう。
> コラッツ操作(2)に違反していると思うのだけど、こういう数はどう処理するの?
典型的な例を挙げたので分かりにくかったと思うが、
(26 ->)17 -> 11 -> 7 というのは確かにあって、
「必ず 3 の倍数で終わる」とかいう話ではないのだ。
つーか、「どのあたりで齟齬が生じているか」について、
数学屋さんと電算屋の間では分かりにくいのだ。
「素数には必ず原始根がある」というのは納得するにせよ、
「原始根って複数あるんじゃないの？ そのあたりはどうなの」とか、
「そもそも『指数』という概念がよくわからん」とか、
「QRコードとか乱数生成とか、リクツは判らんでもないけど、
原始多項式うんぬんとか言われても、正直な話、小分かりがせんのよ」
みたいな感想がある。
そもそも「Z/pZ」っつーのが、「演算を定義せんと意味がねぇ」みたいな
話があって、よくわからん（加法なのか乗法なのかとか）。
せっかく大勢の人が見てくれているのだから、「数学的に厳密な記述」
ではない「わかりやすい説明」（まぁ、「『分かりやすい説明』は、
嘘の温床だ」という意見は確かにあるのだが）っつーのも
試みてくれんか。このスレで（見ているだけの奴もいるし、
書いている奴もいるわけだが）“解っている” 人間も
少なかろうと思うので。
127:１３２人目の素数さん
18/05/26 18:35:17.86 SzRdqnm/.net
>> 119
> すみません、つい熱くなってしまって……
いや、熱くなるのはまったく問題ないので、「こちらこそ、数学の門外漢が
半煮えの議論を持ち出してすまん m(_ _)m」とお詫びしたい。
とはいえ、実験数学が未解決問題の解決に貢献することもあるし、
「素人目線からの、視覚化だのなんだの」が有効なことが あるのだ。
数学屋さんには数式という武器があり、
電算屋にはプログラミング言語という武器がある。
（個人的に Wolfram は気に入らないが）Mathematica みたいに
その間を繋ぐツールもある。
とりあえず「共通の土俵」っつーのを用意したいと思う。
128:１３２人目の素数さん
18/05/26 19:04:19.46 mODZs90x.net
具体的にプログラム言語は何使えんのよ？
129:１３２人目の素数さん
18/05/26 19:04:56.28 mODZs90x.net
ちなみに>>1はhaskell使いらしい
130:１３２人目の素数さん
18/05/26 19:52:05.47 SzRdqnm/.net
>>124
> 具体的にプログラム言語は何使えんのよ？
わしゃぁのう、年寄りじゃけん、本当はアセンブラしか解らんのじゃ。
じゃけんども、C とか LISP とかは、理屈がよう分るんじゃ。
Pascal は、P-system があったんで、Java んような「中間言語」とか
「仮想マシン」っちゅーたらコンセプトは分らんでもないんじゃ。
年取ったけん、IDE がなけりゃプログラムなんぞ書けんように
なってしもうた。
そんなわけで、ようやく Java を使ってなんとかプログラムを
書いとるんじゃ。
ごめんつかぁさい。
131:１３２人目の素数さん
18/05/26 20:15:39.62 mODZs90x.net
中身のある話振ってくれるなら歓迎するけどね。
アイディアがあるなら具体的に頼む。
132:１３２人目の素数さん
18/05/26 20:56:17.99 SzRdqnm/.net
>>127
> アイディアがあるなら具体的に頼む。
ありがとう。
生煮えなので申し訳ないのだが、右（２の冪乗）から来る
値は、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。
133:１３２人目の素数さん
18/05/26 22:12:44.62 mODZs90x.net
逆にxn+1問題で無限大に発散する場合もあるxを探すというのは？
134:１３２人目の素数さん
18/05/26 22:44:42.03 9vYDmViG.net
コラッツ予想をセルオートマトンで可視化する事を試してみました。
URLﾘﾝｸ(dotup.org)
キーは3nplus1です。
大まかに４つのパターンを図示してみました。
1）完全にランダムなパターン
2）1のビットが長く続くパターン(2^n-1)
3）最下位ビットと最上位ビットの間が0のビットで隔てられてるパターン(2^n+1)
4）1のビットが長く続き、さらに離れて最上位ビットが存在するパターン((2^n+1)*2^m-1)
最下位ビットが0の行は赤に塗ってあります。
プログラムに間違いがあればすいませんが、結構興味深い遷移がみられました。
135:１３２人目の素数さん
18/05/26 23:12:06.85 9vYDmViG.net
>130 まとめ
○コラッツ操作を行った際に操作前よりも数が増えるのは最下位ビットから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)となる。
とりあえず挙げられるのはこんなところでしょうか。
既知の情報でしたら申し訳ない。
136:１３２人目の素数さん
18/05/26 23:26:44.26 mODZs90x.net
整数をビット列とみなして考えるのは>>1がかなりやってたから>>1の意見を聞きたいね。
まあ、この程度の成果では驚きはないだろうけど。
137:１３２人目の素数さん
18/05/26 23:31:56.87 mODZs90x.net
結構きれいな絵だけどきれいなものだけ抜き出したの？
よくわからんが全部きれいになるならもしかして凄いのかな？
138:１３２人目の素数さん
18/05/27 00:11:19.66 PUTG2O+S.net
>133
綺麗なパターンが出る値を選んでます。
大抵は増えて減ってを繰り返すパターンになると思いますが、その出現に規則性が見られるように思えます。
まぁ勘違いかもしれないんですが orz
139:１３２人目の素数さん
18/05/27 07:33:04.20 hLMSuDSm.net
>>131
「最下位ビットから2ビット以上1が連続した場合」については、
以下のようなことを考えたことがある。
「ここで、新たな操作を追加する。
（３）n' = 3n + 2
である。
たとえば "11101" のように、左に '1' が二個以上連続した部分（m 個）が
あるとする。これを、m - 1 個の '1' と '1' に分ける。 "11101" だったら
"11" と "101" だ。このとき、"11101" は、"**"と「 "101" に（３）の操作を
二回施した結果」で表される。
"11" -> "*" + "101"
"111" -> "**" + "10001"
"1101" -> "*" + "10001"
"1111" -> "***" + "101011"
"11001" -> "*" + "10111"」
その他の悪戦苦闘っぷりは
URLﾘﾝｸ(animaleconomicus.blog106.fc2.com)
を参照されたい。
140:１３２人目の素数さん
18/05/27 08:58:45.44 hLMSuDSm.net
逆コラッツ操作を行なうプログラムの中で、ずっと
「ｎを二倍して１を引いたものが３で割りきれたら３で割る」
とかいうロジックを使っていたのだが、よく考えたら
「ｎを３で割って２余る」（n ≡ 2(mod 3)）でよかったことに、
いま気づいた。
2*(m + 2) - 1 = 2m + 4 - 1 = 2m + 3
なんだから、3|m（「m が 3 で割切れる」あるいは「m は 3 の倍数」。
遠山 啓さんの『初等整数論』のスタイルだと「3)m」）なら
当たりまえじゃん（だから数学は苦手なんだと(ry）。
そうすると、
１）ｎを３で割って２余るなら、二倍して１を引いてから２で割る。（それが終わったら、次にｎを二倍して右を探す）
２）ｎを３で割って１余るなら、右に逃げる（ｎを二倍して右を探す）。
３）ｎが３で割りきれるなら、下には行けないし右側にも奇数へ向かう枝が出ないので、ひとつ前（根に近い数）に戻る。
という操作で再帰をかければ、「逆コラッツ操作で出てくる奇数の木を探索する」ことができるはずだ。
こうなったら奇数偶数関係ねぇじゃん。orz
141:１３２人目の素数さん
18/05/27 13:50:43.81 OB+BVTS7.net
個人的最近色々とデータをいじっているんだが、1になるまでの回数にちょっとした発見があるんだけど需要ある??
142:１３２人目の素数さん
18/05/27 13:53:03.11 OB+BVTS7.net
あとは逆コラッツとフィボナッチの関連性やn次のコラッツ、コラッツに群の導入などなど
143:righ1113
18/05/27 14:30:36.56 TGwE04e6.net
>>130-131
残念だけど目新しい情報はないかなあ。
144:１３２人目の素数さん
18/05/27 17:28:34.65 hLMSuDSm.net
>>137
> 個人的最近色々とデータをいじっているんだが、1になるまでの回数に
> ちょっとした発見があるんだけど需要ある??
>>138
> あとは逆コラッツとフィボナッチの関連性や、n 次のコラッツ、コラッツに群の
> 導入などなど
ここは、たぶん「『需要ある??』とか、つまんねぇ遠慮なんかしてるんじゃねぇ！ さっさと晒せよ！」
…… っつースレですから。燃料を投下していただければ、いくらでも。
145:１３２人目の素数さん
18/05/27 19:19:29.97 Eccfjv+j.net
スレがにぎわい始めましたね。
あとは>>786の議論についていけるレベルの人が来てくれればいい感じなのですが。
146:１３２人目の素数さん
18/05/27 19:52:38.57 hLMSuDSm.net
>> 139
> あとは（前スレの）＞＞786の議論についていけるレベルの人が来てくれればいい感じなのですが。
つーても、数学板は敷居が高いのよ。
前スレの ＞＞8 の
> 最初に偶数はアウト（１に収束）
> ４の倍数になったらアウト
っつーのも、
×「最初に偶数はアウト」
〇「最初に２の冪乗数はアウト」（つーか、２で割り続ければ奇数に帰着するので、
奇数について証明できればオッケー。てなワケで「４の倍数になったらアウト」と
いうのも、ここに帰着）
とかいったツッコミ（つーか、解説）を誰かしてくれよ、みたいな話にはなる。
むしろ、素人目線の解説を丁寧に してくれるヒトがいてくれると、もっと盛り上がる
ような気がするのだが。
147:１３２人目の素数さん
18/05/27 21:51:55.33 Lbd03fNz.net
藤林丈司
148:前786
18/05/27 22:57:17.76 oX99EjGQ.net
なんだか盛り上がってますが
とりあえず>>94の出力が正しいことの説明がやっと書けそうなので、投下してから見ます。
149:前786
18/05/28 00:37:34.73 juv57CZY.net
頭の中では図と数式だけしかないから大したことない議論に思えるけど
ちゃんと書こうとするとどうも長くなってしまう…
>>94の出力が正しいことの説明。
Z/nZ を図で表すイメージを導入します。
まず n が素数のときは、アルゴリズム (1) のようにグループ分けし、
URLﾘﾝｸ(i.imgur.com)
図のように 2 倍すると右に 1 マス進むように数を並べます。
各グループの左端と右端は繋がっているイメージです。
n が素数べきの場合も同様です。
さらに一般の n でも同様の表現が可能ですが、ここでは別の表現を導入します。
p,q を相異なる素数とするとき、Z/pqZ は
Z/pZ を横軸、Z/qZ を縦軸にとった二次元配列で表せます。
URLﾘﾝｸ(i.imgur.com)
「Z/pqZ は (Z/pZ)×(Z/qZ) と同型」というのはこのことを表します。
例えば下図の赤マスは
URLﾘﾝｸ(i.imgur.com)
mod 7 で 4、mod 3 で 2 であるような数、すなわち 11 を表します。
Z/pqZ の図で数を 2 倍すると、右上のマスに移ります。
ただし、各ブロックで左右の端、上下の端はそれぞれつながっています。
URLﾘﾝｸ(i.imgur.com)
図は一部のみ示していますが、どの矢印も 2 倍を表しています。
150:前786
18/05/28 00:38:11.51 juv57CZY.net
ここから>>94の出力の話。
19n+1 版で、プログラムに 7 を入力して、A'={3,5,6} とした状況を考えます。
B は Z/133Z において、
「 19 の倍数でも 7 の倍数でもなく、mod 7 で 3,5,6 出ない数」
を考えるので、Z/133Z の下図の部分だけを見れば十分です。
URLﾘﾝｸ(i.imgur.com)
グループ分けを考えると、2 倍すると右上に進むことから
図のように 3 つのグループに分かれます。
URLﾘﾝｸ(i.imgur.com)
縦のマス数 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 は図の位置になります。
URLﾘﾝｸ(i.imgur.com)
よって、緑グループのみ得られます。
151:前786
18/05/28 00:38:52.08 juv57CZY.net
次の C は、Z/(7・19^2)Z において下図の部分を考えることになります
URLﾘﾝｸ(i.imgur.com)
縦は 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 での議論と全く同じになり、黄グループの数に対応しないことが分かります。
したがって、出力は>>94の通りになります。
152:１３２人目の素数さん
18/05/28 06:02:47.38 DIMEHMYY.net
>>131 と >>134 から、なんとなく証明への道筋らしきものが見えてきた。
もちろん“道筋らしきもの”なので、完璧な証明に到達できるかどうかは別の話なのだが。
まず、ごく初歩的な話だが、「メルセンヌ数」の話をしておく。「メルセンヌ数」を「メルセンンヌ素数」だと思っているような人は
数学板にはいないだろうが、「素数であるメルセンヌ数」が「メルセンヌ素数」で
あって、メルセンヌ数は単なる「2^n - 1」の形をした数である。
メルセンヌ数が素数であるかどうかは「リュカ検定（ルーカス・テスト）」に
よって比較的効率よく行えるので、「メルセンヌ素数は無限に存在するか？」
「（偶数の）完全数は無限に」という問題と関連して、コンピュータによる
探索が行なわれている。そうやって見つかった素数は桁数が大きいので
「現在知られている最大の素数」みたいな形で話題になる。
つぎに、任意の有限な数 n をビット列で表したときの、最初のオンビットから
最後のオンビットまでの部分を、“コラッツむし”と呼ぶ。
153:１３２人目の素数さん
18/05/28 06:04:45.60 DIMEHMYY.net
４で割って１余る（n ≡ 1(mod 3)）コラッツむし以外のコラッツむしは、
下位に「２個以上連続したオンビット部分」を持っている。ここで、m 個並んだ
オンビットがあるとして、そのうちの下位側の m - 1 個のビットを
「メルセンヌ部分」、残りを「本体」とする。このとき、本体部分に m - 1 回の
「3n + 2」操作を行なったものが、コラッツむしの“真の体長”だと
思うことにしよう。
つまり、n が メルセンヌ部分を持っているときは、メルセンヌむしは
“縮んでいる”わけだ。
3n + 1 操作を受けた“伸びた”
154:コラッツむしの下位側には、0（二進数表記。 オフビット）が現れる。ただし、任意個の 0 は“ないのと一緒”なので、 コラッツむしの体長には含まれない。 そこで、「コラッツ予想が正しいかどうか？」は、「コラッツむしの“真の体長”が 際限なく伸びてゆく場合があるか？」という問題に帰着する。 そうなると、本体部分は「４で割って１余る素数」だ。これに 3n + 1 操作を 行なったときに、メルセンヌ部分がどう表れるかという話になる。この メルセンヌ部分が際限なく表れると、コラッツむしの真の体長が伸びて、 メルセンヌ予想が破綻する。
155:１３２人目の素数さん
18/05/28 06:06:43.64 DIMEHMYY.net
じゃあ、「『メルセンヌ部分を持たないコラッツむし』が『メルセンヌ部分を
持つコラッツむし』に変態する頻度と、変態後の“真の体長”の変化は、
どのようなものか？」という話になる。
“真の体長”が伸びる可能性があるとすれば、それは操作 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・２・１・２ と
変わる。
つまるところ、「真の体長を伸ばすようなメルセンヌ部分が、どれだけ
出てくるか？」という話になる。
「山よりでかい猪は出ない」わけで、真の体長よりも“長い”メルセンヌ部分が
出ることはない。これを踏まえて、「コラッツむしの真の体長が無限に伸びる
ことがあるのか？」という話になる。このあたりが mod 3 と mod 4 の
絡み合いで組合せによって解決できて、「伸びるにしても限度がある」ことが
示されれば、メルセンヌ予想は肯定的に解かれたことになる。
こう考えると わりと単純な話なので、数学の素人でも手を出しやすいような気が
する。もっとも、コラッツ問題自体が「素人にも手をだしやすいが、素人の手には
負えない」問題なんだから、解けるかどうかはまた別の問題なのだが。
156:１３２人目の素数さん
18/05/28 08:14:16.23 DIMEHMYY.net
一応、まとめてみる。
自然数 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 に『三倍して２を足す』操作を p 回繰り返した結果に
コラッツ操作を施すことで、どれほどの桁数（これを n とする）になり、
最下位に何桁（これを m とする）のメルセンヌ数が出てくるか？」を
考える（m < n であることに注意）。
m と n を p と q の関数で表して、 n - m が q - 1 よりもどんどん大きく
なっていったら、コラッツ予想は「はずれ」だということになる。
おそらく、最悪のケースで見積もると、“爆発”（無限大に発散）すると思う。
そうでなかったら、コラッツ問題はとっくに解決しているはずだ。
だから、相当に ややこしいテクニックを駆使して「最悪のケース」を避けて
「無限大には発散しない」ことが示せれば、コラッツ予想は肯定的に証明される
ことになる。
そんなにうまくゆくとも思えないし、可能だとしても相当に苦労するだろうとは
思うのだが、方向性としては ちょっと新しいように思うので、「難しい」とか
「ダメっぽい」とか「ここから先で行き詰まった」くらいの実績は残しておいても
いいと思う。
コラッツ予想に関する「やってみたけどダメだった」的な論文というのは
山ほどあるのだから、いまさら何本かのクズ論文が増えたところで
文句を言う奴もおるまい。
157:128
18/05/28 08:25:18.74 /SyHFjrG.net
>139
既知の情報だったようですね。失礼いたしました
>148
何かしらのお役に立てたのなら幸いです。
158:１３２人目の素数さん
18/05/28 09:44:13.47 DIMEHMYY.net
>>152 ＞＞128
> 既知の情報だったようですね。失礼いたしました
いやいや、２ちゃん（今は「５ちゃん」だが）でガイシュツは恥ではない。
お気にならさず。
> 何かしらのお役に立てたのなら幸いです。
本当に役に立った。ありがとう m(_ _)m
ついでながら、>>151 の
> 2^q - 3 は、2 < q のときに、二進数で q - 1 桁になる。
というのは、「５以上の４で割って１余る奇数」のうち、いちばん
みっしりビットが詰まったやつのことである。
このあたりのコンセプトの整理には、本スレに参加している諸氏の意見が
非常に役立った。併せて感謝申し上げる。ありがとうm(_ _)m
159:１３２人目の素数さん
18/05/28 12:54:56.22 DIMEHMYY.net
ようやく前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」に関してツブしてゆこう、という話ではないかと思う。
オレは何かヘンなことを言っていると思ったら、ツッコミを入れてほしい。歓迎する。
160:前786
18/05/28 15:03:52.79 juv57CZY.net
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} に分ける、というような操作に関しての発言だと思いますが、
これを表現したければ「軌道」と言うのが適切かと思います（群論の言葉です）。
161:前786
18/05/28 15:04:43.97 juv57CZY.net
2 に注目していることについては、
例えば次のような問題を考えれば納得できると思います。
問. どんな自然数からでも、コラッツ操作とコラッツ逆操作を繰り返すことで 9 の倍数に到達できるか？
162:１３２人目の素数さん
18/05/28 15:27:05.72 DIMEHMYY.net
スレの流れからいうと不規則発言なので、「そういうコトを言っている香具師がいる」
くらいに思ってほしい。
なんとなく問題の本質が見えてきたような気がするので、「コラッツ予想」
「コラッツ問題」に関して「他の研究者は、どんなアプローチを取っているんだろうか？」と
思って検索してみた。
そうすると、「3n + 1 問題」の 3 を「一般の k に拡張したときに」とかいう話が
�
163:ｽいんだよね。 「逃げちゃダメだ、逃げちゃダメだ、逃げちゃダメだ」と思う。そんなもん、 「3n + 1」を解決してから考えろ、と思う。 mod k からアプローチするのは、基本的に“あり”だと思う。だけど整数論 （群とか環とか体とか）に関していうと、あんまり道具としては使いやすくないので 、「果たして有効だろうか？」と思う。まぁ、数学の素人が言う こったから、 「ふぅーん、あんたはそう思うのね？」くらいの感じで聞き流してくれても まったく問題がないのだが。 だいたい、「数学」っつーのは“無限”を相手にすることが多い。「実用的な範囲で、 どれくらい抑え込めるのか？」っつーのは、どっちかっていうと有限組合せ数学とか の範囲の仕事なのだ。だから、純粋数学畑の人はあんまり興味を持たないと思うし、 数式処理システムとか実験数学とかいったものとかとは距離を置きたいと思うのが 当然だと思う。 あとは「整数論方面のほうからのアプローチが どこまで通じるか」という期待が あるのだが、そっち方面の研究って、あんまり進んでないような気がする。 「有限束の数え上げ」とか「魔円陣（完全ゴロム環）」とかいった話題は、 もう十年以上も取りあげられていないような気がする。 てなワケで、燃料を投下してみた。敲いてくださって結構。かかってらっしゃい。 数学はまるでダメだが、伊達に長年ネットで のたくっていたワケでもないので、 口だけは達者だ。
164:１３２人目の素数さん
18/05/28 15:54:28.71 DIMEHMYY.net
>>155
おお、数学屋さんがマトモに応答してくれるとは光栄だ。これは皮肉ではない。
本当にそう思っている。
> 2 に注目しているのは、
> コラッツ操作の「偶数を 2 で割る」
> 逆操作の「2 をかける」
> から来ています。
私はビット列として考えているので、“コラッツむし”みたいな概念で「シフト演算」
あるいは「ヌルビットの除去」というイメージで捉えているのだ。このあたり、
プログラマという商売柄がある。そんなわけで、「だったら、コテハン（固定ハンドル）を
使って立場を明確にしろ」ということであれば、対応するつもりだ。
165:１３２人目の素数さん
18/05/28 15:56:30.55 DIMEHMYY.net
>>155 つづき
>>「Z/pZ」（つーか、どうせ自然数なんだから「N/pN」で構わんと思うんだが、
>> それは「整数論」という括りでいうと「自然数に 0 が入っちゃまずいだろう」という
>> 配慮があるんだろうと思う）というのは、単なる剰余系であって、
>> 「何に関して閉じているか」っつーのは、また別の話なんだよな？
> ここで何を気にされてるのかいまいちよく分かりませんが、
> 「閉じている」という表現は全体の一部分を見ているときに使う表現なので、
> この場合適切でないと思います。
>
> 例. 整数全体の中の奇数の集合は、積について閉じていて和について閉じていない。
>
> 「どういう演算を考えているか」を気にしているということでしょうか？
「群論」というと、整数論をちょっと齧った人間としては、まず「循環群」
（その集合の要素をすべて網羅すること）を連想してしまうのだよ。
だから、「2 をかける」という操作よりも、「3n + 1 という操作に関して、
その有限集合が閉じているか？」が気になってしまうのだ。そういう意味では、
「どういう演算を考えているか」が気になる。
166:１３２人目の素数さん
18/05/28 15:57:44.90 DIMEHMYY.net
>>155 さらにつづき
> あと一応もう一つ言葉にツッコんでおきますと、
>> だけど、Z/pZ に対して、任意の i かなんかを持ってくると、Z/nZ（×i）というのは、
>> 「全部廻れる」わけじゃないので、Z/pZ の部分群の和集合という形に
>> なるんだよな？
> この「部分群」もちょっと用法がおかしいです。
> 例えば Z/7Z を {0},{1,2,4},{3,5,6} に分ける、というような操作に関しての
> 発言だと思いますが、
> これを表現したければ「軌道」と言うのが適切かと思います（群論の言葉です）。
済まぬ m(_ _)m。「軌道」という言葉は別のサイトで使っちゃってたので、
あえて避けた部分がある。
「軌道」によって排他的（重なる要素がない）集合に分割される「群」の
部分集合、という意味で「部分群」という言葉を使っただけだ。
コラッツ集合を表す「木」という言葉も、「根本のほうで循環してるんだから、
『木』っておかしくねぇか？」みたいな議論は前スレでもあったと思うが、
「ビット列の中で、最初のオンビットから最後のオンビットまでを
“コラッツむし”と命名する」みたいなコンセプトで、「根っこが 1 ビットである
木構造」と捉えると、「木」と呼んでも しっくりくると思うのだが。
167:１３２人目の素数さん
18/05/28 16:37:50.04 DIMEHMYY.net
>>156
> 問）どんな自然数からでも、コラッツ操作とコラッツ逆操作を繰り返すことで
> 9 の倍数に到達できるか？
なんとなく意味は分かるのだが、どういう問題意識があるのかがピンとこない。
mod p の木に奇数 m があり、mod q の木に奇数 q があったとすると、（p と q が
互いに素だとして）Z/pqZ 上では「根である 1 まで下がって、また上がってくりゃ
いいだけの話じゃん？」と思う。
「p と q の直近の（いちばん近い）共通の奇数 x があり、それぞれコラッツ操作に
よって x -> p と x -> q に至るルートを（効率よく）求める方法を（コラッツ操作と
コラッツ逆操作を それぞれ用いることで）示せ」っつーんなら、「ひょっとしたら、
なんとかなるかも知れん（オレが出来るとは言わんが）」くらいのことは言えるが。
168:前786
18/05/28 17:29:14.11 juv57CZY.net
>>161
私が考えているのは
「コラッツ予想は、初期値が n で割って k 余る数だけ考えれば十分である」
というのがどんな n, k についても成り立つか、という問題です。
それを証明するための一つの手段として、
「どんな自然数からでも、コラッツ操作とコラッツ逆操作を繰り返すことで n で割って k 余る数に到達できる」
を示そうと思っています。
ところで「mod p の木」とか 「mod q の木」などと私は一度も言っていませんが、何の話でしょうか。
Z/pqZ 上では「根である 1 まで下がって、また上がってくりゃいいだけの話じゃん？」、というのも意味がよく分かりません。
169:Mb
18/05/28 19:08:02.21 DIMEHMYY.net
>>162
要するに、
> 「コラッツ予想は、初期値が n で割って k 余る数だけ考えれば十分である」
> というのがどんな n, k についても成り立つか
というのは、
「コラッツ予想は、x ≡ k(mod n) だけ考えれば十分であるというのが、
どんな n, k についても成り立つか？」っつーのと同じことを謂っているように
思うのだが、うちらは「そのあたりに関しては、mod 3 と mod 4 の絡み合いに
関係していそうなので、なんだかんだで場合分けがややこしいことになりそうだ」
という話をしているだけなのだ。
そこで、
> それを証明するための一つの手段として、
> 「どんな自然数からでも、コラッツ操作とコラッツ逆操作を繰り返すことで
> n で割って k 余る数に到達できる」
> を示そうと思っています。
というのが、「コラッツ操作」と「コラッツ逆操作」を混在させてしまうと、
なんとなく迷走してしまいそうで、心配しているだけだ。
その発想だと、「共通の“節点”であるどこか」を経由しないと いかんような気が
するので、「根であるところの 1 へのルートをそれぞれについて求めて、
その差分を取る」みたいなアプローチが成功しそうに思う。
あくまで個人的な感想なのだが。
170:Mb
18/05/28 19:28:33.47 DIMEHMYY.net
>>162
> ところで「mod p の木」とか 「mod q の木」などと私は一度も言っていませんが、
> 何の話でしょうか。
原始根は複数個ありうるので、巡回群（剰余系における、全部の要素を辿る乗数系）も
複数個ありうるのだが、「一部の要素」をフォローする（単一の）乗数と、「その他の
要素」をフォローする乗数（その他大勢）が、全体として Z/pZ を隈なく覆う、
という「グループとしての、木の集まり」というものを考えて、「その集まりを
考えたときに、木の本数が、ある一定数よりも大きくならない」ということを
謂っているんだろうと思っているのだ。
それを考えると、「どこかの木に属している」ということは、「他の木に属していない」
という意味になりそうな気がするわけで、そうした「排他的な木」としての
「mod p の木」とか 「mod q の木」という概念はあっていいような気がするし、
それぞれの木が排他的に「すべての自然数」を所有しているとすると、
「グループとしての、木の集まり」がコラッツ問題をカバーしていることになり、
Z/(全部の木の基数の積)Z の存在を示すことができれば、コラッツ予想が肯定的に
証明できることになるような気がする。
171:前786
18/05/28 21:38:47.13 juv57CZY.net
>>163
mod 3 と mod 4 の絡み合いでややこしくなるとか、コラッツ操作とコラッツ逆操作を混在させて迷走しそうとか
心配はありがたいのですが、既に多数の n や k について証明できているのは見ていただけてるでしょうか。
「なんとなく」の印象だけで話されても困ります。
>>164
>「一部の要素」をフォローする（単一の）乗数
原始根にならない元のことでしょうか。よく分かりません。
数学の言葉でお願いします。
>「その他の要素」をフォローする乗数（その他大勢）
ここはもっとよく分かりません。
>Z/pZ を隈なく覆う、という「グループとしての、木の集まり」
軌道のことでしょうか。
>「その集まりを考えたときに、木の本数が、ある一定数よりも大きくならない」ということを謂っている
なんのことでしょうか。
172:righ1113
18/05/28 22:20:56.19 7MfED6re.net
>>144-147
説明ありがとうございます。完全に理解したとは言えないのですが……
このプログラムの実行には12時間以上かかったので、無駄にならなくて良かったです。
173:１３２人目の素数さん
18/05/28 22:30:29.54 vACmorEE.net
若干スレが荒れぎみですがこれも2chの華ですかね？
174:前786
18/05/29 08:17:04.68 uipUXNvy.net
>>166
よく粘りましたねｗ
逆
175:に言えば、プログラムで数千、数万回計算して得られた結論がたった３レスで説明できた訳ですから、 この考え方をうまくプログラムに落としこめれば計算量を大幅に削減できる可能性も…… >>167 私の発言でそう思わせてしまったなら申し訳ありません。
176:１３２人目の素数さん
18/05/29 14:20:35.00 hqRqM8Wt.net
「すべての自然数 N に対して、偶数は（素因数分解したときの 2 の乗数について
割ったら）奇数に帰着する。
「『４で割って３余る奇数』は、ビット列で表現したときに、下位のオンビット列
（一個以上のビット列が並んでいるビットパターン）」に帰着するので、
「４で割って３余る奇数」に帰着する。
そうすると、「４で割って１余る奇数」に帰着するすべての自然数が、3n + 1 操作に
対して、「４で割って１余る奇数」に帰着するかどうかが問題になるわけだから、
「ある『n ≡ 1(mod 4)の数が、(3n + 1)/2 操作によって、『n' ≡ 1(mod 4)の数』に
なるとき、n' が単調増加して無限大に発散するかどうか？」という話に帰着する。
そんなわけで、そのとき、2 で割ったときに、「『2 < n| 2^n - 1』が無限連鎖するか？」という話になる。
自分は数学屋ではないので、数式を追っかけて解決する自信がない。
数値実験で見当をつけようと思う。
ロジックに穴があったら指摘していただきたい。m(_ _)m
177:righ1113
18/05/29 18:52:19.94 MoZwWLVJ.net
>>169
最後がよく分からないです。
> 2 で割ったときに、「『2 < n| 2^n - 1』が無限連鎖するか？」
詳しい説明が欲しいです。
例えば、ビット列で言うとこう、とか
プログラム(アルゴリズム)で書くとこう、とか。
178:１３２人目の素数さん
18/05/29 19:02:13.73 4lgsCN3f.net
>>168
まあここまでが順調過ぎましたからね
今の方が本来の2chの姿に近いかも
あまりガッカリせずに気長に行きましょう
179:１３２人目の素数さん
18/05/29 21:09:33.77 hqRqM8Wt.net
>>169
> 最後がよく分からないです。
>> 2 で割ったときに、「『2 < n| 2^n - 1』が無限連鎖するか？」
> 詳しい説明が欲しいです。
あ、ごめん。言葉が足りなかった。
最下位に「連続した２個以上のオンビットがある」というのが
n ≡ 3(mod 4)
ということなわけで、
その場合は「下位のメルセンヌ部分を除去したビット列に、
3n + 2 操作を行ないつづけることで、n ≡ 1(mod 4) に帰着する」
ということが謂える。
だから、「メルセンヌ部分を除いた本体が、増えるか減るか」が
肝心なところであって、「最下位に一個以上の 0 があって、本体の長さが
減る」のか、「最下位に二個以上の 1 が現れて、本体の長さが増える」のかが
問題になるわけだ。
その部分に着目すると、コラッツ操作の逆操作を考えたときに、かなり計算量が
減るように思うので、「コラッツ予想は 5 × 2^60 までは成り立つ」みたいな
ショボい話（IEEE の long よりも小さい）ではなくて、メルセンヌ素数的な
デカい数まで（たとえば 10^100 とかまで）コラッツ予想は成り立つことが、
“数値実験的に”ではなく、“数学的に”（といっても、コンピュータによる
実験的な検証が入っているので、数学的な厳密性に欠けているという点については
完璧ではないのだが）「コラッツ予想は成立する」と断言しちゃっていい、
みたいな話になると思うのだ。
180:１３２人目の素数さん
18/05/29 21:10:17.02 hqRqM8Wt.net
少なくとも、「フツーにプログラムを動かしていたら、例外が見つかった」とか、
飛行機が堕ちて死ぬとか巨大彗星が堕ちてきて人類が滅亡するとか、そういった
確率の何百万分の１以下のところまで絞りこめれば、「実用的には、コラッツ問題は
解決した」（とはいえ、コラッツ問題の実用性というのが、あるとは思えないが）と
言っちゃっていいと思う。
暗号理論だって、「偶然、解読のための鍵が見つかっちゃう確率は 0 ではない」という
意味では完璧ではないわけで、「じゃあ、具体的には、コラッツ予想は、どこまでの
範囲で成り立つのか？」という限界を、「可能性がありそうな部分を、一個づつ
ブルート・フォース・アプローチによって潰してゆく」より効率のよさそうな方法で
ツブしてゆくというアプローチがありそうに思う。
で、その過程で、「なんか、こっから先には なんにもなさそうな気がする」という
限界が うっすらと見えてきたら、そこから逆に「じゃあ、このあたりには何があるの？」とかいった見当がつくのかもしれない、と思う。
コラッツ予想はメルセンヌ素数 8,191 に絡んで、2^8191 - 1 あたりで組合せ論的には
頭打ちになると思う。実際にメルセンヌ数から出発してメルセンヌ数に落ちるケースは
127 かなんかが最高だったので、あとは「メルセンヌ数ではない数から出発して、
3n + 1 操作“のみ”によってメルセンヌ数に落ちる」ケースを潰してゆけば、
コラッツ予想が成立する限界点は もっと先まで確認できるように思うし、
ひょっとしたら（四色問題や有限群の分類みたいに）「この先は、組合せ論的にいって
ありえない」みたいなコトになるかもしれない（とはいえ、私は数学の専門家では
ないので、数学者の誰かが証明できたとしても、その証明を理解できる自信は
まったくないのだが(-_-!)）。
てなワケで、現在探索を続行中。
181:１３２人目の素数さん
18/05/29 21:15:32.62 f2WjLLel.net
>>173
探索を実行中ってことはもうプログラムがあるってこと？
なんなら>>1みたいに晒してくれてもいいのよ？
182:１３２人目の素数さん
18/05/29 21:38:00.75 hqRqM8Wt.net
>>170
ごちゃごちゃ長文を書いてしまって申し訳ない。m(_ _)m
要するに、「いままで、『n 以下までにはコラッツ予想の
反例はない』というのを示すのに O(n) の手間がかかって
いたのだが、それを O(lon(n)) に持ってくことができたら、
5*2^60 とかいう ショボい話じゃなくて、 2^127 くらい
までは（できれば 2^4095 くらいまでは）持ってけねぇか？」
っつー話。
>>174
> 探索を実行中ってことはもうプログラムがあるってこと？
『Java の宿題ここで答えます』の回答者側の常連だったので、
「とりあえず動く」レベルのものはあるのだが、やっつけで
書いたもんだから（これが Hacker というものだ）あんまり
フツーのプログラマが見て分かりやすいモンじゃねぇんだよな(-_-!)
自前でやってる WebLog のほうに、近々さらすことにして、
ソーズは もうちょっと洗濯させてくれ m(_ _)m
183:righ1113
18/05/29 22:09:23.31 HdpfadtL.net
>>175
今ひとつ分からないので、自分はソースを待ちます。
184:１３２人目の素数さん
18/05/29 22:34:19.60 f2WjLLel.net
やはり>>786が論理を構築し>>1がその論理をプログラムで実装するというのがこのスレのベストプラクティス。
なにかいいネタはないかな。
185:righ1113
18/05/29 22:53:33.64 HdpfadtL.net
>>177
>>113とか、どうですかね?
186:１３２人目の素数さん
18/05/29 23:17:54.07 f2WjLLel.net
いまいちよくわかってないんだが>>113の①②③はそれぞれ別々に証明する必要があるってこと？
で①②③がいえれば④がいえるってこと？
187:前786
18/05/29 23:19:19.88 z3i0m55/.net
>>177
プログラムの結果を参考にして証明を進める、までできれば私としてはベストですね。
今は>>168で書いた案について考え中。
>>178
>>113の①はなんとかなるかもしれません。
「繰り返すと１つになる」というよりは「繰り返しても集合の個数が増えない」という論法になりそうです。
ちょうど>>168のアイデアにも関連します。
このあと軽く説明します。
188:righ1113
18/05/29 23:30:01.77 HdpfadtL.net
>>179
①と②は対偶関係なので、
①を証明する→③を証明する→④が言える
です。
189:前786
18/05/29 23:38:41.79 z3i0m55/.net
そもそも>>94の説明がなぜあれだけで済んだのかというと
・mod 7*19 で考えるところを、mod 7 と mod19 に分けた。
・mod 7*19^2 で考えるところを mod 7 と mod 19^2 に分け、
さらに mod 19^2 で考えるところは実質 mod 19 で考えるだけで済んだ。
ということが効いているんじゃないかと思います。
それで、一�
190:ﾂ目はおいといて二つ目の mod 19^2 で考えるところが mod 19 で済む という部分がポイントで、 こういうのが許されるのはちょうど「C を繰り返して集合が増えないとき」になりそうなんです。 さらに、プログラムを進めていくとどこかで「繰り返しても集合が増えない」となることも証明できそうなので、 これを利用してプログラムの計算量を減らせそう、という考えです。 時間があるときにちゃんと考えようと思います。
191:前786
18/05/29 23:51:01.24 z3i0m55/.net
（実際のところ、>>156が分かる人がどのくらいるのかちょっと気になる）
192:righ1113
18/05/30 00:00:21.34 SjK0M6Ur.net
>>183
自分は分かっている……つもりです……
193:１３２人目の素数さん
18/05/30 05:29:09.70 BsxBoGmV.net
2倍の繰り返しで
1→2→4→8→16≡7→14≡5→10≡1
0→1
3の倍数が残るけど2で割り続けて奇数になったあと
3n→3n×3+1≡1
でおしまい
2倍は「好きなだけ遡れる」ところがポイントかね
194:１３２人目の素数さん
18/05/30 07:45:42.08 pjE9OVg/.net
13 だったらまだ理解できるんだがな。
1 → 2 → 4 → 8 → 16 ≡ 3 → 6 → 12 → 11 → 9
→ 18 ≡ 5 → 10 → 20 ≡ 7
つーても、これがコラッツ予想の解決とどう結びつくのかがわからんが。
195:１３２人目の素数さん
18/05/30 07:46:53.88 pjE9OVg/.net
あ、
×
196:１３２人目の素数さん
18/05/30 07:48:45.57 pjE9OVg/.net
あ、
× 12 → 11 → 9
〇 12 → 24 ≡ 11 → 22 ≡ 9
だった。
197:１３２人目の素数さん
18/05/30 08:09:47.45 pjE9OVg/.net
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 を
考えたらいいのか …… わからん。
198:前786
18/05/30 08:32:25.52 8DwWThhE.net
>>185
残念
Z/9Z において 0→1 (3倍して1を足す) は可逆でないので、これだと不十分です。
実際、この方針で例えば 16 から 9 の倍数を作ろうとすると、
2 を 2 回かけて 16→32→64
1 を引いて 3 で割って 64→21
で、9 の倍数になりません。
>>186
確かに私の予想が証明できてもすぐにはコラッツ予想に繋がりませんが、
まあ外堀を埋めるような感覚です。
それに、もし万が一私の予想に反例が見つかれば、その時点でコラッツ予想も不成立となるので、
そういう意味ではコラッツ予想を直接攻めていると言えなくもないかなと。
199:１３２人目の素数さん
18/05/30 15:44:56.54 pjE9OVg/.net
>> 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 の
記述は、このあたりに絡んでいるのかもしれないと思う。
200:righ1113
18/05/30 18:37:06.75 0W4YjiD/.net
>>191
下位に2^n-1が出てくるだけじゃなくて、実際のメルセンヌ数も絡むの?!
ますます分からなくなる(>_<)