コラッツ予想がとけたらいいな　その2

**righ1113** ◆OPKWA8uhcY · 2018/05/10(木) 22:10:23.74

コラッツ予想に挑戦するスレです。

前スレ　コラッツ予想がとけたらいいな
https://rio2016.5ch.net/test/read.cgi/math/1350178359/

>>1の証明（未検証）
https://github.com/righ1113/collatzProof

それより弱い成果もあります（未検証）
コラッツのループはあるとしてもとても長い
https://github.com/righ1113/collatzLongLoop

**righ1113** ◆OPKWA8uhcY · 2018/05/10(木) 22:12:02.92

今は前スレ>>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が初期値の場合だけ調べればいい」

**１３２人目の素数さん** · 2018/05/10(木) 22:17:20.64

>>1乙

**前786** ◆5A/gU5yzeU · 2018/05/10(木) 23:48:07.63

前スレ>>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 が奇数の場合に帰着されます。

**前786** ◆5A/gU5yzeU · 2018/05/10(木) 23:53:50.84

あれ、コピペが抜けてた。
>>1乙

**１３２人目の素数さん** · 2018/05/11(金) 00:02:28.46

自己満足しました

**前786** ◆5A/gU5yzeU · 2018/05/11(金) 20:23:02.52

アルゴリズムのどこに無駄があったのかという話

（前スレ>>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 の組ができるかどうかはそもそも考える必要がありません。
ここに無駄がありました。

**前786** ◆5A/gU5yzeU · 2018/05/11(金) 20:23:37.57

証明は次のように進みます。

～～～～～～～～～～

(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' を決めておくことによって
必要なグループのみ扱うようにしています。

**１３２人目の素数さん** · 2018/05/11(金) 20:56:06.22

俺はあんまり素数についてのノウハウ知らないんだよね。
素数のノウハウあれば「n=q,n=qで予想が成り立つ」から「n=pqで予想が成り立つ」へ繋げるアイディアももっと湧くのかもしれない、等と思ったり。

**１３２人目の素数さん** · 2018/05/11(金) 21:47:49.08

とりあえず、目の前に大量のデータがあるわけだけど、
こういうのから何か法則を見出すのって、コツとかあるのかな

**前786** ◆5A/gU5yzeU · 2018/05/11(金) 23:35:34.41

とりあえず 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} 以外に複数のグループに分かれる、というぐらい。
もっと細かく分類する必要がありそう。

④はもっと分からない。
これもさらなる分類が必要と思われる。

**１３２人目の素数さん** · 2018/05/11(金) 23:57:27.27

ふーむ、まずは分類ですか。
まあいきなりきれいな法則は見つかりそうにないし、正しい方針かも。

**righ1113** ◆OPKWA8uhcY · 2018/05/11(金) 23:58:26.25

プログラミングは3割ぐらい進みました。
あと2,3日には出来ると思います。
アルゴリズムも進化して、こちらもコーディングのやりやすさを感じています。

**前786** ◆5A/gU5yzeU · 2018/05/12(土) 01:03:18.42

あ、3 の累乗は証明済みなので、>>11では抜いてあります。

**１３２人目の素数さん** · 2018/05/12(土) 01:06:51.91

なんかこの予想に名前つけたいですね。
名前あったほうが議論しやすいですよね？
>>786なにか名前考えてもらえませんか？

**１３２人目の素数さん** · 2018/05/12(土) 01:19:48.51

なんかこの予想が肯定的に解決するなら素因数分解が多項式時間でとけちゃうとか、重大な結果に繋がったりしないかな？ｗ

**１３２人目の素数さん** · 2018/05/12(土) 02:27:14.92

離散対数問題とか絡んできそうな気が若干する

**righ1113** ◆OPKWA8uhcY · 2018/05/12(土) 04:55:29.69

ジェバンニが一晩でやってくれました
*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>

**１３２人目の素数さん** · 2018/05/12(土) 09:10:52.54

おお、乙です。

**前786** ◆5A/gU5yzeU · 2018/05/12(土) 10:47:03.59

>>18
はやいｗ
乙です。

(6) でいちいち全部出力すると後々大変なことになりそうな予感。
もちろんデータが多いのは利点でもあるけど、うーむ

**前786** ◆5A/gU5yzeU · 2018/05/12(土) 10:55:50.38

>>15
剰余コラッツ予想(Residue Collatz Conjecture)とかですかね。
英語で書くとそれっぽく見える不思議。

