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

**righ1113** ◆OPKWA8uhcY · 2018/02/09(金) 22:41:34.79

コラッツパターン2にしたら、
4x+1が小さくならなくなってしまいました。無念。

**righ1113** ◆OPKWA8uhcY · 2018/02/24(土) 14:20:55.93

構成を大幅に変えました。
コラッツパターン2も変えました。

**１３２人目の素数さん** · 2018/02/27(火) 22:53:52.42

コラッツ問題の解決の役に立つかどうかはわからんが、思いついたので投下。

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

**１３２人目の素数さん** · 2018/02/27(火) 22:55:29.10

以下、超略証。
(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からは周期の中での単調性が示せる。
(格子状の道の最短経路の曲がり方を一つづつ変えて行くように)

**１３２人目の素数さん** · 2018/02/28(水) 19:18:14.81

>>774
＞(格子状の道の最短経路の曲がり方を一つづつ変えて行くように)
ここがだめ(全順序にならん)なので不成立。
一定の条件のもとで、近い数は近くなる、くらいしか言えてないか。

￥ ◆2VB8wsVUoo · 2018/04/06(金) 12:28:59.91

￥

￥ ◆2VB8wsVUoo · 2018/04/06(金) 12:29:18.95

￥

￥ ◆2VB8wsVUoo · 2018/04/06(金) 12:29:38.52

￥

￥ ◆2VB8wsVUoo · 2018/04/06(金) 12:29:56.45

￥

￥ ◆2VB8wsVUoo · 2018/04/06(金) 12:30:18.29

￥

￥ ◆2VB8wsVUoo · 2018/04/06(金) 12:30:38.74

￥

￥ ◆2VB8wsVUoo · 2018/04/06(金) 12:30:58.98

￥

￥ ◆2VB8wsVUoo · 2018/04/06(金) 12:31:16.94

￥

￥ ◆2VB8wsVUoo · 2018/04/06(金) 12:31:36.78

￥

￥ ◆2VB8wsVUoo · 2018/04/06(金) 12:31:59.28

￥

**１３２人目の素数さん** · 2018/04/28(土) 16:55:40.82

１つ予想を立ててみた。

自然数全体の集合を N とする。
まず木を定義する。

定義
自然数 a に対し、集合 T(a) を
T(a) = {b∈N | a と b はコラッツ操作によって同じ数に到達する}
と定める。
T(a) の形の集合を木と呼ぶ。

コラッツ予想が真であることは、自然数全体が１つの木をなすことと同値である。
で、次のように予想した。

予想
T を木とし、n, k を自然数とする。
このとき、ある a∈T が存在して a≡k (mod n) が成り立つ。

コラッツ予想が正しければ、T は N に一致するので、明らかにこの予想は成り立つ。
逆にいえば、予想が成り立たないような T, n, k が存在する場合、コラッツ予想も偽であることになる。

**１３２人目の素数さん** · 2018/04/28(土) 16:56:23.83

基本的な操作を補題としてまとめておく。

補題
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
２つの自然数 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。□

まだいろいろと書けることはあるけど、反応を見ながらということで。

**righ1113** ◆OPKWA8uhcY · 2018/04/28(土) 17:56:49.19

考え方として、
いくつもの木を考えるのですか？
それとも1を含む木T1のみに注目するのですか？

**786** · 2018/04/28(土) 18:15:59.36

全ての木を考えます。
それが１つなのか複数なのかは分かりませんが。

**righ1113** ◆OPKWA8uhcY · 2018/04/28(土) 18:26:23.27

なるほどありがとうございます。

**１３２人目の素数さん** · 2018/04/28(土) 18:28:10.02

お、新人か。

**１３２人目の素数さん** · 2018/04/28(土) 18:42:45.61

ぜひ新しい風を吹き入れてほしいね。

**786** · 2018/04/28(土) 18:53:42.76

これを書こうと思って忘れていた。

コラッツ予想は初期値が奇数の場合だけ調べればいい、というのは明らかだが
>>786の予想が正しければそれを一般化できる。

すなわち、ある n, k について予想が正しければ、
「コラッツ予想は a≡k (mod n) を満たす自然数 a が初期値の場合だけ調べればいい」
と言える。

>>791>>792
よろしくお願いします。

**１３２人目の素数さん** · 2018/04/28(土) 19:00:55.51

modに関しては2と3には何かあるかもしれないが例えば5はどうか？といわれるとちょと疑問
今の時点ではね

**１３２人目の素数さん** · 2018/04/28(土) 20:44:50.70

グラフ理論に「木」があるから名前は変えた方がいいかもね
グラフ理論といえば、コラッツ操作による有向グラフとしてなんかできないかなー、
と昔考えたけど、グラフ理論で扱われるのは有限頂点のグラフだった……

**１３２人目の素数さん** · 2018/04/28(土) 20:47:56.57

いや、まさにグラフ理論の木のつもりで書いたんじゃないか？

**１３２人目の素数さん** · 2018/04/28(土) 21:05:09.07

というか「木」は数学では同値類になるか。
自分が書くならこんな感じ。

関数 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)
は同値関係となる。

**１３２人目の素数さん** · 2018/04/28(土) 21:09:57.55

イメージは1を根とする木かな。
わからなくもないけど
・頂点が無限
・1→4→2→1のループがある
なのでなおさら木とは呼びづらい。

**786** · 2018/04/28(土) 21:23:20.77

確かに「木」だと誤解を招いてしまうかもしれませんね。
「束」のように複数の意味で使われる例もありますが…
良い名称を思いついたら変えようと思います。

**１３２人目の素数さん** · 2018/04/29(日) 00:40:21.09

うーん、やっぱり木が一番しっくりくる。
もうしばらく様子を見ます。

同値類を用いた定義も承知していますが、
一応高校数学の範囲で理解できるよう上のように定義しました。

あと、グラフ理論では無限個の頂点や辺を持つグラフも扱っていたと思います。

予想についての結果をひとつ追加。

命題
任意の木は 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 の倍数を含む。 □

**１３２人目の素数さん** · 2018/04/29(日) 01:27:39.57

ふーむ。
例えば同様の議論で他の倍数も通用したりするの？

**786** · 2018/04/29(日) 18:35:28.76

>>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 でも成り立つ。□

