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:132人目の素数さん
18/05/16 23:38:41.29 Ux+htuCY.net
mod 4 ですか? 意外な数字がでてきましたね。
まあ、証明を楽しみに待ちます。
53:132人目の素数さん
18/05/22 10:07:26.93 WVNRebn9V
>>51
> mod 4 ですか? 意外な数字がでてきましたね。
n mod 4 が 3 の場合に帰着するので、わりと順当な話だろうと思われる。
任意の偶数が「2で割りつづけると奇数に到達する」というのも自明。
問題なのは、「任意の奇数を『3倍して1を足す』と、12で割って8余る偶数」
に到達するという上に向かうルートがあるのだが、
その一番下の奇数の性質とか、ルートの長さとか場所とかの分布が
なかなか追いきれないという点だ。
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:132人目の素数さん
18/05/20 17:38:06.32 faL44BH0.net
ぬおー複雑すぎてついていくのがしんどいorz
平方数がどうとかいうのは群論でも普通によく使われるテクニックなんですか?
64:前786
18/05/20 18:16:56.14 Cf9ohYZi.net
>>62
群論というより、どちらかというと整数論ですかね。
少なくとも自分はよく使います。
65:132人目の素数さん
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:132人目の素数さん
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:132人目の素数さん
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:132人目の素数さん
18/05/21 22:24:15.94 4VRAtjed.net
>>69
おお、ありがとうございます。
群に関して解説しているお勧めページありましたら教えてください。
72:132人目の素数さん
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:132人目の素数さん
18/05/21 23:45:47.55 4VRAtjed.net
ありがとうございます。
1から勉強だなこりゃ
76:132人目の素数さん
18/05/22 20:15:30.49 GnlOeguJ.net
私が勉強追いつくのは結構時間かかると思うのでスレは自由に進めてくださいねw
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) 縦2マス横 (p-1)/2 マスのマス目を考え、図のように3色で塗り分ける。
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) 3色とも少なくとも1つのマスに印がついていれば予想が成り立つ。
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:132人目の素数さん
18/05/23 12:01:38.73 m0d+bsHd.net
整数論関係で盛り上がっているところで申し訳ないのだが、
二進数表記で ON ビットが二個以上連結すると、
上(偶数に向かうシークエンス)というのが、
ON ビット n に対して n - 1 個連続する。
2の倍数を XY 座標の の X に取るとすると、
偶数は、「2で割る」操作のどっかでシークエンスに引っかかる
(つーか、奇数になる)。
コラッツ操作がカオティックな挙動をするというのは、
「3n+1の結果が奇数でありつづける」(つまり、下位のビットが
ON でありつづける)と、「2で割り続ける」と、「偶数は割り続けると、
どこかで奇数になる」という、周期3のループに引っかかっている
せいではないかという気がしてきた。
「3n+1」で無限大に発散することはありえない
(メルセンヌ数との関連で、それは自明)。
つーことは、「下位がオンビットの値(奇数)で受けとめきれない」
偶数があるかどうか、みたいな話になりそうな気がする。
83:righ1113
18/05/23 19:18:42.10 l+nV4t+w.net
>>81
> 「3n+1」で無限大に発散することはありえない
>(メルセンヌ数との関連で、それは自明)。
詳しく知りたいです。
84:132人目の素数さん
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 のみではないビット列が並んでいる」からだ。
そこに、「三倍して1を足す( 3n + 1 )操作」を繰り返すと、「2^p + (2^( p + 2) × q)」の部分に「三倍して2を足す」操作を p 回繰り返すのと同じことになる。
その間、「2^p + (2^( p + 2) × q)」の桁数が増えた結果、そのビット列に p 個以上の 1 が現れて、元の p よりも数が増えると、これは発散してしまう恐れがある。
実際に、それらしい例はある。 31 の場合、31 - 47 - 71 - 107 - 161 の列から 319 - 479 - 719 - 1079 - 1619 - 2029 を経る場合がある。
ただ、これが「無限に連鎖するか?」という話になると、「メルセンヌ素数は無限に存在するか?」みたいな話になるので、「今のところ、わからん」と言うしかない。
とりあえず、「すべての自然数が、コラッツ操作によって p と q の網(木)に引っかかるか?」を考えている。
ただ、「三倍して1を足す( 3n + 1 )操作」の回数は、 p を超えることはないことが判っている。
85:132人目の素数さん
18/05/23 20:40:42.01 m0d+bsHd.net
× > そのビット列に p 個以上の 1 が現れて
〇 > そのビット列に p 個以上連続した 1 が現れて
86:132人目の素数さん
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:132人目の素数さん
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:132人目の素数さん
18/05/24 10:37:42.13 hntPmxCh.net
また通りすがりのプログラマが覗きにきました。お邪魔します。
「奇数 →(奇数 →)6で割って2余る偶数 → 奇数」
というループに乗っていないのは1だけ。
「奇数 → 偶数」というルートを通らないのは2の冪乗数だけ。
それ以外で、“ループ�
93:ナはない”「奇数 → 6で割って2余る偶数 → 奇数」という “ルート”に乗って“いる”のは2の冪乗のうち「6で割って2余る偶数」だけ。 つまり、ここから先は、上記の条件に引っかからない「6で割って2余る偶数」と 「奇数」だけを考えればいい。 ここからは、単純に上記の条件に引っかからない「6で割って2余る偶数」と 「奇数」だけを考えればいいような気がする。 このあたりから始めて、「コラッツ操作を根っこのほうから逆に辿って、 枝がどう伸びているか」を逆に辿ってみようとしているのだが、 辿ってみた結果を どう整理したらいいのかが、正直わからん。484 と 485 とか、 変なところでニアピンしてる奴がいるんだよなぁ(どっちも3ステップ後に 182 を通る)。 これは三次元表示とかを考えたほうがいいのかね? 映像として見ることで、 なんかしらの法則性が見えてくるということも あるわけだし。
94:righ1113
18/05/24 17:50:33.60 Ht7/ViD0.net
>>91
「6で割って2余る数 」か「奇数 」かたっぽだけ調べれば良いような気がします。
画像表示はカオティックなものしか得られずにう~ん……という感じです。
95:132人目の素数さん
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:132人目の素数さん
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:132人目の素数さん
18/05/24 20:52:34.74 c3neDLsf.net
可視化はいいけどどうやって可視化するかはアイディアあんのか?
3次元表示だけじゃ具体性に乏しい。
101:前786
18/05/24 21:45:42.25 COzmyM7A.net
>>94
とりあえずこの出力結果は間違ってなさそうです。
詳細は後ほど。
102:righ1113
18/05/24 22:08:44.37 x3TjQ3yB.net
おお~~
103:132人目の素数さん
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:132人目の素数さん
18/05/25 05:24:49.37 FB8NYZZI.net
>>98
n が 127 以下については、手で描いてみた(A4 の 5mm 方眼紙四枚とか)。
以前誰かが書いてたように、「場合分けが面倒臭いことに
なって手に負えなくなる」という感じのある錯綜したケース
(確かに127 以下はけっこうややこしい)を脱して
ある程度規則性が見えてくるのは、ここより先
(255 とか 1023 とか 2047 とか)らしいんだよね。
そうすると、もう手描きだと追いつかなくなるのと、関係が錯綜して
見づらくなる(つーか、局所的な関係はわかるんだが、全体像が
把握できなくなる)ので、「2で割る」「3n + 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:132人目の素数さん
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:前786
18/05/26 00:55:24.03 PVjl5sK1.net
「コラッツ逆操作だけ」というのがそれほど強い制限でないという話。
まず、コラッツ逆操作では操作 3 を行うか操作 4 を行うかで分岐が起こりますが、
コラッツ操作では分岐は起きません。
なので、例えばある数にコラッツ逆操作を行ってからコラッツ操作を行うと、元の数に戻ることになります。
予想を証明するには、
「ある数 a からコラッツ操作、コラッツ逆操作を繰り返してある数 b にたどり着けるか」
を考える必要がありますが、上記のことから
「ある数 a から何度かコラッツ操作を行い、その後何度かコラッツ逆操作を行うことである数 b にたどり着けるか」
という道筋だけ考えればいいということになります。
そうすると、コラッツ逆操作だけを考えるというのは大体、操作の後半だけを考えるということになります。
これが強い制限と思うかどうかは人それぞれですが、
実際にこれまでは多くの場合にうまくいっているので、大した制限じゃないのだろうと私は思っています。
114:前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 の倍数でもない数が含まれる。
(元々は奇数でなく素数としていたが、全く同じ証明で奇数の場合も示せる)
ではコラッツ操作を用いています。
115:righ1113
18/05/26 05:32:28.98 c0tJyFtX.net
通常のコラッツ予想3x+1ですが、
①プログラムが無限走行→オールNothing出る
(Cを繰り返すと集合が1つになる事が使えないか)
②オールNothing出ない→プログラムは停止
③全てのnでオールNothing出ない(難しい?)
④全てのnでプログラムは停止する
というのを考えたのですが、
実際証明するとなると難しいですかね。
116:132人目の素数さん
18/05/26 06:33:58.67 SzRdqnm/.net
また邪魔なプログラマが通りますよ
コラッツ逆問題(3n+1版。「1 から出発して、すべての自然数に
到達できるか」)について、「(有限な)すべての偶数は、2で割り続ける
ことによって奇数に帰着するので、奇数についてだけ証明できれば足りる」
のは確か。
逆コラッツ操作は、
1)nを2倍する。
2)nを二倍して1を引いたものが3で割りきれるなら、それ(2n-1)を
3で割る。
が可能。
で、このとき、「nが3で割りきれる場合は、(1)の操作によって
『nを二倍して1を引いたものが3で割りきれる数』が出てこない」ことが
判っていて、nの偶奇によらず(1)の操作の結果は偶数になるので、けっきょく
奇数は出てこないことがわかる。
(2)に対応する正のコラッツ操作は、結果的に「nを二倍して1を引いたものが
3で割りきれない数」に「2n+1」操作を繰り返して「6で割って2余る偶数」に
至る“縦のルート”(有限長の上下のルート)を描くことであり、このとき(nの
偶奇によらず)3の倍数が出てきたときは逆コラッツ操作の
(1)(“右へ向かうルート”。こちらは際限なく右に延長できる)は
考慮しなくていい。
なお、“縦のルート”は、最下位ビットが「2個以上の連続するオンビット」である
状態と関連している。
この制約条件のもとで、「1を出発点として、すべての奇数に到達できるか?」が、
コラッツの逆問題となる。
で、「最下位のオンビットが連続しない」数は、「4で割って1余るn」であり、
それが正のコラッツ操作(2)によって「6で割って2になる数」に変換されるはず
だから、それを満たす数について考えればいい ― ような気がする。
だけど、コラッツ予想に関する議論で「mod 12」って話が出てきたのを
見た記憶がオレにはないんだよな (-_-!)。
これって、オレが なにか盛大な勘違いをしているってぇコトなのか?
117:righ1113
18/05/26 15:26:37.54 R0apbE/z.net
>>114
>「nを二倍して1を引いたものが3で割りきれない数」に「2n+1」操作を繰り返して「6で割って2余る偶数」に至る“縦のルート”
ここが分かりません。
具体的な一連の数とかありますか?
118:132人目の素数さん
18/05/26 17:07:34.51 SzRdqnm/.net
>>115
とりあえずこんな感じかな?
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
詳細は のちほど。
119:132人目の素数さん
18/05/26 17:11:05.80 SzRdqnm/.net
つーか、「コラッツ操作」ということを考えたら、
「->」じゃなくて「<-」のほうが判りやすかったかも。
あ、「3n + 1」じゃなくて、「(3n + 1) / 2」で
表示してるのは、このスレを見てるような人だったら
察してくれるよね?
120:132人目の素数さん
18/05/26 17:16:10.29 SzRdqnm/.net
言うまでもないけど、
“☆”がついている値は、
「3の倍数なので、2 の冪乗を掛けても
『2n - 1 が 3 で割りきれる数にならんので、
下に延びる枝(3n + 1 操作の逆操作)がない枝』」
っちゅーことです。
121:righ1113
18/05/26 17:54:29.76 R0apbE/z.net
>>116-118
>>114は大体理解できました。mod12は分かりません。
> で、「最下位のオンビットが連続しない」数は、「4で割って1余るn」であり、
>それが正のコラッツ操作(2)によって「6で割って2になる数」に変換されるはず
>だから、それを満たす数について考えればいい >― ような気がする。
例えば17を見ると、4で割って1余る。
コラッツ操作(2)で26になって、6で割って2余る。
しかし17を2倍して1引いた数が3で割りきれてしまう。
コラッツ操作(2)に違反していると思うのだけど、こういう数はどう処理するの?
122:132人目の素数さん
18/05/26 18:02:39.81 SzRdqnm/.net
>>115
ごめん。
>(2)に対応する正のコラッツ操作は、結果的に「nを二倍して1を引いたものが
3で割りきれない数」に「2n+1」操作を繰り返して「6で割って2余る偶数」に
至る“縦のルート”(有限長の上下のルート)を描くことであり、
っつーのは、
>(2)に対応する正のコラッツ操作は、結果的に「nを二倍して1を引いたものが
3で割りきれない数」に「(3n+1)/ 2」という操作(←ここ重要)を繰り返して「6で割って2余る偶数」に
至る“縦のルート”(有限長の上下のルート)を描くことであり、
という意味だ。
とりあえずツッコミは歓迎なのだが、いまは遠山 啓先生の『初等整数論』で
理論武装中なので、殲滅的攻撃は勘弁してくれいm(_ _)m。
123:righ1113
18/05/26 18:19:59.67 R0apbE/z.net
>>120
すみません、つい熱くなってしまって……
124:132人目の素数さん
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コードとか乱数生成とか、リクツは判らんでもないけど、
原始多項式うんぬんとか言われても、正直な
125:話、小分かりがせんのよ」 みたいな感想がある。 そもそも「Z/pZ」っつーのが、「演算を定義せんと意味がねぇ」みたいな 話があって、よくわからん(加法なのか乗法なのかとか)。 せっかく大勢の人が見てくれているのだから、「数学的に厳密な記述」 ではない「わかりやすい説明」(まぁ、「『分かりやすい説明』は、 嘘の温床だ」という意見は確かにあるのだが)っつーのも 試みてくれんか。このスレで(見ているだけの奴もいるし、 書いている奴もいるわけだが)“解っている” 人間も 少なかろうと思うので。
126:132人目の素数さん
18/05/26 18:35:17.86 SzRdqnm/.net
>> 119
> すみません、つい熱くなってしまって……
いや、熱くなるのはまったく問題ないので、「こちらこそ、数学の門外漢が
半煮えの議論を持ち出してすまん m(_ _)m」とお詫びしたい。
とはいえ、実験数学が未解決問題の解決に貢献することもあるし、
「素人目線からの、視覚化だのなんだの」が有効なことが あるのだ。
数学屋さんには数式という武器があり、
電算屋にはプログラミング言語という武器がある。
(個人的に Wolfram は気に入らないが)Mathematica みたいに
その間を繋ぐツールもある。
とりあえず「共通の土俵」っつーのを用意したいと思う。
127:132人目の素数さん
18/05/26 19:04:19.46 mODZs90x.net
具体的にプログラム言語は何使えんのよ?
128:132人目の素数さん
18/05/26 19:04:56.28 mODZs90x.net
ちなみに>>1はhaskell使いらしい
129:132人目の素数さん
18/05/26 19:52:05.47 SzRdqnm/.net
>>124
> 具体的にプログラム言語は何使えんのよ?
わしゃぁのう、年寄りじゃけん、本当はアセンブラしか解らんのじゃ。
じゃけんども、C とか LISP とかは、理屈がよう分るんじゃ。
Pascal は、P-system があったんで、Java んような「中間言語」とか
「仮想マシン」っちゅーたらコンセプトは分らんでもないんじゃ。
年取ったけん、IDE がなけりゃプログラムなんぞ書けんように
なってしもうた。
そんなわけで、ようやく Java を使ってなんとかプログラムを
書いとるんじゃ。
ごめんつかぁさい。
130:132人目の素数さん
18/05/26 20:15:39.62 mODZs90x.net
中身のある話振ってくれるなら歓迎するけどね。
アイディアがあるなら具体的に頼む。
131:132人目の素数さん
18/05/26 20:56:17.99 SzRdqnm/.net
>>127
> アイディアがあるなら具体的に頼む。
ありがとう。
生煮えなので申し訳ないのだが、右(2の冪乗)から来る
値は、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
< ペントミノ < 四色問題 と並べてみると、組合せ的な話であれば
ペントミノ程度の話なんじゃねーかと思ってるワケですよ。
ただ、「どういうコンセプトで捉えたら、数学的かつ計算器数学的な
問題に落とせ
132:るか」っていう切り口がわからんのよね。 そんなわけで、「アイディアがあるなら具体的に頼む。」という問いには、 「こっちが知りてぇよ」と応えざるを得ない。済まぬ m(_ _)m。
133:132人目の素数さん
18/05/26 22:12:44.62 mODZs90x.net
逆にxn+1問題で無限大に発散する場合もあるxを探すというのは?
134:132人目の素数さん
18/05/26 22:44:42.03 9vYDmViG.net
コラッツ予想をセルオートマトンで可視化する事を試してみました。
URLリンク(dotup.org)
キーは3nplus1です。
大まかに4つのパターンを図示してみました。
1)完全にランダムなパターン
2)1のビットが長く続くパターン(2^n-1)
3)最下位ビットと最上位ビットの間が0のビットで隔てられてるパターン(2^n+1)
4)1のビットが長く続き、さらに離れて最上位ビットが存在するパターン((2^n+1)*2^m-1)
最下位ビットが0の行は赤に塗ってあります。
プログラムに間違いがあればすいませんが、結構興味深い遷移がみられました。
135:132人目の素数さん
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:132人目の素数さん
18/05/26 23:26:44.26 mODZs90x.net
整数をビット列とみなして考えるのは>>1がかなりやってたから>>1の意見を聞きたいね。
まあ、この程度の成果では驚きはないだろうけど。
137:132人目の素数さん
18/05/26 23:31:56.87 mODZs90x.net
結構きれいな絵だけどきれいなものだけ抜き出したの?
よくわからんが全部きれいになるならもしかして凄いのかな?
138:132人目の素数さん
18/05/27 00:11:19.66 PUTG2O+S.net
>133
綺麗なパターンが出る値を選んでます。
大抵は増えて減ってを繰り返すパターンになると思いますが、その出現に規則性が見られるように思えます。
まぁ勘違いかもしれないんですが orz
139:132人目の素数さん
18/05/27 07:33:04.20 hLMSuDSm.net
>>131
「最下位ビットから2ビット以上1が連続した場合」については、
以下のようなことを考えたことがある。
「ここで、新たな操作を追加する。
(3)n' = 3n + 2
である。
たとえば "11101" のように、左に '1' が二個以上連続した部分(m 個)が
あるとする。これを、m - 1 個の '1' と '1' に分ける。 "11101" だったら
"11" と "101" だ。このとき、"11101" は、"**"と「 "101" に(3)の操作を
二回施した結果」で表される。
"11" -> "*" + "101"
"111" -> "**" + "10001"
"1101" -> "*" + "10001"
"1111" -> "***" + "101011"
"11001" -> "*" + "10111"」
その他の悪戦苦闘っぷりは
URLリンク(animaleconomicus.blog106.fc2.com)
を参照されたい。
140:132人目の素数さん
18/05/27 08:58:45.44 hLMSuDSm.net
逆コラッツ操作を行なうプログラムの中で、ずっと
「nを二倍して1を引いたものが3で割りきれたら3で割る」
とかいうロジックを使っていたのだが、よく考えたら
「nを3で割って2余る」(n ≡ 2(mod 3))でよかったことに、
いま気づいた。
2*(m + 2) - 1 = 2m + 4 - 1 = 2m + 3
なんだから、3|m(「m が 3 で割切れる」あるいは「m は 3 の倍数」。
遠山 啓さんの『初等整数論』のスタイルだと「3)m」)なら
当たりまえじゃん(だから数学は苦手なんだと(ry)。
そうすると、
1)nを3で割って2余るなら、二倍して1を引いてから2で割る。(それが終わったら、次にnを二倍して右を探す)
2)nを3で割って1余るなら、右に逃げる(nを二倍して右を探す)。
3)nが3で割りきれるなら、下には行けないし右側にも奇数へ向かう枝が出ないので、ひとつ前(根に近い数)に戻る。
という操作で再帰をかければ、「逆コラッツ操作で出てくる奇数の木を探索する」ことができるはずだ。
こうなったら奇数偶数関係ねぇじゃん。orz
141:132人目の素数さん
18/05/27 13:50:43.81 OB+BVTS7.net
個人的最近色々とデータをいじっているんだが、1になるまでの回数にちょっとした発見があるんだけど需要ある??
142:132人目の素数さん
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:132人目の素数さん
18/05/27 17:28:34.65 hLMSuDSm.net
>>137
> 個人的最近色々とデータをいじっているんだが、1になるまでの回数に
> ちょっとした発見があるんだけど需要ある??
>>138
> あとは逆コラッツとフィボナッチの関連性や、n 次のコラッツ、コラッツに群の
> 導入などなど
ここは、たぶん「『需要ある??』とか、つまんねぇ遠慮なんかしてるんじゃねぇ! さっさと晒せよ!」
…… っつースレですから。燃料を投下していただければ、いくらでも。
145:132人目の素数さん
18/05/27 19:19:29.97 Eccfjv+j.net
スレがにぎわい始めましたね。
あとは>>786の議論についていけるレベルの人が来てくれればいい感じなのですが。
146:132人目の素数さん
18/05/27 19:52:38.57 hLMSuDSm.net
>> 139
> あとは(前スレの)>>786の議論についていけるレベルの人が来てくれればいい感じなのですが。
つーても、数学板は敷居が高いのよ。
前スレの >>8 の
> 最初に偶数はアウト(1に収束)
> 4の倍数になったらアウト
っつーのも、
×「最初に偶数はアウト」
〇「最初に2の冪乗数はアウト」(つーか、2で割り続ければ奇数に帰着するので、
奇数について証明できればオッケー。てなワケで「4の倍数になったらアウト」と
いうのも、ここに帰着)
とかいったツッコミ(つーか、解説)を誰かしてくれよ、みたいな話にはなる。
むしろ、素人目線の解説を丁寧に してくれるヒトがいてくれると、もっと盛り上がる
ような気がするのだが。
147:132人目の素数さん
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 倍すると、右上のマスに移ります。
ただし、各ブロックで左右の端、上下の端は
150:それぞれつながっています。 https://i.imgur.com/bvi0vDc.jpg 図は一部のみ示していますが、どの矢印も 2 倍を表しています。
151:前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)
よって、緑グループのみ得られます。
152:前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の通りになります。
153:132人目の素数さん
18/05/28 06:02:47.38 DIMEHMYY.net
>>131 と >>134 から、なんとなく証明への道筋らしきものが見えてきた。
もちろん“道筋らしきもの”なので、完璧な証明に到達できるかどうかは別の話なのだが。
まず、ごく初歩的な話だが、「メルセンヌ数」の話をしておく。「メルセンヌ数」を「メルセンンヌ素数」だと思っているような人は
数学板にはいないだろうが、「素数であるメルセンヌ数」が「メルセンヌ素数」で
あって、メルセンヌ数は単なる「2^n - 1」の形をした数である。
メルセンヌ数が素数であるかどうかは「リュカ検定(ルーカス・テスト)」に
よって比較的効率よく行えるので、「メルセンヌ素数は無限に存在するか?」
「(偶数の)完全数は無限に」という問題と関連して、コンピュータによる
探索が行なわれている。そうやって見つかった素数は桁数が大きいので
「現在知られている最大の素数」みたいな形で話題になる。
つぎに、任意の有限な数 n をビット列で表したときの、最初のオンビットから
最後のオンビットまでの部分を、“コラッツむし”と呼ぶ。
154:132人目の素数さん
18/05/28 06:04:45.60 DIMEHMYY.net
4で割って1余る(n ≡ 1(mod 3))コラッツむし以外のコラッツむしは、
下位に「2個以上連続したオンビット部分」を持っている。ここで、m 個並んだ
オンビットがあるとして、そのうちの下位側の m - 1 個のビットを
「メルセンヌ部分」、残りを「本体」とする。このとき、本体部分に m - 1 回の
「3n + 2」操作を行なったものが、コラッツむしの“真の体長”だと
思うことにしよう。
つまり、n が メルセンヌ部分を持っているときは、メルセンヌむしは
“縮んでいる”わけだ。
3n + 1 操作を受けた“伸びた”コラッツむしの下位側には、0(二進数表記。
オフビット)が現れる。ただし、任意個の 0 は“ないのと一緒”なので、
コラッツむしの体長には含まれない。
そこで、「コラッツ予想が正しいかどうか?」は、「コラッツむしの“真の体長”が
際限なく伸びてゆく場合があるか?」という問題に帰着する。
そうなると、本体部分は「4で割って1余る素数」だ。これに 3n + 1 操作を
行なったときに、メルセンヌ部分がどう表れるかという話になる。この
メルセンヌ部分が際限なく表れると、コラッツむしの真の体長が伸びて、
メルセンヌ予想が破綻する。
155:132人目の素数さん
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・2・1・2 と
変わる。
つまるところ、「真の体長を伸ばすようなメルセンヌ部分が、どれだけ
出てくるか?」という話になる。
「山よりでかい猪は出ない」わけで、真の体長よりも“長い”メルセンヌ部分が
出ることはない。これを踏まえて、「コラッツむしの真の体長が無限に伸びる
ことがあるのか?」という話になる。このあたりが mod 3 と mod 4 の
絡み合いで組合せによって解決できて、「伸びるにしても限度がある」ことが
示されれば、メルセンヌ予想は肯定的に解かれたことになる。
こう考えると わりと単純な話なので、数学の素人でも手を出しやすいような気が
する。もっとも、コラッツ問題自体が「素人にも手をだしやすいが、素人の手には
負えない」問題なんだから、解けるかどうかはまた別の問題なのだが。
156:132人目の素数さん
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 に『三倍して2を足す』操作を p 回繰り返した結果に
コラッツ操作を施すことで、どれほどの桁数(これを n とする)になり、
最下位に何桁(これを m とする)のメルセンヌ数が出てくるか?」を
考える(m < n であることに注意)。
m と n を p と q の関数で表して、 n - m が q - 1 よりもどんどん大きく
なっていったら、コラッツ予想は「はずれ」だということになる。
おそらく、最悪のケースで見積もると、“爆発”(無限大に発散)すると思う。
そうでなかったら、コラッツ問題はとっくに解決しているはずだ。
だから、相当に ややこしいテクニックを駆使して「最悪のケース」を避けて
「無限大には発散しない」ことが示せれば、コラッツ予想は肯定的に証明される
ことになる。
そんなにうまくゆくとも思えないし、可能だとしても相当に苦労するだろうとは
思うのだが、方向性としては ちょっと新しいように思うので、「難しい」とか
「ダメっぽい」とか「ここから先で行き詰まった」くらいの実績は残しておいても
いいと思う。
コラッツ予想に関する「や
157:ってみたけどダメだった」的な論文というのは 山ほどあるのだから、いまさら何本かのクズ論文が増えたところで 文句を言う奴もおるまい。
158:128
18/05/28 08:25:18.74 /SyHFjrG.net
>139
既知の情報だったようですね。失礼いたしました
>148
何かしらのお役に立てたのなら幸いです。
159:132人目の素数さん
18/05/28 09:44:13.47 DIMEHMYY.net
>>152 >>128
> 既知の情報だったようですね。失礼いたしました
いやいや、2ちゃん(今は「5ちゃん」だが)でガイシュツは恥ではない。
お気にならさず。
> 何かしらのお役に立てたのなら幸いです。
本当に役に立った。ありがとう m(_ _)m
ついでながら、>>151 の
> 2^q - 3 は、2 < q のときに、二進数で q - 1 桁になる。
というのは、「5以上の4で割って1余る奇数」のうち、いちばん
みっしりビットが詰まったやつのことである。
このあたりのコンセプトの整理には、本スレに参加している諸氏の意見が
非常に役立った。併せて感謝申し上げる。ありがとうm(_ _)m
160:132人目の素数さん
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」に関してツブしてゆこう、という話ではないかと思う。
オレは何かヘンなことを言っていると思ったら、ツッコミを入れてほしい。歓迎する。
161:前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} に分ける、というような操作に関しての発言だと思いますが、
これを表現したければ「軌道」と言うのが適切かと思います(群論の言葉です)。
162:前786
18/05/28 15:04:43.97 juv57CZY.net
2 に注目していることについては、
例えば次のような問題を考えれば納得できると思います。
問. どんな自然数からでも、コラッツ操作とコラッツ逆操作を繰り返すことで 9 の倍数に到達できるか?
163:132人目の素数さん
18/05/28 15:27:05.72 DIMEHMYY.net
スレの流れからいうと不規則発言なので、「そういうコトを言っている香具師がいる」
くらいに思ってほしい。
なんとなく問題の本質が見えてきたような気がするので、「コラッツ予想」
「コラッツ問題」に関して「他の研究者は、どんなアプローチを取っているんだろうか?」と
思って検索してみた。
そうすると、「3n + 1 問題」の 3 を「一般の k に拡張したときに」とかいう話が
�
164:スいんだよね。 「逃げちゃダメだ、逃げちゃダメだ、逃げちゃダメだ」と思う。そんなもん、 「3n + 1」を解決してから考えろ、と思う。 mod k からアプローチするのは、基本的に“あり”だと思う。だけど整数論 (群とか環とか体とか)に関していうと、あんまり道具としては使いやすくないので 、「果たして有効だろうか?」と思う。まぁ、数学の素人が言う こったから、 「ふぅーん、あんたはそう思うのね?」くらいの感じで聞き流してくれても まったく問題がないのだが。 だいたい、「数学」っつーのは“無限”を相手にすることが多い。「実用的な範囲で、 どれくらい抑え込めるのか?」っつーのは、どっちかっていうと有限組合せ数学とか の範囲の仕事なのだ。だから、純粋数学畑の人はあんまり興味を持たないと思うし、 数式処理システムとか実験数学とかいったものとかとは距離を置きたいと思うのが 当然だと思う。 あとは「整数論方面のほうからのアプローチが どこまで通じるか」という期待が あるのだが、そっち方面の研究って、あんまり進んでないような気がする。 「有限束の数え上げ」とか「魔円陣(完全ゴロム環)」とかいった話題は、 もう十年以上も取りあげられていないような気がする。 てなワケで、燃料を投下してみた。敲いてくださって結構。かかってらっしゃい。 数学はまるでダメだが、伊達に長年ネットで のたくっていたワケでもないので、 口だけは達者だ。
165:132人目の素数さん
18/05/28 15:54:28.71 DIMEHMYY.net
>>155
おお、数学屋さんがマトモに応答してくれるとは光栄だ。これは皮肉ではない。
本当にそう思っている。
> 2 に注目しているのは、
> コラッツ操作の「偶数を 2 で割る」
> 逆操作の「2 をかける」
> から来ています。
私はビット列として考えているので、“コラッツむし”みたいな概念で「シフト演算」
あるいは「ヌルビットの除去」というイメージで捉えているのだ。このあたり、
プログラマという商売柄がある。そんなわけで、「だったら、コテハン(固定ハンドル)を
使って立場を明確にしろ」ということであれば、対応するつもりだ。
166:132人目の素数さん
18/05/28 15:56:30.55 DIMEHMYY.net
>>155 つづき
>>「Z/pZ」(つーか、どうせ自然数なんだから「N/pN」で構わんと思うんだが、
>> それは「整数論」という括りでいうと「自然数に 0 が入っちゃまずいだろう」という
>> 配慮があるんだろうと思う)というのは、単なる剰余系であって、
>> 「何に関して閉じているか」っつーのは、また別の話なんだよな?
> ここで何を気にされてるのかいまいちよく分かりませんが、
> 「閉じている」という表現は全体の一部分を見ているときに使う表現なので、
> この場合適切でないと思います。
>
> 例. 整数全体の中の奇数の集合は、積について閉じていて和について閉じていない。
>
> 「どういう演算を考えているか」を気にしているということでしょうか?
「群論」というと、整数論をちょっと齧った人間としては、まず「循環群」
(その集合の要素をすべて網羅すること)を連想してしまうのだよ。
だから、「2 をかける」という操作よりも、「3n + 1 という操作に関して、
その有限集合が閉じているか?」が気になってしまうのだ。そういう意味では、
「どういう演算を考えているか」が気になる。
167:132人目の素数さん
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 ビットである
木構造」と捉えると、「木」と呼んでも しっくりくると思うのだが。
168:132人目の素数さん
18/05/28 16:37:50.04 DIMEHMYY.net
>>156
> 問)どんな自然数からでも、コラッツ操作とコラッツ逆操作を繰り返すことで
> 9 の倍数に到達できるか?
なんとなく意味は分かるのだが、どういう問題意識があるのかがピンとこない。
mod p の木に奇数 m があり、mod q の木に奇数 q があったとすると、(p と q が
互いに素だとして)Z/pqZ 上では「根である 1 まで下がって、また上がってくりゃ
いいだけの話じゃん?」と思う。
「p と q の
169:直近の(いちばん近い)共通の奇数 x があり、それぞれコラッツ操作に よって x -> p と x -> q に至るルートを(効率よく)求める方法を(コラッツ操作と コラッツ逆操作を それぞれ用いることで)示せ」っつーんなら、「ひょっとしたら、 なんとかなるかも知れん(オレが出来るとは言わんが)」くらいのことは言えるが。
170:前786
18/05/28 17:29:14.11 juv57CZY.net
>>161
私が考えているのは
「コラッツ予想は、初期値が n で割って k 余る数だけ考えれば十分である」
というのがどんな n, k についても成り立つか、という問題です。
それを証明するための一つの手段として、
「どんな自然数からでも、コラッツ操作とコラッツ逆操作を繰り返すことで n で割って k 余る数に到達できる」
を示そうと思っています。
ところで「mod p の木」とか 「mod q の木」などと私は一度も言っていませんが、何の話でしょうか。
Z/pqZ 上では「根である 1 まで下がって、また上がってくりゃいいだけの話じゃん?」、というのも意味がよく分かりません。
171: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 へのルートをそれぞれについて求めて、
その差分を取る」みたいなアプローチが成功しそうに思う。
あくまで個人的な感想なのだが。
172:Mb
18/05/28 19:28:33.47 DIMEHMYY.net
>>162
> ところで「mod p の木」とか 「mod q の木」などと私は一度も言っていませんが、
> 何の話でしょうか。
原始根は複数個ありうるので、巡回群(剰余系における、全部の要素を辿る乗数系)も
複数個ありうるのだが、「一部の要素」をフォローする(単一の)乗数と、「その他の
要素」をフォローする乗数(その他大勢)が、全体として Z/pZ を隈なく覆う、
という「グループとしての、木の集まり」というものを考えて、「その集まりを
考えたときに、木の本数が、ある一定数よりも大きくならない」ということを
謂っているんだろうと思っているのだ。
それを考えると、「どこかの木に属している」ということは、「他の木に属していない」
という意味になりそうな気がするわけで、そうした「排他的な木」としての
「mod p の木」とか 「mod q の木」という概念はあっていいような気がするし、
それぞれの木が排他的に「すべての自然数」を所有しているとすると、
「グループとしての、木の集まり」がコラッツ問題をカバーしていることになり、
Z/(全部の木の基数の積)Z の存在を示すことができれば、コラッツ予想が肯定的に
証明できることになるような気がする。
173:前786
18/05/28 21:38:47.13 juv57CZY.net
>>163
mod 3 と mod 4 の絡み合いでややこしくなるとか、コラッツ操作とコラッツ逆操作を混在させて迷走しそうとか
心配はありがたいのですが、既に多数の n や k について証明できているのは見ていただけてるでしょうか。
「なんとなく」の印象だけで話されても困ります。
>>164
>「一部の要素」をフォローする(単一の)乗数
原始根にならない元のことでしょうか。よく分かりません。
数学の言葉でお願いします。
>「その他の要素」をフォローする乗数(その他大勢)
ここはもっとよく分かりません。
>Z/pZ を隈なく覆う、という「グループとしての、木の集まり」
軌道のことでしょうか。
>「その集まりを考えたときに、木の本数が、ある一定数よりも大きくならない」ということを謂っている
なんのことでしょうか。
174:righ1113
18/05/28 22:20:56.19 7MfED6re.net
>>144-147
説明ありがとうございます。完全に理解したとは言えないのですが……
このプログラムの実行には12時間以上かかったので、無駄にならなくて良かったです。
175:132人目の素数さん
18/05/28 22:30:29.54 vACmorEE.net
若干スレが荒れぎみですがこれも2chの華ですかね?
176:前786
18/05/29 08:17:04.68 uipUXNvy.net
>>166
よく粘りましたねw
逆
177:に言えば、プログラムで数千、数万回計算して得られた結論がたった3レスで説明できた訳ですから、 この考え方をうまくプログラムに落としこめれば計算量を大幅に削減できる可能性も…… >>167 私の発言でそう思わせてしまったなら申し訳ありません。
178:132人目の素数さん
18/05/29 14:20:35.00 hqRqM8Wt.net
「すべての自然数 N に対して、偶数は(素因数分解したときの 2 の乗数について
割ったら)奇数に帰着する。
「『4で割って3余る奇数』は、ビット列で表現したときに、下位のオンビット列
(一個以上のビット列が並んでいるビットパターン)」に帰着するので、
「4で割って3余る奇数」に帰着する。
そうすると、「4で割って1余る奇数」に帰着するすべての自然数が、3n + 1 操作に
対して、「4で割って1余る奇数」に帰着するかどうかが問題になるわけだから、
「ある『n ≡ 1(mod 4)の数が、(3n + 1)/2 操作によって、『n' ≡ 1(mod 4)の数』に
なるとき、n' が単調増加して無限大に発散するかどうか?」という話に帰着する。
そんなわけで、そのとき、2 で割ったときに、「『2 < n| 2^n - 1』が無限連鎖するか?」という話になる。
自分は数学屋ではないので、数式を追っかけて解決する自信がない。
数値実験で見当をつけようと思う。
ロジックに穴があったら指摘していただきたい。m(_ _)m
179:righ1113
18/05/29 18:52:19.94 MoZwWLVJ.net
>>169
最後がよく分からないです。
> 2 で割ったときに、「『2 < n| 2^n - 1』が無限連鎖するか?」
詳しい説明が欲しいです。
例えば、ビット列で言うとこう、とか
プログラム(アルゴリズム)で書くとこう、とか。
180:132人目の素数さん
18/05/29 19:02:13.73 4lgsCN3f.net
>>168
まあここまでが順調過ぎましたからね
今の方が本来の2chの姿に近いかも
あまりガッカリせずに気長に行きましょう
181:132人目の素数さん
18/05/29 21:09:33.77 hqRqM8Wt.net
>>169
> 最後がよく分からないです。
>> 2 で割ったときに、「『2 < n| 2^n - 1』が無限連鎖するか?」
> 詳しい説明が欲しいです。
あ、ごめん。言葉が足りなかった。
最下位に「連続した2個以上のオンビットがある」というのが
n ≡ 3(mod 4)
ということなわけで、
その場合は「下位のメルセンヌ部分を除去したビット列に、
3n + 2 操作を行ないつづけることで、n ≡ 1(mod 4) に帰着する」
ということが謂える。
だから、「メルセンヌ部分を除いた本体が、増えるか減るか」が
肝心なところであって、「最下位に一個以上の 0 があって、本体の長さが
減る」のか、「最下位に二個以上の 1 が現れて、本体の長さが増える」のかが
問題になるわけだ。
その部分に着目すると、コラッツ操作の逆操作を考えたときに、かなり計算量が
減るように思うので、「コラッツ予想は 5 × 2^60 までは成り立つ」みたいな
ショボい話(IEEE の long よりも小さい)ではなくて、メルセンヌ素数的な
デカい数まで(たとえば 10^100 とかまで)コラッツ予想は成り立つことが、
“数値実験的に”ではなく、“数学的に”(といっても、コンピュータによる
実験的な検証が入っているので、数学的な厳密性に欠けているという点については
完璧ではないのだが)「コラッツ予想は成立する」と断言しちゃっていい、
みたいな話になると思うのだ。
182:132人目の素数さん
18/05/29 21:10:17.02 hqRqM8Wt.net
少なくとも、「フツーにプログラムを動かしていたら、例外が見つかった」とか、
飛行機が堕ちて死ぬとか巨大彗星が堕ちてきて人類が滅亡するとか、そういった
確率の何百万分の1以下のところまで絞りこめれば、「実用的には、コラッツ問題は
解決した」(とはいえ、コラッツ問題の実用性というのが、あるとは思えないが)と
言っちゃっていいと思う。
暗号理論だって、「偶然、解読のための鍵が見つかっちゃう確率は 0 ではない」という
意味では完璧ではないわけで、「じゃあ、具体的には、コラッツ予想は、どこまでの
範囲で成り立つのか?」という限界を、「可能性がありそうな部分を、一個づつ
ブルート・フォース・アプローチによって潰してゆく」より効率のよさそうな方法で
ツブしてゆ�
183:ュというアプローチがありそうに思う。 で、その過程で、「なんか、こっから先には なんにもなさそうな気がする」という 限界が うっすらと見えてきたら、そこから逆に「じゃあ、このあたりには何があるの?」とかいった見当がつくのかもしれない、と思う。 コラッツ予想はメルセンヌ素数 8,191 に絡んで、2^8191 - 1 あたりで組合せ論的には 頭打ちになると思う。実際にメルセンヌ数から出発してメルセンヌ数に落ちるケースは 127 かなんかが最高だったので、あとは「メルセンヌ数ではない数から出発して、 3n + 1 操作“のみ”によってメルセンヌ数に落ちる」ケースを潰してゆけば、 コラッツ予想が成立する限界点は もっと先まで確認できるように思うし、 ひょっとしたら(四色問題や有限群の分類みたいに)「この先は、組合せ論的にいって ありえない」みたいなコトになるかもしれない(とはいえ、私は数学の専門家では ないので、数学者の誰かが証明できたとしても、その証明を理解できる自信は まったくないのだが(-_-!))。 てなワケで、現在探索を続行中。
184:132人目の素数さん
18/05/29 21:15:32.62 f2WjLLel.net
>>173
探索を実行中ってことはもうプログラムがあるってこと?
なんなら>>1みたいに晒してくれてもいいのよ?
185:132人目の素数さん
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
186:righ1113
18/05/29 22:09:23.31 HdpfadtL.net
>>175
今ひとつ分からないので、自分はソースを待ちます。
187:132人目の素数さん
18/05/29 22:34:19.60 f2WjLLel.net
やはり>>786が論理を構築し>>1がその論理をプログラムで実装するというのがこのスレのベストプラクティス。
なにかいいネタはないかな。
188:righ1113
18/05/29 22:53:33.64 HdpfadtL.net
>>177
>>113とか、どうですかね?
189:132人目の素数さん
18/05/29 23:17:54.07 f2WjLLel.net
いまいちよくわかってないんだが>>113の①②③はそれぞれ別々に証明する必要があるってこと?
で①②③がいえれば④がいえるってこと?
190:前786
18/05/29 23:19:19.88 z3i0m55/.net
>>177
プログラムの結果を参考にして証明を進める、までできれば私としてはベストですね。
今は>>168で書いた案について考え中。
>>178
>>113の①はなんとかなるかもしれません。
「繰り返すと1つになる」というよりは「繰り返しても集合の個数が増えない」という論法になりそうです。
ちょうど>>168のアイデアにも関連します。
このあと軽く説明します。
191:righ1113
18/05/29 23:30:01.77 HdpfadtL.net
>>179
①と②は対偶関係なので、
①を証明する→③を証明する→④が言える
です。
192:前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 で考えるだけで済んだ。
ということが効いているんじゃないかと思います。
それで、一�
193:ツ目はおいといて二つ目の mod 19^2 で考えるところが mod 19 で済む という部分がポイントで、 こういうのが許されるのはちょうど「C を繰り返して集合が増えないとき」になりそうなんです。 さらに、プログラムを進めていくとどこかで「繰り返しても集合が増えない」となることも証明できそうなので、 これを利用してプログラムの計算量を減らせそう、という考えです。 時間があるときにちゃんと考えようと思います。
194:前786
18/05/29 23:51:01.24 z3i0m55/.net
(実際のところ、>>156が分かる人がどのくらいるのかちょっと気になる)
195:righ1113
18/05/30 00:00:21.34 SjK0M6Ur.net
>>183
自分は分かっている……つもりです……
196:132人目の素数さん
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倍は「好きなだけ遡れる」ところがポイントかね
197:132人目の素数さん
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
つーても、これがコラッツ予想の解決とどう結びつくのかがわからんが。
198:132人目の素数さん
18/05/30 07:46:53.88 pjE9OVg/.net
あ、
×
199:132人目の素数さん
18/05/30 07:48:45.57 pjE9OVg/.net
あ、
× 12 → 11 → 9
〇 12 → 24 ≡ 11 → 22 ≡ 9
だった。
200:132人目の素数さん
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 を
考えたらいいのか …… わからん。
201:前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
確かに私の予想が証明できてもすぐにはコラッツ予想に繋がりませんが、
まあ外堀を埋めるような感覚です。
それに、もし万が一私の予想に反例が見つかれば、その時点でコラッツ予想も不成立となるので、
そういう意味ではコラッツ予想を直接攻めていると言えなくもないかなと。
202:132人目の素数さん
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 の
記述は、このあたりに絡んでいるのかもしれないと思う。
203:righ1113
18/05/30 18:37:06.75 0W4YjiD/.net
>>191
下位に2^n-1が出てくるだけじゃなくて、実際のメルセンヌ数も絡むの?!
ますます分からなくなる(>_<)
204:132人目の素数さん
18/05/30 19:01:13.88 pjE9OVg/.net
>>192
> 下位に2^n-1が出てくるだけじゃなくて、実際のメルセンヌ数も絡むの?!
> ますます分からなくなる(>_<)
だからコラッツ問題は面白いんじゃないですか (^_^)v
205:
206:132人目の素数さん
18/05/30 21:14:57.31 fCXVi6t2.net
そういえば剰余コラッツ予想(前>>786の予想)の反例が見つかったと仮定して、
その反例から元のコラッツ予想の反例を求めることは簡単なの?
207:前786
18/05/30 23:24:08.24 8DwWThhE.net
>>194
(その名前使ってくれてありがとう)
これは簡単です。
剰余コラッツ予想の反例があるということは、
ある自然数 a,n,k が存在して
「a からコラッツ操作、コラッツ逆操作を繰り返しても、n で割って k 余る数に到達できない」
ということです。
このとき特に、a から k に到達することができません。
ここで、もし a,k が共にコラッツ操作で 1 になるとすると、
a→1→k のルートで a から k に到達できてしまい矛盾します。
したがって、a,k のいずれかがコラッツ予想の反例となります。
208:132人目の素数さん
18/05/30 23:43:24.81 fCXVi6t2.net
え、じゃあa,kのいずれかは5*2^60より大きくなきゃいけないってことか
209:前786
18/05/31 00:03:29.44 sTlF47Ao.net
>>196
あ、ほんとだ
素で気づいてませんでした。
ちょっとこれは認識を改めないといけないかもしれない
210:righ1113
18/05/31 00:15:22.71 hTYeS4Jm.net
プログラムもそこまでとか、ムリだからねっ
211:righ1113
18/05/31 00:24:01.59 hTYeS4Jm.net
>>197
ちなみに今のプログラムで反例が見つかっても>>195に繋げられる?
212:前786
18/05/31 00:41:52.06 sTlF47Ao.net
>>199
ちょっとまだ分かりません。
反例が見つかったら考えようと思っていました。
ちなみに今のプログラムは剰余コラッツ予想を完全に確かめられるものではない(>>103の話)ので、
5*2^60 以下でもプログラムでの反例が見つかる可能性はあります。
213:righ1113
18/05/31 00:46:19.98 hTYeS4Jm.net
弱い成果が得られるやつですよね。
214:前786
18/05/31 00:58:27.40 sTlF47Ao.net
そうですそうです。
215:132人目の素数さん
18/06/02 21:15:03.31 2LuxVRMt.net
n ≡ 1 (mod 4) に 3n + 2 操作を(連続して)行なったときに
何が出てくるかと、
n ≡ 1 (mod 4)に 3n + 1 操作を行なったときに、
n ≡ 0 (mod 2) と 1 ≡ 3 (mod 4) がどんなふうに
出てくるかと、
四進法で 11111 …… がどんなふうに出てくるかで
(これはどっちかというと効率上の問題)、
どうやら 2^63 の壁は突破できそう。
ただ、アルゴリズムの効率がいまひとつなので計算機パワーに
頼っているのと、数学的に理解しやすい表現に落ちないんだよな ……
連分数による無理数の近似を行なおうとすると、φがいちばん
誤差が収束しづらいとか、そんな話になりそうなんだよな。
遠山 啓先生の『初等整数論』の終わりのほうにもそんな話が
出てきてて、「うーん、オレが求めているのは、
そういう結果じゃないんだけどな」と思ってはいるんだが。
216:132人目の素数さん
18/06/07 19:47:31.27 ddCD53Qi.net
スレが止まってるが大丈夫か?
217:righ1113
18/06/07 21:30:24.45 hy9kJ5h9.net
特に進展がないのです……
218:132人目の素数さん
18/06/07 21:38:46.18 GMXTgnWv.net
>>204
「大丈夫だ。問題ない」… とは言えんな。
いまのところ2つのアプローチを考えている。
「下位のオンビット列を切り離して、3n + 2 操作を繰り返したあとに
残った 1(mod 4) に 3n + 1 操作を加えたときに
下位に何が(オンの連続かオフの連続か)出るか(そこで 0(mod 4) が
出るまではいいとしても)」、数学的に考えると「下位のオンビット列を
切り離す」操作をどう考えたらいいかとか、操作が複数になるので
理論的にややこしくなるという問題がある。
かといってそれを素直にビット列で考えてコンピュータで
処理しようと思うと、桁数が多くなる(2^63 を超えたあたり)と
31(2^5 - 1)とかが出てきて収拾がつかなくなりそうな
気がする。
数学的素養にしろコンピュータの性能にしろ、
「そんな装備で大丈夫か?」的な不安はある。
219:132人目の素数さん
18/06/08 13:40:04.11 gOsCxwff.net
数学板でこれを言ったらボロクソに叩かれるのは
220:承知しているが、 「1 ビットに収束する という制約を外して、セルオートマトンで表現する」 とかいった形で画像にしてみて、 その画像に FFT とか ウェーブレット変換とかをかけて挙動を推測する、 とかいうアプローチは あるんじゃねぇ? 画像で表現したときに、「最終的にONな 1 ビットが移動するだけ」になるのは (実験的には)確認されているんだから、画像的に逆三角形が「どん」という 感じで出現するかどうか、っつー話なわけだから。
221:132人目の素数さん
18/06/08 20:05:54.99 ID4JGGod.net
アイディアを出すのは構わないが実装するのはきみだ
222:132人目の素数さん
18/06/08 20:12:20.69 gOsCxwff.net
>>208
> アイディアを出すのは構わないが実装するのはきみだ
解ってる。問題は「他にできる奴がいねぇ」っつー点なんだわ。
やんなくていいから、せめて まともなツッコミくらい
入れてくれないと、気分が萎えるんだよ。
223:132人目の素数さん
18/06/08 20:43:30.22 ID4JGGod.net
まともな突っ込みが欲しければもっとアイディアを具体化してくれ。
まだ突っ込み云々の段階じゃないだろ。
224:132人目の素数さん
18/06/08 21:15:37.98 gOsCxwff.net
>>210
> まともな突っ込みが欲しければもっとアイディアを具体化してくれ。
わかった。要するにお前は
「下位に 0 または 1 が連続するパターンに、
3n + 1 の逆操作を(偶数を経由せずに)1(mod 4) に
至る数の性質を明らかにしろ」っつーコトだな?
そんなもん、簡単にできたら苦労しねぇよ orz
225:132人目の素数さん
18/06/08 21:50:50.71 gOsCxwff.net
>>211
> そんなもん、簡単にできたら苦労しねぇよ orz
いや待て。ちょっと待て。
> 「下位に 0 または 1 が連続するパターンに、
> 3n + 1 の逆操作を(偶数を経由せずに)1(mod 4) に
> 至る数の性質を明らかにしろ」
っつても、「偶数を経由せずに」じゃなくて、
「1(mod 4)を経由せずに」なんじゃねぇの?
(末尾が二進数で 00 とか 01 とか 11 だったら、
別のケースに帰着しちゃうんだから)
これだったら結構 効率よく追っかけられそうな
気はするんだよな
頑張ってみる。サンクス。>>210
226:132人目の素数さん
18/06/09 09:51:12.21 12rdjGpD.net
>>212
× 「偶数を経由せずに」じゃなくて、「1(mod 4)を経由せずに」
〇 「偶数を経由せずに」じゃなくて、「1(mod 4)だけを経由して」
227:righ1113
18/06/09 19:25:47.19 3gm5u4YA.net
プログラムを使って、
n=3037から6367までの素数396個、全て正常終了を確認しました。
オールNothing出ないですね……
228:132人目の素数さん
18/06/09 19:32:18.47 XXNgJp1+.net
ほほう。
>>1乙です。
229:132人目の素数さん
18/06/09 19:39:31.39 XXNgJp1+.net
ちなみに素数に絞ったのはなにか根拠があるんですか?
それともなんとなくですか?
230:righ1113
18/06/09 19:59:06.87 3gm5u4YA.net
本当はむしろ合成数をやりたかったのです。
素数なら30分で終わるところが、合成数だと2時間かかったり。
ほんで素数にしました。
231:132人目の素数さん
18/06/09 20:20:31.16 12rdjGpD.net
>>214
とりあえずコラッツ予想の反例が出なかった、という意味では
順当な結果だと思います。ともあれご苦労様ですm(_ _)m
そうすると、現時点で「コラッツ予想が成立する数の上限値」と
いうのは、どの程度なんでしょうか。
IEEE の 64 bit INT(=Java の long)までは反例がない、
とかいった話ではあるんでしょうか。
232:righ1113
18/06/09 20:48:37.47 3gm5u4YA.net
>>218
>>191の後半に
>「コラッツ予想は数値実験によって
>5*2^60 まで正しいことが確認されている」
>とかいった WikiPedia の記述
があるからそれだと思います。
233:132人目の素数さん
18/06/10 02:56:21.72 tquT+eik.net
>130ですが、また別のアプローチを試みてみたところ、少し面白い結果が得られたのでご報告。既知の情報だったら申し訳ないですが…
「ある奇数にコラッツ操作(3n+1→奇数になるまで2で割る)を試みた結果どんな数になるか」をまとめたところ、以下のような規則性があるのに気づきました。
操作後の数をAとして、Aを3で割った余りが
○1(1.7.13…)の場合:(A*4-1)/3を初項として、以下(4n+1)と掛け合わせた数がAとなる
(1
234:←1.5.21.85…)(7←9.37.149.597…) ○2(5.11.17…)の場合:(A*2-1)/3を初項として、以下(4n+1)と掛け合わせた数がAとなる (5←3.13.53.213…)(11←7.29.117.469…) ○0(3.9.15…)の場合:コラッツ操作でAになる数は存在しない 一旦切ります。
235:218
18/06/10 03:30:20.71 tquT+eik.net
続きです。
で、余り0はほっといて、余り1と余り2をそれぞれまとめてみました。
1: 1. 5. 21. 85. 341. 1365…
7: 9. 37.149. 597. 2389. 9557…
13:17. 69.277.1109. 4437.17749…
19:25.101.405.1621. 6485.25941…
25:33.133.533.2133. 8533.34133…
31:41.165.661.2645.10581.42325…
5: 3.13. 53. 213. 853. 3413…
11: 7.29.117. 469.1877. 7509…
17:11.45.181. 725.2901.11605…
23:15.61.245. 981.3925.15701…
29:19.77.309.1237.4949.19797…
35:23.93.373.1493.5973.23893…
…縦と横を入れ替えると、全部等差数列になってるんですよね、これ。
もう少し続きます。
236:218
18/06/10 03:41:04.40 tquT+eik.net
続きです。長くなってしまって申し訳ない。
3.7.11.5.19.23 初項3 公差4
1.9.17.25.33.41 初項1 公差8
13.29.45.61.77.93 初項13 公差16
5.37.69.101.133.165 初項5 公差32
53.117.181.245.309.373 初項53 公差64
21.149.277.405.533.661 初項21 公差128
213.469.725.981.1237.1493 初項213 公差256
85.597.1109.1621.2133.2645 初項85 公差512
853.1877.2901.3925.4949.5973 初項853 公差1024
341.2389.4437.6485.8533.10581 初項341 公差2048
3413.7509.11605.15701.19797.23893 初項3413 公差4096
1365.9557.17749.25941.34133.42325 初項1365 公差8192
…。
1+2=3
3+2=5
5+8=13
13+8=21
21+32=53
53+32=85
85+128=213
213+128=341
341+512=853
853+512=1365
1365+2048=3413
なんていう分布を見ると、「それぞれの項目が重なり合わないように敷き詰められている」ように思えてなりません。素人なんではっきり証明できる力はないのですがorz
以上、気づいた点のご報告でした。
スレ汚し失礼いたしました。
237:132人目の素数さん
18/06/10 08:07:49.10 GkYmcQpB.net
初項2x+1 (x:整数)
漸化式 a_(n+1)=4 a_n+1
で与えられる数列の各項はコラッツ予想の操作で合流する
(2x+1)×3+1=6x+4
(4(2x+1)+1)×3+1=24x+16=4(6x+4)
一般項a_n=((6x+4)/3)^n-1/3
238:132人目の素数さん
18/06/10 08:29:53.23 GkYmcQpB.net
重ならないように、というのは、
×4+1した隙間の奇数が次々に出てくるのかな
239:132人目の素数さん
18/06/10 09:11:07.49 gH+TEyZw.net
>>204
> 「それぞれの項目が重なり合わないように敷き詰められている」ように思えてなりません。
コラッツ予想は、言い方を変えると「4で割って3余るすべての奇数は、
『3倍して1を足す』『2で割る』という二つの操作によって、
1を根とした二分木上に一意に配置される」ということだから、
その認識は正しいと思います。
> 素人なんではっきり証明できる力はないのですがorz
まぁまぁ、そうおっしゃらずに。数学者は数学的な道具の取り扱いに長けているので、
つい自分の使い慣れた道具で扱おうとして、結果的に灯下探索症候群に
陥ることもあるようですから、素人目線も重要ですよ。
行列を使って永らく未解決だった問題が、連分数や図的解法(古代メソポタミアでは
普通に使われていましたが、二十一世紀に再評価されるまで、ほとんど博物�
240:ルの 展示物扱いでした)で あっさり解けちゃった例もありますし。 ヘヴィサイドの演算子法みたいに、「とにかく解けるんだからいいじゃないか」と いうのに後から数学的なリクツがついてきた、という例もあるので。
241:132人目の素数さん
18/06/10 09:27:08.31 gH+TEyZw.net
>>220 の指摘は、「二分木上に一意に配置される」という観点からいうと、
ある「4で割って1 余る奇数」を d (odd の d です。o だとゼロと紛らわしい
ので)としたとき、「d が d≡0(mod 3)のときには、そこより先に(次の数 d' が
出てくるような)枝はない」「d が d≡1(mod 3)のときには、奇数枝が出ないので、
あるとすれば偶数枝の先に d' がある」「d が d≡2(mod 3)のときには奇数枝も
出るので、奇数枝と偶数枝の両方の先に d' (とか d'' とか)がある可能性がある」という
話になるんじゃないか、と思います。ですから、非常に納得のゆく視点です。
等差級数うんぬんの話というのは、そこから自然に導かれる帰結なのでは
ないでしょうか。
242:132人目の素数さん
18/06/10 09:38:45.60 gH+TEyZw.net
>>226
ごめんなさい。「奇数枝」というのは、「(3n + 1) / 2 操作によって
奇数に至るルート」なので、途中で偶数を経由しています。したがって、
「3n + 1 操作」ベースで考えると、「それは偶数枝として一般的に
扱ったほうが適切なんじゃねぇんの?」という批判は(たぶん)
あるかと思います。
243:132人目の素数さん
18/06/10 11:33:20.33 GkYmcQpB.net
1
2
4←1
8
16←5
32
64←21
128
256←85
512
…
5
10←3
20
40←13
80
160←53
320
640←213
1280
…
244:132人目の素数さん
18/06/10 11:48:45.88 GkYmcQpB.net
一般化するとこんな感じで枝分かれを繰り返してくわけだが
6n+1
12n+2
24n+4←8n+1
48n+8
96n+16←16n+5
192n+32
384n+64←128n+13
…
6n+5
12n+10←4n+3 「奇数枝」はここかな?
24n+20
48n+40←16n+13
96n+80
192n+160←64n+53
…
245:132人目の素数さん
18/06/10 13:29:24.03 gH+TEyZw.net
>>229
> 12n+10←4n+3 「奇数枝」はここかな?
よく分からんが、たぶんそうだと思う。
>>116 の再録になるが、
> 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
みたいな系列だ。
246:132人目の素数さん
18/06/10 13:37:00.64 gH+TEyZw.net
あ、念のため。
このスレに集っている方々にとっては常識だろうけれど、
‘☆’
247:がついてるのは、三の倍数(n ≡ 0 (mod 3))の場合な? 「偉そうに」とか「上から目線」とか、そう思われるのは 不本意なので。
248:righ1113
18/06/10 15:13:02.69 FdIQbMom.net
>>220
自分も昔似たような事を考えていました。
URLリンク(d.hatena.ne.jp)
でも後が続かないのですよね……
同じ事を考えた方がいたのは嬉しいです。
249:132人目の素数さん
18/06/10 16:52:17.37 gH+TEyZw.net
>>232
> 同じ事を考えた方がいたのは嬉しいです。
つーか、似たようなことを考えてる輩(やから)が
このスレに集まってるんだろうがよ(笑)。
250:218
18/06/11 07:22:40.87 l+PAssIA.net
>224
>222を初項の小さい順に並べ直してみると、
1.9.17.25.33.41…a
3.7.11.15.19.23…b
5.37.69.101.133.165…c
13.29.45.61.77.93…d
21.149.277.405.533.661…e
53.117.181.245.309.373…f
a___a___a___a___a___a___a___a___a
_b_b_b_b_b_b_b_b_b_b_b_b_b_b_b_b_
__c_______________c______________
______d_______d_______d_______d__
__________e______________________
__________________________f______
と、フラクタル的な配置が出現しているように思います。
言い換えれば、全ての奇数がこの配置のどこかに格納される事が証明できれば、「とんでもなく大きな数で例外が現れる」可能性を除去できるのではないかと考えたんですが、いかがでしょうか?
あとは、この数列が例外なくコラッツ操作後1に繋がる(1.5.21.85.341.1365…)の数列に帰結する事が証明できれば、コラッツ予想を証明したと言えるのではないかと。
(「そんなんできねーよw」と自分では思ってたんですが、>223が糸口になりそう?)
頓珍漢な事を言ってたら申し訳ないです。