**１３２人目の素数さん** · 2018/05/12(土) 16:47:33.40

初代プログラムで121試したら一晩かけても答えでなかったのに２代目だと一瞬で出たんだが？
そんなにパフォーマンス変わってる？
それとも初代で１晩かかったのがおかしいの？

**righ1113** ◆OPKWA8uhcY · 2018/05/12(土) 17:25:28.39

>>22
かなりの高速化に成功しています。
あと実は、初代ではn=85などでうまくいかない不具合がありました。二代目では直っています。

**１３２人目の素数さん** · 2018/05/12(土) 17:56:15.06

ほう、そいつは素晴らしい

**１３２人目の素数さん** · 2018/05/12(土) 18:02:57.93

ここのところスレとして毎日なにかしらの成果が挙がってる感じですが
そろそろ停滞しはじめてもおかしくない時期ですかね？
なにか壁がありそうな予感。

**前786** ◆5A/gU5yzeU · 2018/05/12(土) 19:04:42.48

>>22>>23
初代プログラムでは、上に書いた通り本来探す必要のない組を探す必要がありました。
なので多分、その「本来探す必要のない組」の中に「どう頑張っても得られない組」が混ざっていたんだと思います。
出力結果を見せていただければはっきりすると思いますが、
まあ旧版の話なのでそこまで調べる必要も無いですかね。

こういうことが起こる可能性があるということは早くから気づいていて、
実はその解消のため作ったのが二代目です。
なので、初代に不具合があったと聞いてむしろ安心しました。
そうでないと二代目を作った意味がないのでｗ

それにしても、体感できるほど速度が上がるというのは想定以上ですね。
もしよければ、また出力結果をまとめてアップしてくれると嬉しいです。

**１３２人目の素数さん** · 2018/05/12(土) 19:19:24.68

うーんまだアルゴリズムをしっかり理解できてないな。
まずはそこからか…

**righ1113** ◆OPKWA8uhcY · 2018/05/12(土) 19:24:14.47

>>20
Nothing消します？重要でない情報なら。

**前786** ◆5A/gU5yzeU · 2018/05/12(土) 21:48:00.59

>>28
今のは今ので残しておいて、別バージョンとして例えば
(4) では得られた B のみ、(6) では得られた C のみ
という風に出力するのは作れるでしょうか。
アルゴリズムを進めるにはその情報だけで十分なので。

それで、大量の n を調べるときは別バージョン、
個別の n を調べるときは今のという風に使い分けていければ一番良いと思います。

**righ1113** ◆OPKWA8uhcY · 2018/05/12(土) 23:42:46.59

>>29なるほど良いアイデアですね。
ではそのように。

**righ1113** ◆OPKWA8uhcY · 2018/05/13(日) 13:22:27.62

大量実行バージョン作りました。ノーマルとの違いは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

**前786** ◆5A/gU5yzeU · 2018/05/13(日) 14:48:12.95

>>31
乙です。

とりあえずざっと見たところ、ほとんどの処理が C' までで終わってますね。
C'' で検索すると合わせて 4 つしか出てこない (73, 85, 127, 133)。
C''' まで出てくることはあるんだろうか。

**前786** ◆5A/gU5yzeU · 2018/05/13(日) 16:45:43.20

よく見たら想定した挙動とちょっと違うような…
「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]]
と二組出力されています。

ちょっと見てみてもらえませんか？
これが直ればさらに速度も上がると思います。

**righ1113** ◆OPKWA8uhcY · 2018/05/13(日) 17:37:11.27

>>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 : []
プログラムは正常終了しました。

**前786** ◆5A/gU5yzeU · 2018/05/13(日) 17:57:57.52

>>34
これなら想定通りです。
てっきり「mod n で見た時 A' に属さない」を入れたおかげで早くなったのだと思っていたんですが。
そうじゃなかったんですね。

**righ1113** ◆OPKWA8uhcY · 2018/05/13(日) 18:08:42.61

>>35
初代が遅かった原因は、自分のコーディングのまずさにあったと思っています。

プログラム、アップロードしました。失礼しました。

**righ1113** ◆OPKWA8uhcY · 2018/05/13(日) 20:06:20.61

>>32
n=455でC'''が出てきました。
大量出力でしたが、ログを取りました。
https://github.com/righ1113/CollatzMod/blob/master/%E4%BA%8C%E4%BB%A3%E7%9B%AE/n%3D455.txt

