X
トップページ⇒数学
1002コメント517KB
コラッツ予想がとけたらいいな
■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん
垢版 |
2012/10/14(日) 10:32:39.71
525 名前：１３２人目の素数さん[sage] 投稿日：2012/09/03(月) 18:24:27.22
http://d.hatena.ne.jp/righ1113/
コラッツ予想について、証明を考えてみました。
ご指摘ご意見ご感想など、ぜひよろしくお願いします。
0737righ1113 ◆OPKWA8uhcY
垢版 |
2017/10/09(月) 17:38:37.95ID:Vv+x6w6w
>>726
3^110503-1で再チャレンジしました。
一日かかって40000桁まで下がったのですが、これ以上続けるのはしんどいです。
グダグダですみません。
0738１３２人目の素数さん
垢版 |
2017/10/10(火) 11:57:48.23ID:ziN8w0WH
停止するかどうかを 3^110503-1 のときに
確かめようとしてる時点で既にグダグダだけどな。

なぜなら、どうせ停止するに決まってるからだｗ

それが 1 になるかは分からないが、少なくとも
停止することは確実だと予想してよいだろう。
無論それ自体も未解決ではあるのだが、
停止「しない」ことが期待されるような良い根拠はどこにも無く、
逆に必ず停止すると思しき良い根拠はいくつもあるわけで。
0739１３２人目の素数さん
垢版 |
2017/10/10(火) 22:17:48.67ID:n27Dzau3
例えばループする自然数があったとして、ループの周期が非常に長く履歴がメモリに納まらないようなことが想定される場合、
ループを検出するアルゴリズムとしてどのようなものが考えられるだろうか？
0740１３２人目の素数さん
垢版 |
2017/10/11(水) 01:44:51.35ID:4RhSgzf6
>>739
1ステップずつ移動するのと2ステップずつ移動するのを用意して
同時に走らせて、両者の値が一致するかどうかを毎回チェックする。
一致したらループに入ってるし、逆にループに入ってたら
必ず一致するタイミングが訪れる。
0755righ1113 ◆OPKWA8uhcY
垢版 |
2017/12/18(月) 03:09:43.02ID:zmSySbud
>>754
そうですね〜
成果は出ていないのですが、もう少しだけ頑張ってみます。
0756righ1113 ◆OPKWA8uhcY
垢版 |
2017/12/29(金) 09:10:07.92ID:miDoSCc+
>>570-576を再掲します。

・前準備1
例えばx_sが7,11,17,13,5,17,13,5……とループするなら、先頭2項は外して、
さらに最小値をx_0とおいて、5,17,13,5,17,13……にします。
例ではx_3=x_0になります。

・前準備2　
x_0~x_s-1がループ1周期として（x_0=x_s）、コラッツパターンX_sと左端を伸ばすパターンY_sのビット長は
[logY_s] = [log(x_0*(3/2)^s)]
[logX_s] = [log(x_0*(3/2)^s)+log(1+1/3x_0)…(1+1/3x_s-1)]
です。このときの[logY_s]と[logX_s]のずれがあってもなくても、周期を重ねるごとに[logX_s]と[logY_s]の差は
2log(1+1/3x_0)…(1+1/3x_s-1)、3log(1+1/3x_0)…(1+1/3x_s-1)、……と増大するので、
ずれも際限なく増大していきます。
0757righ1113 ◆OPKWA8uhcY
垢版 |
2017/12/29(金) 09:13:24.23ID:miDoSCc+
ループ1周期sで、コラッツパターンと左端を伸ばすパターンのずれが1、3周期でずれが3と仮定します。
X_3sを3ビット下位へシフトしてずれを消します。これをX_3s'とおきます。
X_3s'=x_0*(3/2)^3s*(1+1/3x_0)…(1+1/3x_3s-1)/8　　です。

