コラッツ予想がとけたらいいな
■ このスレッドは過去ログ倉庫に格納されています
525 名前:132人目の素数さん[sage] 投稿日:2012/09/03(月) 18:24:27.22 http://d.hatena.ne.jp/righ1113/ コラッツ予想について、証明を考えてみました。 ご指摘ご意見ご感想など、ぜひよろしくお願いします。 >>687 [ ]はガウスの記号、つまり端数を丸めて(絶対値で見た時に切り捨てて)整数にする演算のことじゃないの? >>688 訂正 すまん、ガウスの記号の意味は正負どちらでもそれ以下の最大の整数にする演算、つまりfloorと同じ意味だった ともかく[ ]はガウスの記号だと思うよ (なぜかガウスの記号には高校数学だと[ ]を使うのに対して、大学以上の数学だと下だけに爪が出てる記号(つまり」とその左右反転形)を使うよね) コラッツパターンは、コラッツの操作によって得られるもともとの情報群。 複雑すぎて手に負えない。 左端を伸ばすパターンは、コラッツパターンから 情報を落とすことで得られるポンコツな指標。 操作を進めるごとに情報が落ちていくので、どんどん精度が悪くなる。 こんなものがコラッツパターンの実態を捉えているなんてあり得ないので、 コラッツパターンと比較したところで大して得るものは無い。 「左端傾き」「右端傾き」といった考え方もゴミである。 離散的な対象に対して、大域的にであれ局所的にであれ「傾き」に相当する量を 定義したところで、それは極めて大雑把な荒い指標にしかならない。 そんな頼りない道具だけでコラッツ予想が制御できるわけがない。 ・・・と、御託はこのあたりにして、具体的に間違いを指摘する。 >>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 が成り立つ」 と言っているようにも見えるが、図が無い上に、それぞれのパターンを どのように配置してどこを原点としてどのようにして直線の傾きを 比較するのか文章からは読み取れないので判断のしようがない。 なお、きちんと精査はしていないが、 (1)〜(23)のうち、(17),(22),(23)を除く全ての式は おそらく正しいと思われる。なぜなら、これらの式では ・ 記号の定義 ・ 単なる等式の変形 ・ 自明な評価による自明な不等式の導出 のいずれかの行為しか行っていないからだ。 パターンのずれとか傾きの違いがどうこうなどと 御託を並べているものの、その実態は上記の3項目のみである。 ちなみに、(22),(23)で間違っている箇所は、途中で(17)を使っているところであり、 それゆえに間違いとなる。従って、実質的には(17)のみが間違いとなる。 そして、それ以外の個所では上記の3項目による自明な行為しか行っていないので、 結局、>>677 ではコラッツ予想の難しさを(17)に責任転嫁しているだけということになり、 コラッツ予想について何も言えていないことになる。 指摘ありがとうございます。見直したところ、 (t/s−log_2 3) > 0 のところを、 (t/s−log_2 3) > 1 と勘違いしていました。 またしてもダメでした…… お騒がせしました。 乙。 頭の良い奴が来てくれたか。 俺も力になれればいいんだが、なかなか難しい。 ☆☆☆馬鹿板は数学徒の脳を腐らせる悪い板であり、そやし廃止してナシにすべき。☆☆☆ ¥ ¥さんが数学板に極めて批判的であるのは良く承知していますが、このスレは荒らさないであげて下さいよ 珍しく自分なりに数学をやっている人がその研究経過について報告してくれているのですから 数学板のすべてのスレが腐っているわけではありません 他の板でも腐っているスレもあれば数学板でもこのスレのように「数学」という言葉本来の目的で使用されているスレもあるのですから また数学板の全てのスレで各スレの投稿者や読者の集合が一致しているわけでもありません (もしそうだと主張なさるならば数学の証明として通用するレベルの論理的な証明か又は2ちゃんねる数学板のログのような客観的で確実な証拠でもご提示ください) 板で腐っているかいないか決めつけるのは人の知性の有無を国籍や肌の色で判断するのと同じ乱雑で反知性的な判断であって 数学や知性を愛する¥さんに相応しい行動とは思えません スレ主さんや他の住人の方々、スレ違いの投稿失礼しました 昔からあるスレ攪拌のためのスクリプトかなんかじゃないのかね ☆☆☆馬鹿板は数学徒の脳を腐らせる悪い板であり、そやし廃止してナシにすべき。☆☆☆ ¥ >>706 現代数学の系譜スレでは¥氏はちゃんと会話をなさってるので こちらが適切に発言すれば言葉は通じると思ったわけです メルセンヌ素数 2^110503 - 1 って 止まらないことないですか? 計算機でまわしたのか? 単にデカいから時間かかってるだけじゃないのか? 2^110503-1が大体30000桁で、 10時間程走らせて、今45000桁ぐらいなのです。 また止まったら報告します。 2^n-1をコラッツの操作かけると3^n-1になるんだろ?30000桁が45000桁になってもさほど特別とは思わんな >>725 で指摘されてるが、2^n-1から始めたいなら、 バカ正直に2^n-1からスタートさせるのではなく、 3^n-1からスタートさせないと無駄にも程があるな ちなみに>>1 の計算機だと30000万桁の数値に対して何コラッツステップ/secくらいのスピードで計算できんの? 奇数→奇数を1ステップとして、 2361コラッツ奇数ステップ/sec ぐらいですかね。 すまん、聞いてはみたものの速いのか遅いのかよくわからんw プログラム言語は何使ってんの? 僕もよく分からないですw 言語はHaskellを使っています。多倍長整数が標準搭載されているので。 Haskellか〜 プロトタイプ作るのには良いかもしれんが計算ぶん回すのにはどうなんだろ? C++とまではいかなくても速度高めの言語も試してみるといいかもね。 そうですね、考えてみます。 そういえば今年の始め頃にこんなことをやっていました。 Go,C++,F#,Haskellでコラッツを計算してみた http://d.hatena.ne.jp/righ1113/20170209#1486589174 ん〜haskell最速ってホンマかいなw どんな理屈でそういう結果になるのか想像つかないw haskellだけ多倍長になってないとかかなぁ うーん。なんか違和感あることはある。 多分、多倍長整数と並列計算の組み合わせが 低コストで上手くいっているのがHaskellだと思います。 自信は無いですがw >>726 3^110503-1で再チャレンジしました。 一日かかって40000桁まで下がったのですが、これ以上続けるのはしんどいです。 グダグダですみません。 停止するかどうかを 3^110503-1 のときに 確かめようとしてる時点で既にグダグダだけどな。 なぜなら、どうせ停止するに決まってるからだw それが 1 になるかは分からないが、少なくとも 停止することは確実だと予想してよいだろう。 無論それ自体も未解決ではあるのだが、 停止「しない」ことが期待されるような良い根拠はどこにも無く、 逆に必ず停止すると思しき良い根拠はいくつもあるわけで。 例えばループする自然数があったとして、ループの周期が非常に長く履歴がメモリに納まらないようなことが想定される場合、 ループを検出するアルゴリズムとしてどのようなものが考えられるだろうか? >>739 1ステップずつ移動するのと2ステップずつ移動するのを用意して 同時に走らせて、両者の値が一致するかどうかを毎回チェックする。 一致したらループに入ってるし、逆にループに入ってたら 必ず一致するタイミングが訪れる。 〔問題〕 自然数nを1つ選び、2nを元に3倍して2を足す操作をk回繰り返す。 k を 1,2,3,… とすると、いつかは 2の累乗になる? 一般項 (3^k)(2n+1)- 1 http://rio2016.5ch.net/test/read.cgi/math/1502032053/171-179 面白スレ24 ABC予想が解かれたとかなんとか コラッツも解けるといいですね >>754 そうですね〜 成果は出ていないのですが、もう少しだけ頑張ってみます。 >>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)、……と増大するので、 ずれも際限なく増大していきます。 ループ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です。 まとめると、 ループ1周期sで、コラッツパターンと左端を伸ばすパターンのずれが1、3周期でずれが3としたとき、 s > x_0(ループ中の最小値) です。 あるいは同じことですが、 ループ1周期でずれが1、3周期でずれが3としたとき、 1〜nまででコラッツの反例がなければ、 n周期以下のループは存在しない です。 新しい証明を考えました。 https://github.com/righ1113/collatzProof ポイントは、「最下位からの連続するビット1の個数」の帰納法で考えることです。 >>761 すみませんが、よく分からないです。 1回でも小さくなることを証明すれば、十分じゃないでしょうか。 nの全ての値がコラッツ操作で小さくなる→n+1の全ての値がコラッツ操作で小さくなる が言えるので、帰納法により、全ての値がコラッツ操作で小さくなる ことが言えると思います。 8x+3(n=2)→12x+5(n=1)→18x+8(n=0)→9x+4(n=?) 補題1-2がn=1の場合に偽じゃねえかな 【補題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も更新しました。 問題は「最初の数より小さくなる」かどうかだから次は16x+7で同じことになるね ・2x→x ・4x+1→3x+1 では小さくなっているが n>2では「最初の数より小さくなる」ことが保証できんのだ 2x→xによって整数全体に移るせいで問題がフラクタル構造持ってる 再帰的な解決はここを回避しないと封じられてしまう気がする >>765 すみませんよく分からないです…… じっくり考えてみます。 8x+3(n=2)→12x+5(n=1)=4(3x+1)+1→3(3x+1)+1 ^^^^^^^^^^^^^^^^^^^^ ここでは小さくなっているが、 ^^^^^^^^^^ この最初の数より小さくなっていない、でしょうか。 理解しました。 ◆◆◆■■■■ 15→127 □◆◆■■■□■ 23→95 □□◆■■□□□■ 35→71 □□□■□■□■■ 53 □□□□□□□■□■ 5 □□□□□□□□□□■ 1 新しいコラッツパターンを考えました。 ◆を追加します。 すると、nの大小=x_sの大小が言えるので、 smaller(n+1)ならば、smaller(n+2) が言えると思うのですが、どうでしょうか。 2x+1→6x+4→3x+2 2x+0→1x+0 をセットの操作として考える xの係数は奇数なのでxの偶奇で次の偶奇が定まる xを2x+1、2x+0で置換してもう1セット操作する xの係数は奇数(というか3の冪)となるのでやはり次の偶奇はxの偶奇で定まる あとは帰納法で「下位nビットがnセット操作分の変化を定める」のがわかる 下位ビット固定は固定した分しか定まらないのでうまくいかない印象 コラッツパターン2にしたら、 4x+1が小さくならなくなってしまいました。無念。 構成を大幅に変えました。 コラッツパターン2も変えました。 コラッツ問題の解決の役に立つかどうかはわからんが、思いついたので投下。 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 以下、超略証。 (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からは周期の中での単調性が示せる。 (格子状の道の最短経路の曲がり方を一つづつ変えて行くように) >>774 >(格子状の道の最短経路の曲がり方を一つづつ変えて行くように) ここがだめ(全順序にならん)なので不成立。 一定の条件のもとで、近い数は近くなる、くらいしか言えてないか。 1つ予想を立ててみた。 自然数全体の集合を N とする。 まず木を定義する。 定義 自然数 a に対し、集合 T(a) を T(a) = {b∈N | a と b はコラッツ操作によって同じ数に到達する} と定める。 T(a) の形の集合を木と呼ぶ。 コラッツ予想が真であることは、自然数全体が1つの木をなすことと同値である。 で、次のように予想した。 予想 T を木とし、n, k を自然数とする。 このとき、ある a∈T が存在して a≡k (mod n) が成り立つ。 コラッツ予想が正しければ、T は N に一致するので、明らかにこの予想は成り立つ。 逆にいえば、予想が成り立たないような T, n, k が存在する場合、コラッツ予想も偽であることになる。 基本的な操作を補題としてまとめておく。 補題 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 2つの自然数 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。□ まだいろいろと書けることはあるけど、反応を見ながらということで。 ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.1 2024/04/28 Walang Kapalit ★ | Donguri System Team 5ちゃんねる