**１３２人目の素数さん** · 2018/05/13(日) 20:33:55.94

そんなデカい数まで走らせられるのか
凄いな

**righ1113** ◆OPKWA8uhcY · 2018/05/13(日) 21:01:46.58

1つ実行するのに20分ぐらいかかったので、
ここいらへんが限界のようです。

**前786** ◆5A/gU5yzeU · 2018/05/13(日) 22:47:57.50

>>37
やっぱ出ましたか。
こうなると理論上はいくらでも長くなりそう。

455=5*7*13
(Z/5Z)*, (Z/7Z)*, (Z/13Z)* それぞれで 2 の位数は 4, 3, 12
(Z/455Z)* での 2 の位数はその最小公倍数である 12

n がたくさんの素因数を持てば持つほど、また、2 の位数が小さければ小さいほど最初の Z/nZ の分割が多くなるので
わりと納得の結果です。

**前786** ◆5A/gU5yzeU · 2018/05/15(火) 23:42:53.44

証明がちょっと進んだけど
余白が……ではなく時間が足りない。

**１３２人目の素数さん** · 2018/05/16(水) 00:14:21.05

ほう、ちょっとづつだとしても毎日前進してるというのは凄いですな。
アイディアだけでも先行で聞かせてほしい。

**前786** ◆5A/gU5yzeU · 2018/05/16(水) 00:15:54.58

とりあえず状況の整理だけ

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 の場合に部分的に予想が証明できた。

**１３２人目の素数さん** · 2018/05/16(水) 00:22:01.01

ほほう、>>786は群論の知識があるのか。
俺にはないorz.

**１３２人目の素数さん** · 2018/05/16(水) 00:24:30.33

でもまあ着実に外堀が埋まっていってる感じですかね？

**１３２人目の素数さん** · 2018/05/16(水) 20:58:53.07

群論的な観点でいえば合成数の場合を素数の場合に帰着する望みはありそうなんですか？

**前786** ◆5A/gU5yzeU · 2018/05/16(水) 23:09:35.30

>>46
n と m が互いに素であるとき Z/mnZ は (Z/mZ)×(Z/nZ) に同型なので
何かしら関連付けることはできるかもしれませんが、
完全に帰着させるのは難しそうというのが正直なところ。

これには根拠がありまして、プログラムの出力結果を見ると
例えば n=35 にかかった計算量は
n=5 と n=7 の計算量の合計よりかなり多いということが見て取れます。
そうすると、n=35 を n=5 と n=7 に帰着させるのは苦しいんじゃないかなあと思うわけです。

**１３２人目の素数さん** · 2018/05/16(水) 23:17:00.63

>>47
ふーむそうなのか。
ありがとうございます。
先は長そうですな。

**前786** ◆5A/gU5yzeU · 2018/05/16(水) 23:32:04.61

このままだと、場合分けが延々と広がって収拾がつかなくなる、
といういつもの感じになりそうな雰囲気がぷんぷんしますけどね。

とりあえず示せたのはこちら。

定理
>>43において指数が 2 であり、かつ p≡3 (mod 4) のとき、
k=1,2,…,p-1 に対して予想が成り立つ。

証明は後日。

**１３２人目の素数さん** · 2018/05/16(水) 23:38:41.29

mod 4 ですか？　意外な数字がでてきましたね。
まあ、証明を楽しみに待ちます。

**前786** ◆5A/gU5yzeU · 2018/05/20(日) 00:54:51.37

途中まで。

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 はλ*(平方数) の形で表せる元全体に等しい。□

**前786** ◆5A/gU5yzeU · 2018/05/20(日) 00:55:45.58

次に (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 を得る。
したがって ⇔ が成り立つ。□

**前786** ◆5A/gU5yzeU · 2018/05/20(日) 00:56:31.04

補題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)
と同値である。□

**前786** ◆5A/gU5yzeU · 2018/05/20(日) 00:58:06.31

あとは方程式 (a)～(d) の解の存在を示せばよい。
とりあえずここまで。

前にもあったけど、こうやって代数方程式に帰着できたのは個人的に面白いと思った。

**righ1113** ◆OPKWA8uhcY · 2018/05/20(日) 03:49:10.15

ところで流れと関係ない質問ですが、
プログラムの3のところを5に変えたら、
5x+1問題を論じている事になりますか？

**前786** ◆5A/gU5yzeU · 2018/05/20(日) 09:48:45.09