[logX_3s'] - [logY_3s] = 0　　から始めて　
[log(x_0*(3/2)^3s)+log(1+1/3x_0)…(1+1/3x_3s-1)/8] - [log(x_0*(3/2)^3s)] = 0
切り上げを外して
-1 < log(1+1/3x_0)…(1+1/3x_3s-1)/8 < 1
logを外して
1/2 < (1+1/3x_0)…(1+1/3x_3s-1)/8 < 2

ここで、x_0がループ中最小で、s<=x_0ならば、
(1+1/3x_0)…(1+1/3x_3s-1) < ((1+1/3x_0)^3x_0)^(3s/3x_0) <= (1+1/3x_0)^3x_0 < e
なので、
(1+1/3x_0)…(1+1/3x_3s-1)/8 < e/8 ≒ 0.339
となって1/2を下回って矛盾します。よってs>x_0です。
0758righ1113 ◆OPKWA8uhcY
垢版 |
2017/12/29(金) 09:16:25.04ID:miDoSCc+
まとめると、
ループ1周期sで、コラッツパターンと左端を伸ばすパターンのずれが1、3周期でずれが3としたとき、
s > x_0（ループ中の最小値）　　です。

あるいは同じことですが、
ループ1周期でずれが1、3周期でずれが3としたとき、
1〜nまででコラッツの反例がなければ、
n周期以下のループは存在しない　　　です。
0762righ1113 ◆OPKWA8uhcY
垢版 |
2018/01/22(月) 00:44:19.88ID:4mi9P+bz
>>761
すみませんが、よく分からないです。
1回でも小さくなることを証明すれば、十分じゃないでしょうか。

nの全ての値がコラッツ操作で小さくなる→n+1の全ての値がコラッツ操作で小さくなる
が言えるので、帰納法により、全ての値がコラッツ操作で小さくなる
ことが言えると思います。
0763１３２人目の素数さん
垢版 |
2018/01/22(月) 04:00:15.16ID:zEZO4ljt
8x+3(n=2)→12x+5(n=1)→18x+8(n=0)→9x+4(n=?)

補題1-2がn=1の場合に偽じゃねえかな
0764righ1113 ◆OPKWA8uhcY
垢版 |
2018/01/22(月) 20:40:41.60ID:CNwla0Dh
【補題1-2】を次のように変更します。
旧：¬smaller(n+1)ならば、¬smaller(n)である。
新：¬smaller(k+2)ならば、¬smaller(k+1)である。

これにより、この命題でのsmallerの引数が2以上に制限されます。
>>763の例は
8x+3(n=2)→12x+5(n=1)→ここで打ち止め
となり問題を回避できます。

GitHubも更新しました。
0765１３２人目の素数さん
垢版 |
2018/01/23(火) 05:46:43.90ID:O+AtXeLE
問題は「最初の数より小さくなる」かどうかだから次は16x+7で同じことになるね
・2x→x
・4x+1→3x+1
では小さくなっているが
n>2では「最初の数より小さくなる」ことが保証できんのだ

2x→xによって整数全体に移るせいで問題がフラクタル構造持ってる
再帰的な解決はここを回避しないと封じられてしまう気がする
0766righ1113 ◆OPKWA8uhcY
垢版 |
2018/01/23(火) 09:59:19.01ID:MzJqaum6
>>765
すみませんよく分からないです……
じっくり考えてみます。
0767righ1113 ◆OPKWA8uhcY
垢版 |
2018/01/23(火) 10:50:15.55ID:iVG/+p9N
8x+3(n=2)→12x+5(n=1)=4(3x+1)+1→3(3x+1)+1
　　　　　　　　　　　　　　　　^^^^^^^^^^^^^^^^^^^^
　　　　　　　　　　　　　　　　ここでは小さくなっているが、
^^^^^^^^^^
この最初の数より小さくなっていない、でしょうか。
理解しました。
0768righ1113 ◆OPKWA8uhcY
垢版 |
2018/02/03(土) 16:35:17.43ID:fD/urjTL
◆◆◆■■■■　　　　　　　15→127
□◆◆■■■□■　　　　　　23→95
□□◆■■□□□■　　　　　35→71
□□□■□■□■■　　　　　53
□□□□□□□■□■　　　　5
□□□□□□□□□□■　　　1

新しいコラッツパターンを考えました。
◆を追加します。
すると、nの大小=x_sの大小が言えるので、
smaller(n+1)ならば、smaller(n+2)
が言えると思うのですが、どうでしょうか。
0769１３２人目の素数さん
垢版 |
2018/02/04(日) 07:22:20.66ID:mw9eaFXP
2x+1→6x+4→3x+2
2x+0→1x+0
をセットの操作として考える
xの係数は奇数なのでxの偶奇で次の偶奇が定まる
xを2x+1、2x+0で置換してもう1セット操作する
xの係数は奇数(というか3の冪)となるのでやはり次の偶奇はxの偶奇で定まる

あとは帰納法で「下位nビットがnセット操作分の変化を定める」のがわかる

下位ビット固定は固定した分しか定まらないのでうまくいかない印象
0771righ1113 ◆OPKWA8uhcY
垢版 |
2018/02/09(金) 22:41:34.79ID:6EKEcZuH
コラッツパターン2にしたら、
4x+1が小さくならなくなってしまいました。無念。
0772righ1113 ◆OPKWA8uhcY
垢版 |
2018/02/24(土) 14:20:55.93ID:RYOtT8nZ
構成を大幅に変えました。
コラッツパターン2も変えました。
0773１３２人目の素数さん
垢版 |
2018/02/27(火) 22:53:52.42ID:/Yl+hgqj
コラッツ問題の解決の役に立つかどうかはわからんが、思いついたので投下。

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
0774１３２人目の素数さん
垢版 |
2018/02/27(火) 22:55:29.10ID:/Yl+hgqj
以下、超略証。
(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からは周期の中での単調性が示せる。
(格子状の道の最短経路の曲がり方を一つづつ変えて行くように)
0775１３２人目の素数さん
垢版 |
2018/02/28(水) 19:18:14.81ID:6Xntgk3f
>>774
＞(格子状の道の最短経路の曲がり方を一つづつ変えて行くように)
ここがだめ(全順序にならん)なので不成立。
一定の条件のもとで、近い数は近くなる、くらいしか言えてないか。
0786１３２人目の素数さん
垢版 |
2018/04/28(土) 16:55:40.82ID:d9jkS/fs
１つ予想を立ててみた。

自然数全体の集合を 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 が存在する場合、コラッツ予想も偽であることになる。
0787１３２人目の素数さん
垢版 |
2018/04/28(土) 16:56:23.83ID:d9jkS/fs
基本的な操作を補題としてまとめておく。

補題
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。□


まだいろいろと書けることはあるけど、反応を見ながらということで。
0788righ1113 ◆OPKWA8uhcY
垢版 |
2018/04/28(土) 17:56:49.19ID:UAXb8Z2X
考え方として、
いくつもの木を考えるのですか？
それとも1を含む木T1のみに注目するのですか？
0789786
垢版 |
2018/04/28(土) 18:15:59.36ID:d9jkS/fs
全ての木を考えます。
それが１つなのか複数なのかは分かりませんが。
0793786
垢版 |
2018/04/28(土) 18:53:42.76ID:d9jkS/fs
これを書こうと思って忘れていた。

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

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

>>791>>792
よろしくお願いします。
0794１３２人目の素数さん
垢版 |
2018/04/28(土) 19:00:55.51ID:zCYrfxzC
modに関しては2と3には何かあるかもしれないが例えば5はどうか？といわれるとちょと疑問
今の時点ではね
0795１３２人目の素数さん
垢版 |
2018/04/28(土) 20:44:50.70ID:aSLESMuD
グラフ理論に「木」があるから名前は変えた方がいいかもね
グラフ理論といえば、コラッツ操作による有向グラフとしてなんかできないかなー、
と昔考えたけど、グラフ理論で扱われるのは有限頂点のグラフだった……
0797１３２人目の素数さん
垢版 |
2018/04/28(土) 21:05:09.07ID:aSLESMuD
というか「木」は数学では同値類になるか。
自分が書くならこんな感じ。

関数 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)
は同値関係となる。
0798１３２人目の素数さん
垢版 |
2018/04/28(土) 21:09:57.55ID:aSLESMuD
イメージは1を根とする木かな。
わからなくもないけど
・頂点が無限
・1→4→2→1のループがある
なのでなおさら木とは呼びづらい。
0799786
垢版 |
2018/04/28(土) 21:23:20.77ID:d9jkS/fs
確かに「木」だと誤解を招いてしまうかもしれませんね。
「束」のように複数の意味で使われる例もありますが…
良い名称を思いついたら変えようと思います。
0800１３２人目の素数さん
垢版 |
2018/04/29(日) 00:40:21.09ID:daW9MuG1
うーん、やっぱり木が一番しっくりくる。
もうしばらく様子を見ます。

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

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


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

命題
任意の木は 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 の倍数を含む。 □
0802786
垢版 |
2018/04/29(日) 18:35:28.76ID:daW9MuG1
>>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 でも成り立つ。□

（続く）
0803786
垢版 |
2018/04/29(日) 18:36:40.20ID:daW9MuG1
補題
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) となる。□
0804１３２人目の素数さん
垢版 |
2018/04/29(日) 22:12:16.24ID:Z6W4RKDj
mod 5とか mod 7について何か出すのは難しいかもしれないけど
3^n-1についてとかなら何か出せるんだろうか？
0805786
垢版 |
2018/04/30(月) 11:15:04.08ID:RzdNNNxX
>>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 が奇数の場合に帰着されます。
0806786
垢版 |
2018/04/30(月) 11:45:54.34ID:RzdNNNxX
偶数から奇数への帰着について先に書いておきます。