（続く）

**786** · 2018/04/29(日) 18:36:40.20

補題
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) となる。□

**１３２人目の素数さん** · 2018/04/29(日) 22:12:16.24

mod 5とか mod 7について何か出すのは難しいかもしれないけど
3^n-1についてとかなら何か出せるんだろうか？

**786** · 2018/04/30(月) 11:15:04.08

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

**786** · 2018/04/30(月) 11:45:54.34

偶数から奇数への帰着について先に書いておきます。

定理
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 が奇数の場合のみ考えようと思います。

**１３２人目の素数さん** · 2018/04/30(月) 22:46:03.02

>>1に聞いてみたいが>>786の実力はどれくらい期待できる？

**righ1113** ◆OPKWA8uhcY · 2018/05/01(火) 09:19:14.30

いや、自分よりすごい上だと思います。

**１３２人目の素数さん** · 2018/05/01(火) 19:50:11.04

ほほう、それは楽しみ

**786** · 2018/05/01(火) 19:52:19.63

>>808
いえ、それほどでも

個別の n, k について考えるだけならそれほどハードルは高くないと思いますので、
一緒に考えてくれる方がいたら嬉しいなと思います。
さしあたって次の目標は n=15, 19 あたりです。

**１３２人目の素数さん** · 2018/05/01(火) 21:00:47.74

予想
T を木とし、n, k を自然数とする。
このとき、ある a∈T が存在して a≡k (mod n) が成り立つ。

↑まだこれのイメージがわいてない段階だから一緒に考えるっつってもあんま期待すんなよｗ

**１３２人目の素数さん** · 2018/05/01(火) 21:53:00.73

まあ問題のとらえ方というか予想の立て方が、普通の人より高いところに目線があるんだろなって雰囲気は感じる。

**１３２人目の素数さん** · 2018/05/01(火) 22:30:43.98

予想がなかなかイメージ湧かないな～
プロローグでプログラムを組もうとしたときのような困難さを感じるorz.

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

とりあえず、プログラム組んで虱潰しで潰していけばn=15とかもなにがしかの結果が出るのだろうか？
そんな甘くない？

**１３２人目の素数さん** · 2018/05/01(火) 23:08:54.94

例えば>>1なら>>786の予想を理解して、しらみつぶしで探索するようなプログラムを、書けそう？書けなさそう？

**１３２人目の素数さん** · 2018/05/01(火) 23:19:15.11

プログラムでやろうと思ったら結局、原始根である必要があるんだろうか？
うーん。わからん。

**786** · 2018/05/01(火) 23:36:27.65

なるほどそんな感じですか…
ちょっと考えてみます

**１３２人目の素数さん** · 2018/05/01(火) 23:54:58.95

>>786はプログラム組める人なんですか？

**１３２人目の素数さん** · 2018/05/02(水) 00:04:01.57

x(2^n)-1→x(3^n)-1 (x,nは自然数)
がわかってるから、2か3が原始根ならどうとでもなる気が

**786** · 2018/05/02(水) 00:46:18.38

>>818
プログラムはド素人です。
上で言ったのは、「イメージがわかない」というのをどうにかできないかなーということです。

**righ1113** ◆OPKWA8uhcY · 2018/05/02(水) 11:48:19.30

>>815
いやー何ともいえないですねー

**786** · 2018/05/02(水) 17:55:20.98

この予想に至った経緯を図を交えて述べてみます。
そんな大層なものではないですが。

まず、木のイメージは次の図のような感じです。
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の倍数の場合だけ調べれば十分」
ということを考えたことがありました。

**786** · 2018/05/02(水) 17:55:49.20

それとは別に
・初期値が奇数の場合だけ調べれば十分
・初期値が 4n+3 の形の場合だけ調べれば十分
とかはよく見る話だと思います。

それで、この間ふと「これって一般化できないかな」と思ったのです。
すなわち「コラッツ予想は、初期値が n で割って k 余る数場合だけ調べれば十分」は成り立つのかと。
で、これを証明するにはどうすればいいかを考えた結果、
>>786の予想に落ち着きました。

**１３２人目の素数さん** · 2018/05/02(水) 19:26:48.28

>>821
なに守りに入ってんだよw

**１３２人目の素数さん** · 2018/05/02(水) 19:29:42.99

>>786は何かトリップ付けといた方がいいかもね

**１３２人目の素数さん** · 2018/05/02(水) 20:10:19.87

「コラッツ予想は初期値が3の倍数の場合だけ調べれば十分」
これはこのスレでも>>132で言及されているね

**１３２人目の素数さん** · 2018/05/02(水) 20:28:11.26

「コラッツ予想は、初期値が n で割って k 余る数場合だけ調べれば十分」

こっちのほうがアイディアはわかりやすいな

**１３２人目の素数さん** · 2018/05/02(水) 21:15:08.89

ん、「コラッツ予想は、初期値が n で割って k 余る数場合だけ調べれば十分」と>>786の予想が頭の中で微妙にすっきり繋がらないな
もうちょっと時間くれ

**１３２人目の素数さん** · 2018/05/02(水) 21:34:00.98

あ～なんかわかったかも

**１３２人目の素数さん** · 2018/05/02(水) 21:55:27.60

てことは例えば「コラッツの予想は5の倍数だけ調べれば十分」も証明済みってことか
へ～～

**１３２人目の素数さん** · 2018/05/02(水) 22:26:15.60

個別のnやkに対してどういう戦略で証明を進めていくのか説明してくれたらもしかしたらプログラムでしらみつぶし探索できるかもしれないな。
やや楽観的すぎるかもしれないが。

多分、>>1が実装してくれるｗｗ

**786** ◆5A/gU5yzeU · 2018/05/03(木) 00:08:17.82

>>819
確かに使えそうですが…いまいち使い方が思いつきません。
もし具体的なアイデアがあればお願いします。

>>825
ではお言葉に甘えて。

余談ですが、コラッツ予想の証明の方針として、
「1以外のどんな自然数もコラッツ操作によって自身より小さい数になる」
を示すというのが（多分）よく取られます。
例えば偶数や 4n+1 の形の奇数は自身より小さい数になることがすぐに分かるので、
「初期値が 4n+3 の形の場合に調べれば十分」
ということがわかります。