>>55
なると思います。

**前786** ◆5A/gU5yzeU · 2018/05/20(日) 16:32:50.23

>>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 通り。

**前786** ◆5A/gU5yzeU · 2018/05/20(日) 16:33:24.36

(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 の場合に予想が成り立つ。

**前786** ◆5A/gU5yzeU · 2018/05/20(日) 16:36:22.12

あ、あと訂正。
>>43で「指数1, mod 3 で 1」の欄に 131 があるけど、
131 は「指数1, mod 3 で 2」の欄でした。

**１３２人目の素数さん** · 2018/05/20(日) 17:38:06.32

ぬおー複雑すぎてついていくのがしんどいorz
平方数がどうとかいうのは群論でも普通によく使われるテクニックなんですか？

**前786** ◆5A/gU5yzeU · 2018/05/20(日) 18:16:56.14

>>60
群論というより、どちらかというと整数論ですかね。
少なくとも自分はよく使います。

**１３２人目の素数さん** · 2018/05/20(日) 22:31:52.19

>>1は理解できてる？
基本このスレには3人しかいないから俺がだめなら>>1しかいない。。。

**righ1113** ◆OPKWA8uhcY · 2018/05/21(月) 01:21:10.42

>>62
いや～4割ぐらいっすねー

**１３２人目の素数さん** · 2018/05/21(月) 20:37:31.44

とりあえず、この場合の平方数というのは

可換体 K の乗法群 K* の部分集合 {x2 | x ∈ K} （直積集合と紛れるおそれのないときには
これを (K*)2 などと表す）の元を平方数や平方元と呼ぶことがある。（wikipediaより）

であってますかね？

**前786** ◆5A/gU5yzeU · 2018/05/21(月) 21:02:18.85

>>64
あってます。
Z/pZ の場合は「平方剰余」という呼ばれ方をすることが多いですが、
私は「平方数」の方が慣れているのでそうしました。

**１３２人目の素数さん** · 2018/05/21(月) 21:25:13.58

誠に申し訳ないが乗法群の説明がwikiじゃよくわからんorz.
むかし学校で習ったような気もするがあまりに昔の話で記憶が霞んでるorz.

とりあえずこのページ見つけたけどこれでいい？
https://math-note.xyz/algebra/basis-of-algebra/

**前786** ◆5A/gU5yzeU · 2018/05/21(月) 21:59:04.76

>>66
>>51で扱っているものは「環の乗法群」あるいは「体の乗法群」というもので
そこには載ってないですね…

乗法群とは、「積に関して逆元を持つ要素を集めた群」です (群がよく分からなければ集合と読み替えてください)。
Z/nZ の場合、これは 0 から n-1 のうちで n と互いに素な数だけを集めたものになります。
したがって、
Z/pZ の乗法群は {1,2,...,p-1}
Z/3pZ の乗法群は 3 の倍数でも p の倍数でもない元全体の集合
となります。

**１３２人目の素数さん** · 2018/05/21(月) 22:24:15.94

>>67
おお、ありがとうございます。
群に関して解説しているお勧めページありましたら教えてください。

**１３２人目の素数さん** · 2018/05/21(月) 22:54:59.90

あ～すいません。
群じゃなくて環、体なんですかね？

**前786** ◆5A/gU5yzeU · 2018/05/21(月) 23:20:03.77

有名ですけどこの辺りとか

物理のかぎしっぽ - 代数学
http://hooktail.org/misc/index.php?%C2%E5%BF%F4%B3%D8

群、環、体について基本的なことが載っています。
Z/nZ の話に絞れば、例えば

Excel VBA 数学教室 - 数学辞典 - 整数論入門講座
http://excelmath.atelierkobato.com/kosiki/elementary-number/

この辺りも詳しそうです。

**前786** ◆5A/gU5yzeU · 2018/05/21(月) 23:34:55.13

ざっと見たところ、上記のサイトには
>>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/

**１３２人目の素数さん** · 2018/05/21(月) 23:45:47.55

ありがとうございます。
1から勉強だなこりゃ

**１３２人目の素数さん** · 2018/05/22(火) 20:15:30.49

私が勉強追いつくのは結構時間かかると思うのでスレは自由に進めてくださいねｗ

**前786** ◆5A/gU5yzeU · 2018/05/22(火) 23:49:30.33

>>73
まあこちらもそんなに大きな進展はないですけどね。

>>11の②の場合 (n=p、p は 5 以上の素数、Z/pZ で 2 が原始根、p≡1 (mod 3)) で
k=0 だけ抜けてるのをやはり何とかしたいので考え中。

まだ証明はできてませんが、この場合ほとんどの p ではアルゴリズムが C で終わりそうです。
実際、200 以下の出力では n=13 を除いて全ての場合でアルゴリズムが C で終わっています。

**前786** ◆5A/gU5yzeU · 2018/05/23(水) 00:52:33.04

一旦理屈をすっ飛ばしますが、
n=p、p は 5 以上の素数、Z/pZ で 2 が原始根、p≡1 (mod 3) で k=0 のとき、
とりあえず以下の方法で検証できることが分かりました。

(1) 縦２マス横 (p-1)/2 マスのマス目を考え、図のように３色で塗り分ける。
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) ３色とも少なくとも１つのマスに印がついていれば予想が成り立つ。