定理
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 が奇数の場合のみ考えようと思います。
0810786
垢版 |
2018/05/01(火) 19:52:19.63ID:w7yajc4M
>>808
いえ、それほどでも


個別の n, k について考えるだけならそれほどハードルは高くないと思いますので、
一緒に考えてくれる方がいたら嬉しいなと思います。
さしあたって次の目標は n=15, 19 あたりです。
0811１３２人目の素数さん
垢版 |
2018/05/01(火) 21:00:47.74ID:b6ssvKjY
予想
T を木とし、n, k を自然数とする。
このとき、ある a∈T が存在して a≡k (mod n) が成り立つ。

↑まだこれのイメージがわいてない段階だから一緒に考えるっつってもあんま期待すんなよｗ
0812１３２人目の素数さん
垢版 |
2018/05/01(火) 21:53:00.73ID:b6ssvKjY
まあ問題のとらえ方というか予想の立て方が、普通の人より高いところに目線があるんだろなって雰囲気は感じる。
0813１３２人目の素数さん
垢版 |
2018/05/01(火) 22:30:43.98ID:b6ssvKjY
予想がなかなかイメージ湧かないな〜
プロローグでプログラムを組もうとしたときのような困難さを感じるorz.
0814１３２人目の素数さん
垢版 |
2018/05/01(火) 23:05:13.72ID:b6ssvKjY
とりあえず、プログラム組んで虱潰しで潰していけばn=15とかもなにがしかの結果が出るのだろうか？
そんな甘くない？
0815１３２人目の素数さん
垢版 |
2018/05/01(火) 23:08:54.94ID:b6ssvKjY
例えば>>1なら>>786の予想を理解して、しらみつぶしで探索するようなプログラムを、書けそう？書けなさそう？
0816１３２人目の素数さん
垢版 |
2018/05/01(火) 23:19:15.11ID:b6ssvKjY
プログラムでやろうと思ったら結局、原始根である必要があるんだろうか？
うーん。わからん。
0817786
垢版 |
2018/05/01(火) 23:36:27.65ID:EK2mztLp
なるほどそんな感じですか…
ちょっと考えてみます
0819１３２人目の素数さん
垢版 |
2018/05/02(水) 00:04:01.57ID:ykYomvAh
x(2^n)-1→x(3^n)-1 (x,nは自然数)
がわかってるから、2か3が原始根ならどうとでもなる気が
0820786
垢版 |
2018/05/02(水) 00:46:18.38ID:uBxaRL/7
>>818
プログラムはド素人です。
上で言ったのは、「イメージがわかない」というのをどうにかできないかなーということです。
0822786
垢版 |
2018/05/02(水) 17:55:20.98ID:uBxaRL/7
この予想に至った経緯を図を交えて述べてみます。
そんな大層なものではないですが。

