トップページ⇒数学
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/
コラッツ予想について、証明を考えてみました。
ご指摘ご意見ご感想など、ぜひよろしくお願いします。
0689１３２人目の素数さん
垢版 |
2017/06/23(金) 21:08:08.37ID:8j+4jyzS
>>688訂正
すまん、ガウスの記号の意味は正負どちらでもそれ以下の最大の整数にする演算、つまりfloorと同じ意味だった
ともかく[ ]はガウスの記号だと思うよ
（なぜかガウスの記号には高校数学だと[ ]を使うのに対して、大学以上の数学だと下だけに爪が出てる記号（つまり」とその左右反転形）を使うよね）
0690１３２人目の素数さん
垢版 |
2017/06/24(土) 10:26:51.33ID:crDj8neM
コラッツパターンは、コラッツの操作によって得られるもともとの情報群。
複雑すぎて手に負えない。

左端を伸ばすパターンは、コラッツパターンから
情報を落とすことで得られるポンコツな指標。
操作を進めるごとに情報が落ちていくので、どんどん精度が悪くなる。
こんなものがコラッツパターンの実態を捉えているなんてあり得ないので、
コラッツパターンと比較したところで大して得るものは無い。

「左端傾き」「右端傾き」といった考え方もゴミである。
離散的な対象に対して、大域的にであれ局所的にであれ「傾き」に相当する量を
定義したところで、それは極めて大雑把な荒い指標にしかならない。
そんな頼りない道具だけでコラッツ予想が制御できるわけがない。
0691１３２人目の素数さん
垢版 |
2017/06/24(土) 10:34:09.83ID:crDj8neM
・・・と、御託はこのあたりにして、具体的に間違いを指摘する。
>>677の(17)の不等式が完全に間違っている。(17)では