**前786** ◆5A/gU5yzeU · 2018/05/23(水) 00:56:44.28

あ、>>75の(4)は「予想が成り立つ」より「アルゴリズムが C で終わる」の方が適切です。

n=13 の場合、次のような結果になります。
https://i.imgur.com/4grIMIw.jpg
黄色マスに印がつかないので、アルゴリズムは C で終わりません。

**righ1113** ◆OPKWA8uhcY · 2018/05/23(水) 01:21:25.86

プログラムでイレギュラーを見つけました。

プログラムの3を19に変えてn=7で、
---
(4) A' の各元 a に対し、3a+1 がどの Bi に属すかを見る。（どの Bi にも属さないこともある）
---
で全ての3a+1が属さないのです。
プログラム上ではオールNothingになります。

詳しい説明は今晩します。

**righ1113** ◆OPKWA8uhcY · 2018/05/23(水) 01:31:18.18

正確にはこうです。

プログラムの3を19に変えてn=7で、
---
(4) A' の各元 a に対し、19a+1 がどの Bi に属すかを見る。（どの Bi にも属さないこともある）
---
で全ての19a+1が属さないのです。
プログラム上ではオールNothingになります。

**１３２人目の素数さん** · 2018/05/23(水) 12:01:38.73

　整数論関係で盛り上がっているところで申し訳ないのだが、
二進数表記で ON ビットが二個以上連結すると、
上（偶数に向かうシークエンス）というのが、
ON ビット n に対して n - 1 個連続する。

　２の倍数を XY 座標のの X に取るとすると、
偶数は、「２で割る」操作のどっかでシークエンスに引っかかる
（つーか、奇数になる）。

　コラッツ操作がカオティックな挙動をするというのは、
「３ｎ＋１の結果が奇数でありつづける」（つまり、下位のビットが
ON でありつづける）と、「２で割り続ける」と、「偶数は割り続けると、
どこかで奇数になる」という、周期３のループに引っかかっている
せいではないかという気がしてきた。

　「３ｎ＋１」で無限大に発散することはありえない
（メルセンヌ数との関連で、それは自明）。

　つーことは、「下位がオンビットの値（奇数）で受けとめきれない」
偶数があるかどうか、みたいな話になりそうな気がする。

**righ1113** ◆OPKWA8uhcY · 2018/05/23(水) 19:18:42.10

>>79
>　「３ｎ＋１」で無限大に発散することはありえない
>（メルセンヌ数との関連で、それは自明）。
詳しく知りたいです。

**１３２人目の素数さん** · 2018/05/23(水) 20:35:47.24

>>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 のみではないビット列が並んでいる」からだ。

　そこに、「三倍して１を足す（ 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 を超えることはないことが判っている。

**１３２人目の素数さん** · 2018/05/23(水) 20:40:42.01

×　> そのビット列に p 個以上の 1 が現れて
〇　> そのビット列に p 個以上連続した 1 が現れて

**１３２人目の素数さん** · 2018/05/23(水) 20:43:34.27

あかん。
>> 4 で割って 3 余る奇数（n mod 4 = 3）
は余計だった。すまぬ。

**righ1113** ◆OPKWA8uhcY · 2018/05/23(水) 21:07:48.22

>>81
なるほど。下位の連続した1のビットに注目しているのですね。
自分もコラッツパターンで考えていました。
http://d.hatena.ne.jp/righ1113/touch/20120514/1336979899

**１３２人目の素数さん** · 2018/05/23(水) 21:36:38.24