そして、この方針は>>786の予想とは全く別物だと私は思っています。
上の論法では任意の木に 4n+3 の形の数が含まれることは（多分）説明できていませんし、
逆に「任意の木に○○が含まれる」ということから「○○以外の数は自身より小さくなる」という話に繋げることもできないと思います。

このように、
「初期値が n で割って k 余る数の場合だけ調べれば十分」
を証明する方法は1つとは限りません。
>>786の予想はあくまでそのうちの一つの手段です。
たとえ>>786の予想の証明を諦めたとしても
「初期値が n で割って k 余る数の場合だけ調べれば十分」を諦めたことにはなりませんので、
そこらへん混同しないようお願いします。

次は n=5 の場合の証明を書こうと思います。

**786** ◆5A/gU5yzeU · 2018/05/03(木) 13:16:10.01

・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) なので、上の場合に帰着される。□

**786** ◆5A/gU5yzeU · 2018/05/03(木) 13:17:32.89

・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) の場合に帰着される。□

**786** ◆5A/gU5yzeU · 2018/05/03(木) 13:19:00.64

・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) に変えても証明できます。

**１３２人目の素数さん** · 2018/05/03(木) 13:21:26.72

むむう。
この感じだとプログラム化はかなり難易度高いかなぁ

**righ1113** ◆OPKWA8uhcY · 2018/05/03(木) 16:02:07.46

ふと思ったのですけど、プログラムとして
・T(1)を列挙
・a∈T(1)がa≡k mod nかを調べる
(kとnには具体的な数を入れる)
とかやっても意味ないですよね……

**１３２人目の素数さん** · 2018/05/03(木) 17:20:39.15

modを3倍にしていくのが基本戦略なのかな？

**１３２人目の素数さん** · 2018/05/03(木) 17:32:04.01

プログラム化は難しいと思うけど、
奇数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)がすべての奇数の集合と一致するかどうか、という問題はコラッツ予想と同じにならないかな？

**１３２人目の素数さん** · 2018/05/03(木) 17:40:34.30

証明が完成するまでmodに何回3をかけたかに注目したら何か出てくるかな？

**786** ◆5A/gU5yzeU · 2018/05/03(木) 17:56:31.46

>>837
うーん、そうですね…
k が既に 1 に到達することが分かっている数の場合、
a=k と取れてしまうわけですから調べる意味がなくなります。
wikipediaによると、5*2^60 までは 1 に到達することが分かっているそうなので、
k を 5*2^60 より大きくしないといけないことになりますが…

>>838
今のところそうですね。
まあ、やってみたら自然とそうなったという感じです。

**786** ◆5A/gU5yzeU · 2018/05/03(木) 17:58:47.10

>>840
あ、これはちょっと調べてみたいですね

**１３２人目の素数さん** · 2018/05/03(木) 18:03:43.93

プログラム組めるとデータ量が圧倒的に違うからなんとかしたいなあ

**１３２人目の素数さん** · 2018/05/03(木) 20:14:22.88

>>786がプログラム組めないのが痛いなあ
可能な限りシステマチックな手順に証明手順を落とし込めないですか？

**786** ◆5A/gU5yzeU · 2018/05/04(金) 00:22:45.95

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) を得る。

**786** ◆5A/gU5yzeU · 2018/05/04(金) 00:24:05.38

(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) を得る。

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

(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' の候補が残っていないので全ての操作を終了する。

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

操作だけをまとめます

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) と同様に、さらに再帰的に繰り返す。

**１３２人目の素数さん** · 2018/05/04(金) 01:15:28.20

おおお凄い
あんたプログラムの才能あるよ
まあ数学できる人はプログラムできても不思議じゃないけど
あとは>>1に任せたっwww

**786** ◆5A/gU5yzeU · 2018/05/04(金) 09:55:57.24

すいません、(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) 以降は再帰ではなく単なる繰り返しになります。

**786** ◆5A/gU5yzeU · 2018/05/04(金) 10:25:18.46

いくつか補足をば。

このアルゴリズムの正当性を説明するには、次の補題が必要です。

補題
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 が含まれるグループのみにして下さい。

**１３２人目の素数さん** · 2018/05/04(金) 10:47:29.12

>>1なら実装出来そう？
>>1が無理ならプログラム板にでもいって助っ人を探してくるけど

**righ1113** ◆OPKWA8uhcY · 2018/05/04(金) 10:54:18.15

>>852
やってみます。

**１３２人目の素数さん** · 2018/05/04(金) 11:06:01.81

おっさすが
頑張れー
工数はどれくらいかな
1週間位？

**righ1113** ◆OPKWA8uhcY · 2018/05/04(金) 11:10:02.62

>>854
それぐらい頂けるとありがたいです。

**１３２人目の素数さん** · 2018/05/04(金) 11:37:11.89

できればプログラムは計算過程を出力して
>>786が検証できるようにして欲しいな

**１３２人目の素数さん** · 2018/05/04(金) 15:57:32.57

ちなみにこのアルゴリズム素数限定らしいですが
合成数を入力したらどうなるんですかね
無限ループ？

**786** ◆5A/gU5yzeU · 2018/05/04(金) 17:00:03.61

>>1も>>852もありがとうございます。

>>857
素数に限ったのは>>851の補題があるから…と思っていたのですが、
よく考えたらこれ p が素数じゃなくても奇数なら成り立ちますね。
アルゴリズムの方も、素数に限らず奇数なら大丈夫な気がしてきました。

偶数を入れてしまうと、2倍写像が可逆にならないことにより
仮にプログラムがうまく動いたとしても証明になりません。

**righ1113** ◆OPKWA8uhcY · 2018/05/04(金) 17:42:36.90