[s']＝[(log_2 x_0)/(t/s−log_2 3)] ＜ 3x_0

となっているが、分母の (t/s−log_2 3) が非常にゼロに近い場合、

[s']
＝ [(log_2 x_0)/(t/s−log_2 3)]
＝ [(log_2 x_0)/(ほぼゼロ)]
＝ [(log_2 x_0) * (1/ほぼゼロ)]
＝ [(log_2 x_0) * 滅茶苦茶デカイ係数 ]
＞ 3x_0

となり得るので、この場合、不等号が逆転することになる。

「このような可能性は実際には起こらず、確実に [s'] ＜ 3x_0 が成り立つ」

と言うのであれば、そのことを証明しなければならない。
しかし、末尾の coq では証明されていない。

「図を使って傾きを比較することで [s'] ＜ 3x_0 が成り立つ」

と言っているようにも見えるが、図が無い上に、それぞれのパターンを
どのように配置してどこを原点としてどのようにして直線の傾きを
比較するのか文章からは読み取れないので判断のしようがない。
0692１３２人目の素数さん
垢版 |
2017/06/24(土) 10:40:58.68ID:crDj8neM
なお、きちんと精査はしていないが、
(1)〜(23)のうち、(17),(22),(23)を除く全ての式は
おそらく正しいと思われる。なぜなら、これらの式では

・ 記号の定義
・ 単なる等式の変形
・ 自明な評価による自明な不等式の導出

のいずれかの行為しか行っていないからだ。
パターンのずれとか傾きの違いがどうこうなどと
御託を並べているものの、その実態は上記の3項目のみである。

ちなみに、(22),(23)で間違っている箇所は、途中で(17)を使っているところであり、
それゆえに間違いとなる。従って、実質的には(17)のみが間違いとなる。
そして、それ以外の個所では上記の3項目による自明な行為しか行っていないので、
結局、>>677ではコラッツ予想の難しさを(17)に責任転嫁しているだけということになり、
コラッツ予想について何も言えていないことになる。
0693righ1113 ◆OPKWA8uhcY
垢版 |
2017/06/24(土) 12:53:18.60ID:JGgmjFB8
指摘ありがとうございます。見直したところ、
(t/s−log_2 3) > 0 のところを、
(t/s−log_2 3) > 1 と勘違いしていました。
またしてもダメでした……
お騒がせしました。
0694１３２人目の素数さん
垢版 |
2017/06/26(月) 21:23:01.72ID:1jLGU0ra
乙。
頭の良い奴が来てくれたか。
俺も力になれればいいんだが、なかなか難しい。
0695１３２人目の素数さん
垢版 |
2017/08/06(日) 18:21:21.93ID:oDKJI1vJ
耳栓をしたら世界が変わってワロタ
0696￥ ◆2VB8wsVUoo
垢版 |
2017/08/06(日) 18:21:56.37ID:+CYdGQny
☆☆☆馬鹿板は数学徒の脳を腐らせる悪い板であり、そやし廃止してナシにすべき。☆☆☆

￥
0697１３２人目の素数さん
垢版 |
2017/08/06(日) 20:09:55.82ID:oDKJI1vJ
耳栓をしたら世界が変わってワロタ
0705１３２人目の素数さん
垢版 |
2017/08/07(月) 03:17:18.68ID:/yQwEvEc
￥さんが数学板に極めて批判的であるのは良く承知していますが、このスレは荒らさないであげて下さいよ
珍しく自分なりに数学をやっている人がその研究経過について報告してくれているのですから

数学板のすべてのスレが腐っているわけではありません
他の板でも腐っているスレもあれば数学板でもこのスレのように「数学」という言葉本来の目的で使用されているスレもあるのですから
また数学板の全てのスレで各スレの投稿者や読者の集合が一致しているわけでもありません
（もしそうだと主張なさるならば数学の証明として通用するレベルの論理的な証明か又は２ちゃんねる数学板のログのような客観的で確実な証拠でもご提示ください）

板で腐っているかいないか決めつけるのは人の知性の有無を国籍や肌の色で判断するのと同じ乱雑で反知性的な判断であって
数学や知性を愛する￥さんに相応しい行動とは思えません

スレ主さんや他の住人の方々、スレ違いの投稿失礼しました
0708￥ ◆2VB8wsVUoo
垢版 |
2017/08/07(月) 06:47:24.69ID:/rspiZFz
☆☆☆馬鹿板は数学徒の脳を腐らせる悪い板であり、そやし廃止してナシにすべき。☆☆☆

￥
0719１３２人目の素数さん
垢版 |
2017/08/07(月) 08:44:46.18ID:0YzkEl/p
耳栓をしたら世界が変わってワロタ
0720１３２人目の素数さん
垢版 |
2017/08/07(月) 15:14:50.99ID:/yQwEvEc
>>706
現代数学の系譜スレでは￥氏はちゃんと会話をなさってるので
こちらが適切に発言すれば言葉は通じると思ったわけです
0721１３２人目の素数さん
垢版 |
2017/08/07(月) 15:17:03.95ID:0YzkEl/p
耳栓をしたら世界が変わってワロタ
0722righ1113 ◆OPKWA8uhcY
垢版 |
2017/10/08(日) 09:15:13.38ID:StPF7u7V
メルセンヌ素数 2^110503 - 1 って
止まらないことないですか？
0723１３２人目の素数さん
垢版 |
2017/10/08(日) 11:28:20.81ID:Cutv7rfi
計算機でまわしたのか？
単にデカいから時間かかってるだけじゃないのか？
0724righ1113 ◆OPKWA8uhcY
垢版 |
2017/10/08(日) 11:36:26.39ID:V4WPWhh+
2^110503-1が大体30000桁で、
10時間程走らせて、今45000桁ぐらいなのです。
また止まったら報告します。
0725１３２人目の素数さん
垢版 |
2017/10/08(日) 15:27:53.11ID:m0FVLI/3
2^n-1をコラッツの操作かけると3^n-1になるんだろ？30000桁が45000桁になってもさほど特別とは思わんな
0726１３２人目の素数さん
垢版 |
2017/10/08(日) 15:58:04.91ID:Pp5mcjdG
>>725で指摘されてるが、2^n-1から始めたいなら、
バカ正直に2^n-1からスタートさせるのではなく、
3^n-1からスタートさせないと無駄にも程があるな
0727１３２人目の素数さん
垢版 |
2017/10/08(日) 23:28:04.64ID:Cutv7rfi
ちなみに>>1の計算機だと３００００万桁の数値に対して何コラッツステップ/secくらいのスピードで計算できんの？
0729righ1113 ◆OPKWA8uhcY
垢版 |
2017/10/09(月) 00:59:44.36ID:Vv+x6w6w
奇数→奇数を1ステップとして、
2361コラッツ奇数ステップ/sec　ぐらいですかね。
0730１３２人目の素数さん
垢版 |
2017/10/09(月) 01:11:15.90ID:93q6V3EV
すまん、聞いてはみたものの速いのか遅いのかよくわからんｗ
プログラム言語は何使ってんの？
0731righ1113 ◆OPKWA8uhcY
垢版 |
2017/10/09(月) 01:19:17.60ID:Vv+x6w6w
僕もよく分からないですw
言語はHaskellを使っています。多倍長整数が標準搭載されているので。
0732１３２人目の素数さん
垢版 |
2017/10/09(月) 01:28:20.34ID:93q6V3EV
Haskellか〜
プロトタイプ作るのには良いかもしれんが計算ぶん回すのにはどうなんだろ？
C++とまではいかなくても速度高めの言語も試してみるといいかもね。
0734１３２人目の素数さん
垢版 |
2017/10/09(月) 01:53:47.71ID:93q6V3EV
ん〜haskell最速ってホンマかいなｗ
どんな理屈でそういう結果になるのか想像つかないｗ
0735１３２人目の素数さん
垢版 |
2017/10/09(月) 02:00:31.03ID:93q6V3EV
haskellだけ多倍長になってないとかかなぁ
うーん。なんか違和感あることはある。
0736righ1113 ◆OPKWA8uhcY
垢版 |
2017/10/09(月) 02:04:02.85ID:Vv+x6w6w
多分、多倍長整数と並列計算の組み合わせが
低コストで上手くいっているのがHaskellだと思います。
自信は無いですがw
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のみに注目するのですか？
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況