お、新人さんかい？

**前786** ◆5A/gU5yzeU · 2018/05/24(木) 00:50:30.75

>>77>>78
これ気になるんで詳細待ってます。
正常に動いていれば Nothing 以外も出てくるはずですが…

**righ1113** ◆OPKWA8uhcY · 2018/05/24(木) 01:01:12.08

>>86
すいません今晩はムリでした(>_<)

**前786** ◆5A/gU5yzeU · 2018/05/24(木) 01:22:11.96

>>87
さいですか。
まあ、気長に待ちますんでお気になさらず。

**１３２人目の素数さん** · 2018/05/24(木) 10:37:42.13

　また通りすがりのプログラマが覗きにきました。お邪魔します。

　「奇数 →（奇数 →）６で割って２余る偶数 → 奇数」

というループに乗っていないのは１だけ。

　「奇数 → 偶数」というルートを通らないのは２の冪乗数だけ。

　それ以外で、“ループではない”「奇数 → ６で割って２余る偶数 → 奇数」という
“ルート”に乗って“いる”のは２の冪乗のうち「６で割って２余る偶数」だけ。

　つまり、ここから先は、上記の条件に引っかからない「６で割って２余る偶数」と
「奇数」だけを考えればいい。

　ここからは、単純に上記の条件に引っかからない「６で割って２余る偶数」と
「奇数」だけを考えればいいような気がする。

　このあたりから始めて、「コラッツ操作を根っこのほうから逆に辿って、
枝がどう伸びているか」を逆に辿ってみようとしているのだが、
辿ってみた結果をどう整理したらいいのかが、正直わからん。484 と 485 とか、
変なところでニアピンしてる奴がいるんだよなぁ（どっちも３ステップ後に
182 を通る）。

　これは三次元表示とかを考えたほうがいいのかね？　映像として見ることで、
なんかしらの法則性が見えてくるということもあるわけだし。

**righ1113** ◆OPKWA8uhcY · 2018/05/24(木) 17:50:33.60

>>89
「6で割って2余る数」か「奇数」かたっぽだけ調べれば良いような気がします。

画像表示はカオティックなものしか得られずにう～ん……という感じです。

**１３２人目の素数さん** · 2018/05/24(木) 19:31:53.90

>>90
確かにカオスって「断面」で見るからそういう感じはするんだよね orz
つーても一次元で見ても傾向がわからんような気が。

**righ1113** ◆OPKWA8uhcY · 2018/05/24(木) 19:35:11.39

>>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''でカラになります。ここで止めました。

どこかプログラムがバグってるんですかね。
自分はてっきり、これが無限走行へ至る道かと思ったのですが。

**１３２人目の素数さん** · 2018/05/24(木) 19:40:13.49

漏れは航空宇宙工学科出身なので
「可視化」っつーのは重要だとは思ってるんだけど、
カオス系のように「見えたからって、なんも解決せん」とか、
f^-1 ゆらぎのように「実際に計測してみたら、単なる
対数分布だった」（ラーメンの汁に浮いてる油滴なんかがそう）とか、
ハズレが多いのは分かってるんだが ……
なんかしら別視点に期待する部分はあると思われ。

**前786** ◆5A/gU5yzeU · 2018/05/24(木) 20:30:26.05

>>92
>>86は B の段階で全て Nothing になったのだと勘違いしていました
ちゃんと見てみます。

**righ1113** ◆OPKWA8uhcY · 2018/05/24(木) 20:34:17.94

ああすみません。
>>78の書き方が悪かったです。

**１３２人目の素数さん** · 2018/05/24(木) 20:52:34.74

可視化はいいけどどうやって可視化するかはアイディアあんのか？
３次元表示だけじゃ具体性に乏しい。

**前786** ◆5A/gU5yzeU · 2018/05/24(木) 21:45:42.25

>>92
とりあえずこの出力結果は間違ってなさそうです。
詳細は後ほど。

**righ1113** ◆OPKWA8uhcY · 2018/05/24(木) 22:08:44.37

おお~~

**１３２人目の素数さん** · 2018/05/24(木) 22:53:57.29

>>97
新展開ですか？

**前786** ◆5A/gU5yzeU · 2018/05/25(金) 00:00:11.96

出力結果が正しいことの説明もしたいところですが、その前に別の話を。

まず一応誤解のないように言っておきますが、
この結果から即座に「コラッツ予想の 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 で考えたものが私の予想です。