今日は(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>

**１３２人目の素数さん** · 2018/05/04(金) 17:47:04.88

おお、乙です
感触はどうですか？
難易度たかい？

**righ1113** ◆OPKWA8uhcY · 2018/05/04(金) 17:51:58.20

難易度は、チョイ難しい、ってとこですかね～

**１３２人目の素数さん** · 2018/05/04(金) 18:09:38.72

n=19を手計算でやろうとしたら結構大変で中断w
根性なくてすまん

**１３２人目の素数さん** · 2018/05/04(金) 18:21:33.28

しかし>>786もプログラム覚えたらいいのに
メキメキ上達すると思いますよ？
便利だし

**786** ◆5A/gU5yzeU · 2018/05/04(金) 23:46:39.07

>>859
おお、なんか感動した。
ありがとう、続きもなにとぞよろしく頼みます。

>>862
いや、難しさを共有できるだけでもありがたいです。
n=19 の場合は 2 が原始根になるので A は
　A1={0}, A2={0以外}
の2つ、B も2つで得られない組は1つのみ、
それから C が3つ、という感じになるはずですがどうだったでしょうか。

2 が原始根かつ p≡1 (mod 3) のときは必ずこうなります。
ですが、この後それぞれの C を含む組が得られるか、という部分について一般的な理論がまだできていません。
プログラムを通じてその辺のヒントが得られればいいなと思っています。

>>863
いや、やろうとしたことはあるんですが、
プログラミングができる環境を得る方法がよく分からなくて断念した経験がありまして。
また試してみようかな

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

PCが一台あれば、無償アプリのどれかを使ってなんとかなりそうに思う

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

>>1のプログラム作成の進捗具合はどうですかね？
そろそろ本格的に難しい部分に差し掛かって手が止まってもおかしくないですが
>>1をみくびりすぎかな？

**righ1113** ◆OPKWA8uhcY · 2018/05/05(土) 19:32:02.22

>>866
今日は(5)まで作りました。
明日あたりやばそうですw

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

乙です
順調そうでなによりです

**786** ◆5A/gU5yzeU · 2018/05/05(土) 23:35:20.36

>>867
乙です。
重ね重ねありがとうございます。

>>805で挙げたものの証明が終わってないので
ちょっと進めときます。

・n が 5 以上の素数、Z/nZ において 2 が原始根、k≠0 の場合

まず、k=1,2,…,n-1 の場合は n=5 の場合と同様。

定理
T を木とする。p を 5 以上の素数とし、Z/pZ において 2 が原始根であると仮定する。
k を 1,2,…,n-1 のいずれかとする。このとき、ある a∈T が存在して a≡k (mod p) となる。

証明
n=5 の場合(>>833) と全く同様なので省略。□

これで>>805の残りは4つめと5つめですが、5つめはプログラムで確認できることなので
あとは4つめだけを書いていくことにします。
今日はちょっと時間がないので明日にでも。

**１３２人目の素数さん** · 2018/05/06(日) 13:40:43.22

新参です
コラッツ予想が解ける一歩手前でしたが一瞬寝落ちして表が消えた状態で上書き保存されて泣きそうです
証明はきわめてシンプルになります

**１３２人目の素数さん** · 2018/05/06(日) 16:04:17.20

>>870
表を早くつくりなおすんだ！

**786** ◆5A/gU5yzeU · 2018/05/06(日) 16:07:53.88

昨日の続き。
群論を使います。
Z/nZ の乗法群を (Z/nZ)* と書きます。

・n が 5 以上の素数、Z/nZ において 2 が原始根、k=0 の場合

素数であることを強調するために、n=p とおく。
概ね>>848,>>850のアルゴリズムに沿って進める。

まず (Z/3pZ)* における 2 の位数を求める。
(Z/3pZ)* は (Z/3Z)*×(Z/pZ)* に同型である。
(Z/3Z)*, (Z/pZ)* それぞれにおいて 2 の位数は 2, p-1 であるから、
(Z/3pZ)* における 2 の位数はそれらの最小公倍数 p-1 である。

(Z/3pZ)* の位数は 2(p-1) であるから、2 で生成される部分群 B1 の指数は 2 である。
(Z/3pZ)* の B1 による剰余類を {B1, B2} とおく。

さて、T を木とし、3 の倍数でも p の倍数でもない b∈T を任意に取る。
b を mod 3p で見た時に b∈B1 であれば、ある d∈N で
　b*2^d≡1 (mod 3p)
とできるので、あとは>>787補題(4)によって p の倍数を得る。

以下、b∈B2 とする。
射影 Z/9pZ→Z/3pZ による B2 の引き戻しを C とおく。
b を mod 9p で見ると b∈C である。
もし上と同様に>>787補題(4)を用いて B1 の元を得られれば、予想の証明が完了する。
式で表すと、
　b*2^d≡1 (mod 3) かつ (b*2^d-1)/3≡2^e (mod 3p)
を満たす d,e∈N が存在すればよいことになる。
これはまとめて一つの式で
　b*2^d-1≡3*2^e (mod 9p)　…①
と表せる。

①を満たす d,e が存在するかどうかを考える
ここから p≡1 (mod 3) か p≡2 (mod 3) かで状況が変わる。

**786** ◆5A/gU5yzeU · 2018/05/06(日) 16:09:14.44

定理
上の状況で p≡2 (mod 3) のとき、①を満たす d,e が存在する。
したがって、この場合>>786の予想が成り立つ。

証明
(Z/9pZ)* における 2 の位数を調べる。
(Z/9pZ)* は (Z/9Z)*×(Z/pZ)* に同型である。
(Z/9Z)*, (Z/pZ)* それぞれにおいて 2 の位数は 6, p-1 であるから
(Z/3pZ)* における 2 の位数はそれらの最小公倍数 3(p-1) である。

一方 C の要素の個数を考えると、
Z/9pZ→Z/3pZ の核が {0,3p,6p} であることから
　|C|=3*|B2|=3(p-1)
となり、これは 2 の位数と一致する。
C が 2 倍写像で閉じていることから、
C のどの2元も 2 を何回かかけることで互いに移りあう。

ここで、整数 c を
　c≡1 (mod 9) かつ c≡2 (mod p)
を満たすようにとる。
c が mod 9p で C に属することを確かめる。
そのためには、c が mod 3p で 2 の累乗で表せないことを示せばよい。
c≡2^m (mod 3p) と仮定すると
2^m≡c≡1 (mod 3) かつ 2^m≡c≡2 (mod p)
であるが、第1式より m は偶数、第2式より m は奇数なので矛盾。
したがって、c が mod 9p で C に属する。

**786** ◆5A/gU5yzeU · 2018/05/06(日) 16:10:09.58

C の2元は 2 を何回かかけることで互いに移りあうので、
方程式①の b を c に変えても解の有無は変わらない。そこで方程式
　c*2^d-1≡3*2^e (mod 9p)
を考える。この式が成り立つことは、mod 9, mod p で両辺が等しいことと同値。
c の取り方から、
　2^d-1≡3*2^e (mod 9) …②
　2^(d+1)-1≡3*2^e (mod p) …③
の共通解を探せばよいことになる。

②を解くと、
「d≡2 (mod 6) かつ e が偶数」または「d≡4 (mod 6) かつ e が奇数」
を得る。
前者の場合、d=6d'+2, e=2e' とおいて③に代入すると
　2^(6d'+3)-1≡3*2^(2e') (mod p) …④
となる。ここで、Z/pZ において 2 が原始根であることから、
2 の偶数乗であることと 0 でない平方数であることは同値。
さらに、2 の位数 p-1 は 3 の倍数でないから、2^3=8 も原始根である。
したがって、2^(6d') は 0 でない全ての平方数をとり得る。
2^(6d'+2) も0 でない全ての平方数をとり得る。
このことから、④は方程式
　2x^2-1≡3y^2 (mod p) …⑤
と同値である。同様にして、②の解が後者であった場合は
　2x^2-1≡6y^2 (mod p) …⑥
に同値である。

2 が原始根であるから、3,6 のいずれかは平方数である。
よって、⑤,⑥のいずれかは方程式
　2x^2-1≡y^2 (mod p)
に同値。これは x=y=1 を解に持つ。したがって元の①も解を持つ。□

**786** ◆5A/gU5yzeU · 2018/05/06(日) 16:11:07.90

p≡1 (mod 3) の場合も同様に考えると、
C が 3 つのグループに分かれてしまうため、考えるべき方程式が増える。。
計算は省略するが、この場合は次のようになる。

⑦ 3x^2+1≡8y^6 (mod p)
⑧ 6x^2+1≡32y^6 (mod p)
⑨ 3x^2+1≡32y^6 (mod p)
⑩ 6x^2+1≡4y^6 (mod p)
⑪ 3x^2+1≡2y^6 (mod p)
⑫ 6x^2+1≡8y^6 (mod p)
について
「⑦と⑧の少なくとも一つが解を持つ」かつ
「⑨と⑩の少なくとも一つが解を持つ」かつ
「⑪と⑫の少なくとも一つが解を持つ」
が成り立てば、①は解を持つ。

なお、解が見つからなかったとしても
上で書いたアルゴリズムのように次は Z/27pZ で考えて D を構成して…と進めることができる。

**righ1113** ◆OPKWA8uhcY · 2018/05/06(日) 16:36:10.03

今日は(7)まで作りました。残りは繰り返し処理です。
*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 0),(1,Just 0),(1,Nothing),(2,Just 1),(1,Just 1),(2,Just 0)]
(4) A' No. : [0]
C : [[5,10,17,20,34,40],[13,19,26,38,41,52],[31,47,55,59,61,62]]
(6) tuple : [(0,Nothing),(0,Just 1),(0,Just 0)]
(7) B' No. : [0]
*CollatzMod>

**righ1113** ◆OPKWA8uhcY · 2018/05/06(日) 16:38:47.09

現状のソースも貼っておきます。

import Data.List (nub, sort, findIndex, (\\), intersect)
import Data.Maybe (fromJust)

twoTimes :: Int -> Int -> [Int]
twoTimes x p = take p $ iterate (\y -> y*2 `mod` p) x

makeA :: Int -> [[Int]]
makeA p = nub $ map sort [nub $ twoTimes x p | x <- [0..p-1]]
makeB :: Int -> [[Int]]
makeB p = nub $ map sort [nub $ twoTimes x (3*p) | x <- [0..(3*p)-1], x `mod` 3 /= 0, x `mod` p /= 0]

findA :: Int -> Int -> Int
findA x p = fromJust $ findIndex (elem x) (makeA p)
findB :: Int -> Int -> Maybe Int
findB x p = findIndex (elem x) (makeB p)
findX :: Int -> [(Int, Maybe Int)]
findX p = nub [(findA x p, findB (3*x+1 `mod` p) p) | x <- [0..p-1]]

-- (4)A1,A2,…のうち、全てのBjとの組が得られていないものを調査
makeFour' :: Int -> Int -> Bool
makeFour' x p = [Just y | y <- [0..((length $ makeB p) -1)]] /= sort [v | (k, v) <- findX p, v /= Nothing, k==x]
makeFour :: Int -> [Int]
makeFour p = filter (\x -> makeFour' x p) [0..((length $ makeA p) -1)]

-- 組(A',Bj)が得られていないようなBj を見つける
makeCBefore :: Int -> Int -> [Int]
makeCBefore x p = [0..((length $ makeB p) -1)] \\ [fromJust v | (k, v) <- findX p, v /= Nothing, k==x]
-- Bjの元
makeCBefore2 :: Int -> Int -> [Int]
makeCBefore2 x p = concat [(makeB p) !! y | y <- makeCBefore x p]
makeC :: Int -> Int -> [[Int]]
makeC x p = nub $ map sort [nub $ twoTimes y (9*p) | y <- [0..(9*p)-1], elem (y `mod` (3*p)) (makeCBefore2 x p)]

**righ1113** ◆OPKWA8uhcY · 2018/05/06(日) 16:41:20.99

makeCAfter :: Int -> Int -> [Int]
makeCAfter x p
= concat [(makeB p) !! y | y <- intersect [0..((length $ makeB p) -1)] [fromJust v | (k, v) <- findX p, v /= Nothing, k==x]]
findC :: Int -> Int -> Int -> Maybe Int
findC x y p = findIndex (elem x) (makeC y p)
findY :: Int -> Int -> [(Int, Maybe Int)]
findY x p = nub [(fromJust $ findB y p, findC (3*y+1 `mod` p) x p) | y <- makeCAfter x p]

-- (7)B1,B2,…のうち、全てのCjとの組が得られていないものを調査
makeSeven' :: Int -> Int -> Int -> Bool
makeSeven' x y p = [Just z | z <- [0..((length $ makeC y p) -1)]] /= sort [v | (k, v) <- findY y p, v /= Nothing, k==x]
makeSeven :: Int -> Int -> [Int]
makeSeven y p
= nub $ intersect [k | (k, _) <- findY y p] (filter (\x -> makeSeven' x y p) [0..((length $ makeB p) -1)])

main = do
putStrLn ("素数pを入力してください")
pStr <- getLine
let p = read pStr :: Int
putStrLn ("Z/pZ : " ++ show([0..p-1]))
putStrLn ("A : " ++ show(makeA p))
putStrLn ("Z/3pZ : " ++ show([0..(3*p)-1]))
putStrLn ("B : " ++ show(makeB p))
putStrLn ("(3) tuple : " ++ show(findX p))
putStrLn ("(4) A' No. : " ++ show(makeFour p))
let q1 = 0 -- A' No.
putStrLn ("C : " ++ show(makeC q1 p))
putStrLn ("(6) tuple : " ++ show(findY q1 p))
putStrLn ("(7) B' No. : " ++ show(makeSeven q1 p))
-- 上記3行を繰り返し処理すれば良い
-- let q2 = 0 -- B' No.

**１３２人目の素数さん** · 2018/05/06(日) 16:59:28.35

>>876
乙です。
もうプログラムも完成間近か
予定を前倒ししそうな勢いですな。
素晴らしいことです。

**１３２人目の素数さん** · 2018/05/06(日) 17:07:57.99

意外と行数がすくないですがこれがHaskellのパワーなんですかね？

**righ1113** ◆OPKWA8uhcY · 2018/05/06(日) 17:15:25.28

>>880
そうですHaskellのチカラです。
1行で5コぐらい事をおこなっていて、高密度に圧縮されています。

**786** ◆5A/gU5yzeU · 2018/05/06(日) 17:32:23.25

>>876
乙です。
あれ、もしかして修正前のもので作ってる？
もしよければ>>850の修正バージョンでお願いしたいなーと

**１３２人目の素数さん** · 2018/05/06(日) 17:36:44.75

おおっとｗ　修正依頼来ましたかｗ
>>1ガンバ！ｗ

**righ1113** ◆OPKWA8uhcY · 2018/05/06(日) 17:40:56.75

>>882
あれ、修正前で作ってますかね?!
(7)が違うのかな～

**786** ◆5A/gU5yzeU · 2018/05/06(日) 17:45:56.96

＞(7)B1,B2,…のうち、全てのCjとの組が得られていないものを調査

修正後ではこの操作が不要で B' というものがそもそも現れないはずなので…
すみませんがよろしくお願いします。

**righ1113** ◆OPKWA8uhcY · 2018/05/06(日) 18:03:25.39

>>885
あれ～
了解ですっ

**１３２人目の素数さん** · 2018/05/06(日) 18:06:24.27

まあ開発にハプニングは付き物ですねｗ
それ込みで予定通りくらいですかね？

**righ1113** ◆OPKWA8uhcY · 2018/05/06(日) 18:28:36.71

>>887
まあなんとかなると思います。

**１３２人目の素数さん** · 2018/05/06(日) 19:30:01.21

>>1って前、グーグルドライブでファイル公開してたよね？
今回のファイルもグーグルドライブとかで公開してくれないですか？
インデントが消えてるのかなんなのか>>877-878コピペじゃ上手く動かないみたい。

**１３２人目の素数さん** · 2018/05/06(日) 19:48:44.04

UTF-8がどうとかいわれたので日本語けしてインデントつけたら動いたみたいです。
19を入力してみました。

$ ./collatz.exe
19
input num
Z/pZ : [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
A : [[0],[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]]
Z/3pZ : [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56]
B : [[1,2,4,7,8,14,16,25,28,29,32,41,43,49,50,53,55,56],[5,10,11,13,17,20,22,23,26,31,34,35,37,40,44,46,47,52]]
(3) tuple : [(0,Just 0),(1,Just 0),(1,Just 1),(1,Nothing)]
(4) A' No. : [0]
C : [[5,10,11,20,22,40,44,80,83,88,91,127,131,149,151,160,161,166],[13,23,26,37,46,52,67,74,79,92,97,104,119,125,134,145,148,158],[17,31,34,35,47,62,68,70,77,94,101,103,109,124,136,137,140,154]]
(6) tuple : [(0,Nothing),(0,Just 1),(0,Just 0),(0,Just 2)]
(7) B' No. : []

**１３２人目の素数さん** · 2018/05/06(日) 19:51:42.14

まあ、なんにしても>>786がこのプログラムを自分のマシンで動かせるところまではなんとか持っていきたいですねぇ

◆0wsjwd69zI · 2018/05/06(日) 20:08:57.95

一応酉
コラッツ数列について綺麗な法則性を見つけました
簡単な計算規則の適用で4→2→1ループまでの計算回数を半分以下にできます
早く完成させねば

**１３２人目の素数さん** · 2018/05/06(日) 22:03:49.10

>>786のPCってOSは何ですか？
Haskell動かせるようになってほしいんですが。

**786** ◆5A/gU5yzeU · 2018/05/06(日) 23:00:25.05

>>891 >>893
私としては今は証明を考えるのが楽しいので
プログラムはそのうち気が向いたら…ぐらいに思ってたのですが

一応OSはメインのPCが windows8.1, 他に windows10 も使える環境にあります。

あ、よく見たら>>890で n=19 が証明できてますね。

**１３２人目の素数さん** · 2018/05/07(月) 12:09:02.03

>>1のhaskell環境ってどうなってますか？
合わせられるならなるべくあわせたほうがいいよね？

**１３２人目の素数さん** · 2018/05/07(月) 12:16:14.19

できればこれを機にプログラムに目覚めてほしいw
まあ自分でプログラム書くところまでいかなくても
せっかく>>1がここまで頑張ったので
プログラム動かすだけでも試してほしいな

￥ ◆2VB8wsVUoo · 2018/05/07(月) 13:13:44.80

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 13:14:03.60

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 13:14:23.45

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 13:14:42.21

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 13:15:01.74

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 13:15:18.92

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 13:15:36.84

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 13:15:53.64

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 13:16:10.16

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 13:16:27.06

￥

**righ1113** ◆OPKWA8uhcY · 2018/05/07(月) 19:46:11.20

>>895
自分の環境はWindows10で、
Haskell Platform 8.0.2-a
GHC 8.0.2
です。
最新版のHaskell Platformでも問題ないと思います。

**１３２人目の素数さん** · 2018/05/07(月) 20:24:25.94

>>907
乙です。

>>890は>>1が書きかけのプログラムに19を食わせただけなのでちゃんと証明になってるかわかんないです。
証明になってるんですかね？

>>786はせっかく才能あるんだから食わず嫌いは勿体ないですよ！

￥ ◆2VB8wsVUoo · 2018/05/07(月) 20:45:11.83

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 20:45:30.60

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 20:45:50.08

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 20:46:09.68

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 20:46:27.95

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 20:46:46.28

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 20:47:07.74

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 20:47:28.98

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 20:47:50.11

￥

￥ ◆2VB8wsVUoo · 2018/05/07(月) 20:48:10.31

￥

**786** ◆5A/gU5yzeU · 2018/05/07(月) 21:18:34.19

>>908
嫌ってるわけじゃありません。興味もあります。
ただ、そもそも私はそういう話をしに来たんじゃなく、
もっとこう、ここまでの証明がいいとか悪いとか、
全く別のアイデアがあるだとか、この予想から何が分かるかとか、
そういう数学の話をしたくてここに来たんです。
その辺ノってくれる方はいないっぽいですかね…

>>890では B' の候補が無いと出力されているので、この時点でアルゴリズムが終了します。
　アルゴリズムが終了する⇒その n で予想が成り立つ
です。

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

まあ>>786がそういうなら無理強いはできませんね。

あと>>786が期待しているようなレベルの人は今はこのスレにはいないかもしれませんが、
スレが盛り上がってもっと人の目に留まるようになればあるいは凄い人が来てくれるかもしれません。

頑張って盛り上げていきましょう！

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

とりあえず、いまは>>1のプログラムが仕上がるのを待つ、ですかね。
データがそろったら新事実が見つかるかもしれないし。

**righ1113** ◆OPKWA8uhcY · 2018/05/07(月) 22:15:51.29

一日遅延ですがp=7が出来ました。
繰り返し処理は明日以降考えます。

*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 0),(1,Just 0),(1,Nothing),(2,Just 1),(1,Just 1),(2,Just 0)]
(4) A' No. : [0]
C : [[5,10,17,20,34,40],[13,19,26,38,41,52],[31,47,55,59,61,62]]
(6) tuple : [(0,Nothing),(0,Just 1),(0,Just 0)]
一度も現れなかったCi : [2]
D : [[31,47,55,59,61,62,94,110,118,122,124,125,157,173,181,185,187,188]]
(8) tuple : [(0,Nothing),(0,Just 0),(1,Nothing),(1,Just 0)]
一度も現れなかったDi : []
*CollatzMod>

**righ1113** ◆OPKWA8uhcY · 2018/05/07(月) 22:25:45.18

書きかけのコードはこちらです。
https://github.com/righ1113/CollatzMod/blob/master/CollatzMod.hs

ビルドする時は1行目をコメントアウトしてください。

**１３２人目の素数さん** · 2018/05/07(月) 22:29:45.96

ほほう、githubとはお洒落さんですな。

**786** ◆5A/gU5yzeU · 2018/05/07(月) 23:15:41.98

ノってくれる方がいない、は言い過ぎでした。
>>801や>>837などで、これまでも数学的な話はできています。
こういう意見を頂けるのは非常にうれしいし、返信を考えるのは楽しいです。
ついカッとなってしまってああいう言い方になってしまいました。

>>921
待つしかないなんてことはありません。
私は私でまた証明の続きを考えます。

>>922
おお、例と同じ結果になってる
乙です。

￥ ◆2VB8wsVUoo · 2018/05/08(火) 02:01:58.21

￥

￥ ◆2VB8wsVUoo · 2018/05/08(火) 02:02:27.80

￥

￥ ◆2VB8wsVUoo · 2018/05/08(火) 02:02:50.68

￥

￥ ◆2VB8wsVUoo · 2018/05/08(火) 02:03:12.91

￥

￥ ◆2VB8wsVUoo · 2018/05/08(火) 02:03:36.16

￥

￥ ◆2VB8wsVUoo · 2018/05/08(火) 02:03:58.30

￥

￥ ◆2VB8wsVUoo · 2018/05/08(火) 02:04:18.93

￥

￥ ◆2VB8wsVUoo · 2018/05/08(火) 02:04:40.45

￥

￥ ◆2VB8wsVUoo · 2018/05/08(火) 02:05:02.27

￥

￥ ◆2VB8wsVUoo · 2018/05/08(火) 02:05:25.15

￥

**１３２人目の素数さん** · 2018/05/08(火) 19:46:15.66

>>1が>>758で

1～nまででコラッツの反例がなければ、
n周期以下のループは存在しない　です。

ていうアイディアを出してたんだけど>>786の予想から繋げて何か言えないかなーと妄想中

**１３２人目の素数さん** · 2018/05/08(火) 20:06:46.16

仮に1を含まない木が存在したとして、さらにその木がループを含むと仮定し、
かつコラッツの予想がnの倍数だけ調べればいいとすれば何か言えそうな気がするが
いまのところ気がするだけｗ

**righ1113** ◆OPKWA8uhcY · 2018/05/08(火) 22:30:58.28

いちおう出来ましたが、あやしいです。
p=21で止まってしまうのです。
ログをつけましたので、見ていただけないでしょうか。

https://github.com/righ1113/CollatzMod

**786** ◆5A/gU5yzeU · 2018/05/08(火) 23:09:08.43

>>938
乙です。
見てみます。

**１３２人目の素数さん** · 2018/05/08(火) 23:14:21.71

21は3の倍数だからってのは関係ない？

**786** ◆5A/gU5yzeU · 2018/05/08(火) 23:40:03.65

見たところ48行目までは正常に動いてるっぽい。
確かに49行目が怪しいですね。
46行目で 0,1,2,3 番目の C に対して組が得られているので、
本来なら (0,Just 0) などが出力されるところだと思います。

例えば33行目でDを扱った後に何かがリセットされてない…とか？

**righ1113** ◆OPKWA8uhcY · 2018/05/09(水) 00:10:26.53

>>940,941
ありがとうございます。
ペアが空っぽというのは無いのですね。
明日は午後が空くので、そこで見ようと思います。

**righ1113** ◆OPKWA8uhcY · 2018/05/09(水) 17:27:09.70

>>938
直したと思います。
昨日の場所にログを置きました。

と思ったらp=73でまたしてもバグが！
配列のインデックスをオーバーとかこうとか……

プログラム、普通には動くと思いますので、　僕はマイペースでバグ取りしたいと思います。

**１３２人目の素数さん** · 2018/05/09(水) 18:25:58.87

おお、>>1乙です

**１３２人目の素数さん** · 2018/05/09(水) 20:39:28.35

ちなみに73と言うのはどこから来たの？
100くらいまで全部計算まわしたの？

**righ1113** ◆OPKWA8uhcY · 2018/05/09(水) 20:47:14.93

>>945
7以上の奇数を順番に見ていって、
73でバグに当たりました。

**１３２人目の素数さん** · 2018/05/09(水) 20:54:40.23

藤林丈司

**１３２人目の素数さん** · 2018/05/09(水) 22:28:37.28

おれもバグ取り協力したいけどアルゴリズムも十分理解してないしhaskellも十分理解してないからダブルで難しいorz

**１３２人目の素数さん** · 2018/05/09(水) 22:54:26.36

それにしてもまだバグがあるかもしれないけど5以上71以下の奇数で全部>>786予想が成り立つってこと？
けっこう凄くね？

**righ1113** ◆OPKWA8uhcY · 2018/05/09(水) 22:57:34.50

>>943
バグ直ったかも。
でも家のPCのネットワーク系がダメになってしまったので、
GitHubは更新できません。

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

まじで

**righ1113** ◆OPKWA8uhcY · 2018/05/09(水) 23:36:49.21

>>950
家のネットが一時的に直ったのでGitHub更新しました。

これにて完了?かな?

**１３２人目の素数さん** · 2018/05/10(木) 00:04:24.40

>>1乙です
手間じゃなければ例えば100以下の奇数に対してとかの実行結果もGitHubに上げてほしいです。
そうすれば>>786とか他の人も参照できるだろうし。

**１３２人目の素数さん** · 2018/05/10(木) 00:15:42.09

まあそれよりも>>786のOKをもらうのが先ですかね？

**786** ◆5A/gU5yzeU · 2018/05/10(木) 00:32:43.38

いやー手計算でn=19とかでひーこら言ってるところにあっさり73とか言われると
さすがにプログラムの力を思い知らされますねえ。
>>1乙です。
p=21 は大丈夫そうですね。p=73 はあとでじっくり見てみます。

>>949
証明できたことは凄いですけど、
「予想が成り立つのが凄い」という意味で言ってるんであれば、
それは全然不思議ではありません。

というのも、>>786で書いた通り
　この予想が成り立たない⇒コラッツ予想が成り立たない
なので、簡単に反例が見つかる方がおかしいのです。

**righ1113** ◆OPKWA8uhcY · 2018/05/10(木) 00:42:26.14

>>955
ところで、「全てのn,kでa≡k (mod n)が成り立つ→コラッツ予想は真」
って証明あるのですか？
あるなら見てみたいです。

**786** ◆5A/gU5yzeU · 2018/05/10(木) 00:51:20.30

>>956
うーん、ないですね。
それは成り立たないんじゃないかと思っています。
もし成り立つなら、>>786はコラッツ予想と同値になるので一気に>>786の重要度が増すんですがｗ
逆であれば、>>786に書いた通り成り立ちます。

**righ1113** ◆OPKWA8uhcY · 2018/05/10(木) 00:56:11.87

そうですかー残念です……

**righ1113** ◆OPKWA8uhcY · 2018/05/10(木) 10:03:31.78

「コラッツ予想は、初期値が n で割って k 余る数場合だけ調べれば十分」
というのは、初期値が1になるまで調べるのか、
初期値が自身より小さくなればOKなのか、
どちらだろう？

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

nは奇数に限るのかな？
8m+5と2m+1は同じ数に移るから8m+5(n=8,k=5)は調べなくて良い、のような例はあるんじゃないかな

**１３２人目の素数さん** · 2018/05/10(木) 12:04:57.68

n=pとn=qで予想が成り立つ＝> n=pqで予想が成り立つ
が言えたら面白そう

**786** ◆5A/gU5yzeU · 2018/05/10(木) 18:30:14.35

>>959
1になるまで調べる、ですね。
実際に一つずつ調べるんであれば、もちろん「既に調べた数が得られるまで」とするのが自然かと思います。

>>960
奇数だけ扱っているのは、>>806によって偶数は奇数に帰着されるからです。
8m+5 と 2m+1 は両方とも 3m+2 に移るから 3m+2 を調べれば十分、という具合です。

>>961
これが言えれば素数だけ示せばよくなるのでだいぶ楽になりますね。
n=p, n=q と n=pq の間に何かしら繋がりがありそうな感じはしますが、まだよく分かりません。

**１３２人目の素数さん** · 2018/05/10(木) 18:45:17.78

プログラムの実行結果からn=p,n=q,n=pqの関係を考察できそう？

**１３２人目の素数さん** · 2018/05/10(木) 19:48:27.73

やっぱプログラムの実行結果公開してほしいなぁ。
>>1頼んます。

**righ1113** ◆OPKWA8uhcY · 2018/05/10(木) 20:00:51.88

5以上100以下の奇数とか、やってみます？

**１３２人目の素数さん** · 2018/05/10(木) 20:01:52.46

>>965
そうですね。とりあえずそれで。
頼んます。

**righ1113** ◆OPKWA8uhcY · 2018/05/10(木) 20:46:51.95

83までとさせてください。
https://github.com/righ1113/CollatzMod/blob/master/p%3D5to83.txt

**１３２人目の素数さん** · 2018/05/10(木) 20:50:34.18

おお、仕事速いすな。
乙です。
さてここから何か見つかるか…

**１３２人目の素数さん** · 2018/05/10(木) 20:56:15.68

うーん。
パッと見では法則は見えないですな。
まあそりゃそうか。

**１３２人目の素数さん** · 2018/05/10(木) 21:01:05.73

３の倍数が比較的計算長くなるのかな？