まず、木のイメージは次の図のような感じです。
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の倍数の場合だけ調べれば十分」
ということを考えたことがありました。
0823786
垢版 |
2018/05/02(水) 17:55:49.20ID:uBxaRL/7
それとは別に
・初期値が奇数の場合だけ調べれば十分
・初期値が 4n+3 の形の場合だけ調べれば十分
とかはよく見る話だと思います。

それで、この間ふと「これって一般化できないかな」と思ったのです。
すなわち「コラッツ予想は、初期値が n で割って k 余る数場合だけ調べれば十分」は成り立つのかと。
で、これを証明するにはどうすればいいかを考えた結果、
>>786の予想に落ち着きました。
0826１３２人目の素数さん
垢版 |
2018/05/02(水) 20:10:19.87ID:0C84qqBY
「コラッツ予想は初期値が3の倍数の場合だけ調べれば十分」
これはこのスレでも>>132で言及されているね
0827１３２人目の素数さん
垢版 |
2018/05/02(水) 20:28:11.26ID:0C84qqBY
「コラッツ予想は、初期値が n で割って k 余る数場合だけ調べれば十分」

こっちのほうがアイディアはわかりやすいな
0828１３２人目の素数さん
垢版 |
2018/05/02(水) 21:15:08.89ID:0C84qqBY
ん、「コラッツ予想は、初期値が n で割って k 余る数場合だけ調べれば十分」と>>786の予想が頭の中で微妙にすっきり繋がらないな
もうちょっと時間くれ
0830１３２人目の素数さん
垢版 |
2018/05/02(水) 21:55:27.60ID:0C84qqBY
てことは例えば「コラッツの予想は5の倍数だけ調べれば十分」も証明済みってことか
へ〜〜
0831１３２人目の素数さん
垢版 |
2018/05/02(水) 22:26:15.60ID:0C84qqBY
個別のnやkに対してどういう戦略で証明を進めていくのか説明してくれたらもしかしたらプログラムでしらみつぶし探索できるかもしれないな。
やや楽観的すぎるかもしれないが。

多分、>>1が実装してくれるｗｗ
0832786 ◆5A/gU5yzeU
垢版 |
2018/05/03(木) 00:08:17.82ID:VqsJsG3V
>>819
確かに使えそうですが…いまいち使い方が思いつきません。
もし具体的なアイデアがあればお願いします。

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


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

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

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


次は n=5 の場合の証明を書こうと思います。
0833786 ◆5A/gU5yzeU
垢版 |
2018/05/03(木) 13:16:10.01ID:VqsJsG3V
・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) なので、上の場合に帰着される。□
0834786 ◆5A/gU5yzeU
垢版 |
2018/05/03(木) 13:17:32.89ID:VqsJsG3V
・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) の場合に帰着される。□
0835786 ◆5A/gU5yzeU
垢版 |
2018/05/03(木) 13:19:00.64ID:VqsJsG3V
・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) に変えても証明できます。
0837righ1113 ◆OPKWA8uhcY
垢版 |
2018/05/03(木) 16:02:07.46ID:Z16wUiiY
ふと思ったのですけど、プログラムとして
・T(1)を列挙
・a∈T(1)がa≡k mod nかを調べる
(kとnには具体的な数を入れる)
とかやっても意味ないですよね……
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況