コラッツ予想がとけたらいいな
■ このスレッドは過去ログ倉庫に格納されています
525 名前:132人目の素数さん[sage] 投稿日:2012/09/03(月) 18:24:27.22 http://d.hatena.ne.jp/righ1113/ コラッツ予想について、証明を考えてみました。 ご指摘ご意見ご感想など、ぜひよろしくお願いします。 つまり、コラッツ操作で1にたどり着いた後は、 (1+1/(3*x0))...(1+1/(3*x_s-1)) < 2^3 が成り立たなくなります。 とりあえず、色々コンピュータで検証してます。 4.1 Xsを12ステップで区切ったときライトエッジパターンに8個以上1が入ることはない、についてだけど 2連続の0はない 3連続の1はない 11011のパターンはない で計算したところ以下のパターンが出てきたんだが。 110101101011 これは問題になる? 110101101011は、二回繰り返すと 110101101011110101101011となって、 3連続の1が出てくるので、除外されます。 Coqでは、>>468 のpdfで、25ページの下の方の (filter remove_1_1_1 (map (cycle 2 nil) remove_8_12’)で、 cycle 2でパターンを二回繰り返して、filter remove_1_1_1で3連続の1を除外しています。 どゆこと? ライトエッジパターンは必ず周期12のループになるの? そっかー、ならないですね。 二周期目を調べる時は、 12ステップで除外しきれなかったパターンの直積を取って、filterをかけないとダメですね。 ……と思ったら「12ステップで除外しきれなかったパターン」って上の110101101011しかないんですね。 だったらcycle 2も直積も同じことで、110101101011110101101011となって、やはり除外されます。 これでどうでしょうか? いや、なんか怪しいです。 もうちょっと考え直してみます。 他スレのご指摘により数式だけでなく日本語の説明を加えました。 諸兄におかれましては何卒よろしくご査収の上ご批評賜りたくよろしくお願い申し上げます。 http://koubeichizoku.ix-web.tk/collatz/ ここで論じられているビットパターンは拙論では 2^p×3^m×g±1 (gは 6a±1) として捉えており、これらは素因数分解の一意性 からユニークな数であることに着目しています。 コラッツ予想の題意に従った奇数から奇数への変化のうち奇数間で増大するものを ≫+で表せば 2・2^p・g−1 ≫+ 2・2^(p-1)・3^1・g−1≫+ 2・2^(p-2)・3^2・g−1 ... ≫+ 2・2^1・3^(p-1)・g−1 ≫+ 2・3^p・g−1 となって L(p,g):={2・2^p・g−1,2・2^(p-1)・3^1・g−1, 2・2^(p-2)・3^2・g−1 ... ,+ 2・2^1・3^(p-1)・g−1 ,2・3^p・g−1} となって 相異なる(p,g)のL集合同士は互いに素 また同じく相異なるLの和集合同士も互いに素となります。(L(p,g)∪ L(p',g')=φ)(p≠p’)∨(g≠g’) ここで論じられているビットパターンは拙論では 2^p×3^m×g±1 (gは 6a±1) として捉えており、これらは素因数分解の一意性 からユニークな数であることに着目しています。 コラッツ予想の題意に従った奇数から奇数への変化のうち奇数間で増大するものを ≫+で表せば 2・2^p・g−1 ≫+ 2・2^(p-1)・3^1・g−1≫+ 2・2^(p-2)・3^2・g−1 ... ≫+ 2・2^1・3^(p-1)・g−1 ≫+ 2・3^p・g−1 となって L(p,g):={2・2^p・g−1,2・2^(p-1)・3^1・g−1, 2・2^(p-2)・3^2・g−1 ... ,+ 2・2^1・3^(p-1)・g−1 ,2・3^p・g−1} とすれば、 相異なる(p,g)のL集合同士は互いに素 また同じく相異なるLの和集合同士も互いに素となります。(L(p,g)∪ L(p',g')=φ)(p≠p’)∨(g≠g’) >>479 coqが通ったのに何が怪しいの? なんのためのcoqなの? coqは通ったけど、通った命題そのものがトンチンカンな主張だったってこと? >coqは通ったけど、通った命題そのものがトンチンカンな主張だったってこと? まあ、そういう事です。 Coqに通すまでの論証に穴があったという事です。 そうならないように始めの命題からCoqで一気通貫で証明を通すことが望ましいね。 実際には難しいだろうけど。 110101101011は除外出来ない事が分かりました。 そこで証明を次のように修正します。 12区切りのライトエッジパターンに110101101011が現れたとする。 末尾は1なので、次の12区切りは先頭が0である。 「先頭が1」「2連続の0」「3連続の1」「1,1,0,1,1」を除外した、12区切りで1が7個入るパターンは、 次の6つしかない。(Haskellで確認済み) [0,1,0,1,0,1,1,0,1,0,1,1] [0,1,0,1,1,0,1,0,1,0,1,1] [0,1,1,0,1,0,1,0,1,0,1,1] [0,1,1,0,1,0,1,1,0,1,0,1] [0,1,1,0,1,0,1,0,1,1,0,1] [0,1,0,1,1,0,1,0,1,1,0,1] 1~3個目は11で終わっているため、次の12区切りも0始まりとなってループする。 再び110101101011が来る余地は無い。 4~6個目は、次の12区切りで1始まりが可能なので、さらに調べる。 「先頭が10」で、「2連続の0」「3連続の1」「1,1,0,1,1」を除外した、12区切りで1が7個入るパターンは、 次の8つしかない。(Haskellで確認済み) [1,0,1,0,1,0,1,0,1,0,1,1] [1,0,1,0,1,0,1,1,0,1,0,1] [1,0,1,0,1,1,0,1,0,1,0,1] [1,0,1,1,0,1,0,1,0,1,0,1] [1,0,1,0,1,0,1,0,1,1,0,1] [1,0,1,1,0,1,0,1,1,0,1,0] [1,0,1,1,0,1,0,1,0,1,1,0] [1,0,1,0,1,1,0,1,0,1,1,0] 1個目は11で終わっているため、次の12区切りも0始まりとなってループする。 2~5個目は1で終わっているため、次の12区切りも1or0始まりとなってループする。 6,7個目は、連続して並べると、 110101101011 [0,1,*,*,*,*,*,*,*,1,0,1] [1,0,1,1,0,1,0,1,1,0,1,0] 110101101011 [0,1,*,*,*,*,*,*,*,1,0,1] [1,0,1,1,0,1,0,1,0,1,1,0] となって「1,1,0,1,1」が現れるので除外される。 8個目は、連続して並べると、 110101101011 [0,1,*,*,*,*,*,*,*,1,0,1] [1,0,1,0,1,1,0,1,0,1,1,0] 110101101011 となって「1,1,0,1,1」が現れるので110101101011にはならない。 よって、二回以上110101101011が現れることはない。 初期値をX0 とy0B * 2^(py0+2)(1ずらし→2ずらし)から始めれば、 Xs はysB * 2^(pys+2) を超えないので、Xs < ysB * 2^(pys+2) である。 さて、これをCoqでどうやってやろう…… どうせその論証にも穴がある。 都合の悪い並びはいつまで経ってもなくならない。 穴を埋めようとすると >「先頭が10」で、「2連続の0」「3連続の1」「1,1,0,1,1」を除外した こんな感じの細かい条件がさらに追加される。 それでもなお、都合の悪い並びはなくならない。 キリがないどころか、そもそもこのやり方では本質的に不可能。 0と1の並び方の規則を探求すること自体が全くの無駄。 こいつらは基本的にランダム列に近づきたがっている。 途中で不完全燃焼を起こしてループに陥るだけで、 それまでの間はランダム列に近づきたがっている。 そうやって規則がない方向に行こうとしている対象について 規則を探求しても、うまく行くわけないだろ。 それよりも、「ランダム列に近づきたがってる」ことを 実際に証明した方が早い(もちろん現状では未解決)。 >>489 これ検証すんの結構つらいわw Coqでなんとかならんか? 1が7個のパターンだけ考えてるみたいだけど 1が6個以下のパターンを除外していい理由がよくわからん。 Coqは考え中です。 (ちゃんとやってないですけど) 1が6個のパターンは、0,0が除外されるので [0,1,0,1,0,1,0,1,0,1,0,1] [1,0,1,0,1,0,1,0,1,0,1,0] しかないんんですけど、こんなパターンは無いかなあと。 (どこかで1,1,が現れるはず) 1が5個以下のパターンは、必ず0,0が含まれるので、 全て除外されます。 >>こんなパターンは無いかなあと。 数学の証明しようってのにずいぶんずぼらだなw まあ気持ちはわかるが。 ポエムのうちは読む気はないけど証明されたら眺めてみようかくらいに思ってる人はそれなりにいると思うからがんばってね。 12区切りで1が6個入るパターンは除外される証明ができました。 >>468 の7ページを見ながらご覧下さい。 http://cdn-ak.f.st-hatena.com/images/fotolife/r/righ1113/20160628/20160628023431.jpg ライトエッジパターンでは「2連続の0」「3連続の1」「1,1,0,1,1」に加えて「0,1,0,1,0,1,0」 も除外されるという事です。 >>468 発散する初期値がないことの証明も間違ってるように見える。 実際に (log_2 x_s)/s の挙動を計算してみると、 発散する初期値があろうがなかろうが、無条件で有界であることが分かる。 まず、9ページ目の(3)式はコラッツの軌道のsステップ目を表現しただけだから、 何の条件もなしに成り立っている。以下、(3)式から出発して x_s = x_0(3^s/2^t)(1+1/(3x_0))・・・(1+1/(3x_{s−1})) ≦ x_0(3^s/2^t)(1+1/3)・・・(1+1/3) = x_0(3^s/2^t)(1+1/3)^s = x_0(3^s/2^t)(4/3)^s ≦ x_0(3^s)(4/3)^s = x_0 4^s となるので、log_2 x_s ≦ log_2 x_0+slog_2 4 となって、 (log_2 x_s)/s ≦(log_2 x0)/s + 2 となる。よって、 発散する初期値があろうがなかろうが、無条件で有界になっている。 このことから、pdfの10ページ目にある 「 Here, from Fig.3 (傾きが垂直に近づくので) 」 のところは自動的に間違いとなる。 こういうのはどうでしょうか。 xは発散するとする。 (1+1/3x_0)…(1+1/3x_{s-1}) < 2^4 だから (1+1/3x_1)…(1+1/3x_s) < 2^4 も成り立つ。 t=saと置き、(1+3/t)^t < (1+1/3x_1)…(1+1/3x_s)が成り立つようにaを定める。 s→∞でt→∞だから、 lim[t→∞](1+3/t)^t = e^3 ≒ 20 > 16 だから、 無限大に辿り着く前に16を超える。越えた所をs'と置くと、 (1+1/3x_1)…(1+1/3x_s') > 16 となって、(1+1/3x_1)…(1+1/3x_s') < 2^4 と矛盾する。 >>499 >t=saと置き、(1+3/t)^t < (1+1/3x_1)…(1+1/3x_s)が成り立つようにaを定める。 問題外。x_sの発散スピードが大きいとき、そのようなaは取れない。 コラッツの問題を舐めるな。 t=e^sとか、t=s!とかにしてもダメなんでしょうか? >>501 どうも君は不等式に対する感覚がイカれてるね。 パッと見てすぐに分かる間違いに全く気づいてない。 tが大きければ大きいほど、(1+3/t)^t は e^3 に近づくのだから、余計に (1+3/t)^t < (1+1/3x_1)…(1+1/3x_s) が成り立ちにくくなるだけだろ。 ていうか、x_1からx_sまでが物凄い勢いで大きければ、 (1+1/3x_1)…(1+1/3x_s) はほとんど 1 に等しいのだから、もはや (1+3/t)^t < (1+1/3x_1)…(1+1/3x_s) なんて成り立たないでしょ。 >>503 より詳しく説明しよう。 もし発散する初期値が存在するならば、次が成り立つことが証明できる。 ∀ε>0, ∃x_0 s.t. x_0は発散する初期値であり、かつ (1+1/3x_1)…(1+1/3x_s) < 1+ε (s∈N). このことから、(1+1/3x_1)…(1+1/3x_s) を統一的に下から押さえることができる定数は 「 1 」しかないことが分かる。つまり、x_0が発散する初期値ならば、 1 < (1+1/3x_1)…(1+1/3x_s) (s∈N) が成り立つということ。しかし、この不等式は自明なので、何の役にも立たない。 結局、この方針では原理的に不可能。 ん〜識者乱入か? 俺じゃよくわからんし勘違いを防ぐためにも なるべくCoqで証明を通してほしいよね。 もしちゃんとZs < Ys <= Xs < ysB * 2^(pys+2) < 8Zs が言えたら、 Zsと8Zsのずれは3で、これがずっと変わらない って無限大までいっても変わらないって事だから xsが発散してもずれは3以下なんだと、今気づかせてもらった。 という訳で、無限大に発散する方はあきらめます。 4-2-1以外のLoopがない方に注力します。 >>1 はいまどうしてるの? まだ頑張ってんの? それとも休憩中? >>489 の状態遷移図の穴が埋められないんです。 ちょっと休憩中です。 >>>489 の状態遷移図の穴が埋められないんです。 穴は埋まらないよ。この方針じゃ原理的に不可能。 なんで分からないのかなあ。>>506 のときみたいに 「これじゃ本質的にダメなんだ」って心の底から悟れよ。 ダメなんだよこれじゃ。ダメなの。このやり方じゃ解けないの。 本質的に解けないことちゃんと数学的に証明をしてあげないと。 頭ごなしに否定するだけじゃ納得するはずないでしょ。 >>511 数学的に証明するのはムリ。 しかし、ほぼ確実な状況証拠はある。 3n+1版ではなく、an+1版のコラッツ予想を考える(ただしaは7以上の奇数)。 この場合、ほとんどの初期値でコラッツの軌道が発散することが予想されている。 軌道上に出現する各々の値の偶奇を0,1で横一列に並べると、 どうもその列は、ほとんどの初期値で2進正規になっているように見える。 もし2進正規になってることが証明できたならば、コラッツ予想でおなじみの 「軌道上では偶数と奇数が1/2ずつの確率で出現しそう」というヒューリティクスが 実際に正しいことが分かり、「ほとんどの初期値で発散する」という予想も正しいことが確定する。 おそらく、コラッツの軌道は本質的にランダムになりたがってる。 もともとの3n+1版でも同じことで、やはりランダムになりたがってる。 しかし、こちらの場合は掛ける数が「3」であるがゆえに、十分大きな数になれず、 それゆえに自由度が低下し、途中で不完全燃焼を起こしてループに陥る。 が、それまでの間はランダム列に近づきたがっている。初期値を大きく取れば取るほど、 ランダム列に近づきたがる期間も長くなるので、その間で幾らでも抜け穴となるパターンが生じうる。 だから本質的にムリなのだ。(続く) (続き) ライトエッジの「抜け穴」と似たような現象は、以下の箇所にも見られる。 英語版のコラッツ予想の記事を見ると、 >In particular, Krasikov and Lagarias showed that the number of integers in the interval [1,x] >that eventually reach one is at least proportional to x^0.84.[19] という記述がある。区間[1,x]に属する自然数のうち、コラッツの変換によって1になる数の比率は、 少なくとも x^{0.84} はある、という驚くべき文章である。 文献[19]をかいつまんで説明すると、「コラッツの変換によって1になる自然数の集合」を、 ある種のパラメータで分割して、いくつかの集合に分けるところから始まる。 それらの集合の間に定まる漸化式を使って、x^{0.84}という評価を得ている。 この漸化式が完全に制御できれば、もっといい結果が出るわけだが、 漸化式がイジワルな形をしており、漸化式を展開するたびにランダム性が増してしまって制御できなくなる。 そこで、途中で評価を落として不等式の形にすることで、不等式の左辺と右辺に何とかパターン性を 出現させ、それによって問題を対処する。その結果、x^{0.84} という中途半端な数字になってしまう。 ライトエッジの抜け穴は、この「評価を落としてパターン性を出現させる」ところに どことなく対応しているように見える。ライトエッジを完全に解析すると、まず間違いなく、 そのパターンは有限通りには収まらず、複雑な形の漸化式で記述されることになる。 その漸化式を展開するたびにランダム性が増してしまい、結局は制御できなくなる。 逆に、もしライトエッジが有限通りに収まったら、文献[19]の漸化式も実際には 上手くパターンに落とし込めることになると予想される。が、今のところそういう話は見てないし、 [19]を読んで漸化式を触ってみても、もう本能的に「こりゃムリだわ」っていう感想しか出てこない。 そんなわけで、ライトエッジの方針もムリに決まってるのだ。 (補足) 結局、>>512 の話でも、>>513 の話でも、 コラッツの変換を深く深く弄れば弄るほど、 ランダム性が増していく感触が確かな手ごたえとして観測される。 どこまでいっても、パターンに収まってくれる気配が全く出てこない。 「本質的にランダムになりたがっている」としか思えないのだ。 また、コラッツ予想の難しさはまさにこの部分にあるはずだ。 >>488 にも書いたが、コラッツ予想に取り組むなら、 「ランダムになりたがってる」という感触を どうやって解析したらいいかを真正面から考えるしかないだろう。 そして、そのこと自体が既に難しく、だからこその未解決問題なのだろう。 コラッツ予想で毎回思うんだけど プログラムでいうif文を扱える数学って存在すんのかなあ ifを扱える数学というか、プログラムの停止問題は解けないでそ。 Coqでコラッツの予想を厳密に定義するとどんな感じになるの? 有限回繰り返したときってCoqでどうやって表現すりゃいいんだ? >>518-519 Coqでは止まらない再帰関数は書けないので、 >>373 では、再帰を有限回で0終了させる引数yを入れてあります。 で、どんなxに対してもlast collatz03が0にならないyが存在する、という事で、 Require Import List.して Theorem collatz_is_true: forall (x:nat), x<>0 -> (exists y:nat, 1=(last (collatz03 x y) 0)). ってとこじゃないでしょうか。 うーんyで適用回数制限してんの? 止まらない再帰かけないってのも不便だな。 本質的には問題に成らんのかな Coqの仕様なんでなんとも…… >>520 でコラッツの定義としては問題ないと思います。 http://koubeichizoku.ix-web.tk/collatz/ 修正いたしました。当板の諸兄におかれましては何卒よろしくご査収の上 ご批評賜りたく、よろしくお願い申し上げます。 まず、x0の範囲を8bit以上から15bit以上に変更します。 これで、Xsが1ステップ進むごとに約0.585プラスされます。 禁止パターンは以下です。 ・00 ・111 ・11011 ・0101010 ・11 01011 01011 01011 以下のシミュレーションをおこないます。 【シミュレーションA】 1.7ビットの初期値x0A=1111111を用意する。 2.x0Aを下位へ1ビットシフトして(末尾は捨てる)、x0Aに加える。 3.最下位ビットに1加える。(下位からの繰り上がりが常に有る事を想定) 4.n+1ビットになっていたら、最下位ビットを捨ててnビットにする。 5.2~4を繰り返す。 得られる値をxsAとする。 xsAのライトエッジパターンは17区切りで以下になりますが、 [0,#1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0] 1個左にずらして01101011010110101の繰り返しとします。 それに合わせて、X0のライトエッジパターンも0と定義して、0ステップ目から17区切りにします。 (もしX1が0なら従来通り1ステップ目から始めます。) https://drive.google.com/file/d/0B_FTpAj7C52FLWI5TWMtMi1tVms/view?usp=sharing xsAは17区切りで1が10個入ります。 17区切りで1が11個入るパターンは禁止パターンなので除外します。 17区切りで1が10個入るパターンは、全部で21個あるのですが、先のライトエッジパターンの操作により、 0始まりのもの8個だけを考えれば良いです。 A1からA8の状態遷移を考えます。どれも0につながるので、この8個で閉じています。 薄い灰色は禁止パターンになるので、遷移できない箇所です。 濃い灰色はXsに0.585を足していって脱落した所です。 これを元に樹形図を描くと、最長が A4-A2-A2-A3-A3-A1-A8-A8-A7-A7-A6-脱落 の17*12ステップですが、 A2-A2-A3-A3 と A8-A8-A7-A7は脱落するので、 A4-A2-A2-A3-A1-A8-A8-A7-A6-脱落 の17*10ステップが最長となります。 これは、170ステップ以内で、17区切りで1が9個入るパターンが現れる事を意味しています。 xsAのライトエッジパターンに手を加えます。 170ステップごとに0を挿入します。 これをおこなっても先の議論より、 Xs < xsA*2^pxs (2^pxsはXsより十分右へ離す定数)が言えます。 170ステップごとに0を挿入した事により、xsAの傾きが変わります。 挿入する前は10/17=0.58823… > log(3/2)ですが、 挿入後は100/171=0.58479… < log(3/2)です。 グラフでは、「左端を伸ばすパターン」<「コラッツパターン」<「xsA」と並んでいますが、 xsAの傾きがlog(3/2)より小さい為、順序が逆転し、矛盾します。 この矛盾を回避するには、順序が逆転する前に、コラッツ値が1になるしかありません。 書いてみて分かったんですが ちょっとダメみたいです。お騒がせしました。 状態遷移図を修正しました。 before:A1\after:A1で結果がA8になっているのは、 A1からA1に遷移させるつもりだったけど、実際に計算してみるとA8に遷移してた、ということです。 あと、A4-A2-A2の遷移はA4-A2-A3になってしまうので、 A4-A2-A3-A1-A8-A8-A7-A6-D1 の17*9ステップが最長となります。 実はもう一つ問題があるのですが、それは後で書きます。 A6-D1-A1-A8と遷移したとします。 D1の末尾は0なので、A1〜A8に繋げる事ができません。 そこで11を挿入します。(1じゃないのは0101010回避のため) 次にA1を普通にやって、A8の先頭で、コラッツパターンの右端を2つ左にずらします。 これで11と相殺されます。 このときのA8のライトエッジパターンは[-2,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1] と書いても良いかもしれません。 これで「左端を伸ばすパターン」<「コラッツパターン」<「xsA」の関係も維持されます。 2bitで計算して coqで確認 というのは どちらかというと ありそうな証明です 頑張ってください 全てのnに対して2^n-1がコラッツの予想成り立つことは示せないかな。 >>535 まじで。 >>1 の言うようにビットパターンをセルオートマトンとみなすと 無限大に発散する数というのは自己複製型みたいになるのかな? >>531 ちょっと変えます。 A6-D1-A1と遷移したとします。 D1の末尾は0なので、A1〜A8に繋げる事ができません。 そこで、適当な後方から11を借りてきます(1じゃないのは0101010回避のため)。 貸した部分まで来たら、また後方から11を借ります。 D1が現れるごとに借りる個数は増えていきますが、コラッツパターンは無限に続くという仮定の元でおこなっているので、問題ないです。 また、11を前方へ移動させているだけなので、ライトエッジパターンの総量はかわらず、 「左端を伸ばすパターン」<「コラッツパターン」<「xsA」の関係も維持されます。 まだナントカパターンでやってるのか。頭の悪い奴だな。 左端を延ばすパターンでも、ライトエッジパターンでも、 2進法で表された何らかの数の、左端と右端の数桁だか数十桁だかの 固定された桁数しか見ていない。そのような固定された桁数では、 絶対にパターンに嵌まらないイレギュラーなパターンが出てくる。 それらのパターンまで取り込むと、既存の桁数では足りず、 確認すべき桁数を拡張しなければならない。 >そこで、適当な後方から11を借りてきます(1じゃないのは0101010回避のため)。 この部分は、まさに桁数を拡張していることに対応する。 そして、この作業は終わらない。すなわち、有限個のパターンでは収まらない。 一般的に記述すると、漸化式の形で延々と続くような記述になってしまう。 その漸化式は、次の項に進むごとに、2進法で表された数の中心に向かって、 左端と右端から どんどんと桁数が侵食されていくような形式になるはず。 >D1が現れるごとに借りる個数は増えていきますが、コラッツパターンは無限に続くという仮定の元でおこなっているので、問題ないです。 この部分は、まさにこのことを示唆している。 そして、一般的に記述した漸化式を解析することは、もともとのコラッツの問題と 同程度もしくはそれ以上に難しい。よって、この方法では無理。 righ1113 ◆OPKWA8uhcY は、桁の計算をいつもいつも概算で済ませて「問題ないはず」と発言し、 そのたびに、後になって修正するのを繰り返しているが、要するに、 桁の計算は概算で済ませてはいけないのである。いい加減にコイツは気づくべきである。 概算で済ませず、厳密に計算してみろ。 有限個のパターンでは収まらず、漸化式の形で延々と続くような記述にしかならないはずだ。 そして、その漸化式は複雑すぎて手に負えず、この方針では解けないのだ。 仮に全ての奇数で成立することが証明できれば全ての整数で成り立ちますか? >>1 さんよ とりあえず目標を>>534 まで落としてみないか? これでも十分難しいぞ? Coqスレの147あんたじゃろ? あの時は目標を落としたことで前に進んだじゃろ? ちなみにCoqスレの148は俺じゃから。 まあ考えてみてくれ。 調べた所、1000000009151が241ステップと長めだったので、計算してみました。 https://drive.google.com/file/d/0B_FTpAj7C52FRXJHeFhFbGJRZUE/view?usp=sharing 状態遷移は上手くいっているみたいです。 11の貸し借りも出来ているんですけど、、貸す所と借りる所がかぶらなかったので、あまり参考になりませんでした…… 11の貸し借りでかぶるとどうなるかを見るために、 100ステップずつ11を借りる例を考えてみます。 借りる先は2乗ステップ目です。 ・100ステップ目で10000ステップ目から11を借りる ・200ステップ目で40000ステップ目から11を借りる …… ・10000ステップ目で貸した11の穴埋めと、新たな11を10^8ステップ目から借りる ・40000ステップ目で貸した11の穴埋めと、新たな11を16*10^8ステップ目から借りる …… ・10^8ステップ目で計111111を、10^16ステップ目から借りる ・16*10^8ステップ目で計111111を、16^2*10^16ステップ目から借りる …… 貸す所が010101…になっている場合もあるので、実際は倍の長さが必要ですが、 それでも、「借りる11…が次のゾーンにひっかかる」というような事は起きません。 この作業に終わりはないのですが、この作業の途中で、 傾きの影響で、左端を伸ばすパターンとxsAの順序が逆転して矛盾します。 式で書くと、 100^(2^n-1)ステップで"11"*n*2を100^(2^n)ステップから借りる時、 次のゾーンまでは少なくとも200*100^(2^n-1)空いているから、 2*n*2 < 200*100^(2^n-1)が言えて、次のゾーンにはかからない。です。 修正します。 式で書くと、 100nステップで"11"*(log(4√n)+1)*2を(100n)^2ステップから借りる時、 次のゾーンまでは少なくとも200*100(n-1)空いているから、 2*(log(4√n)+1)*2 < 200*100(n-1)が言えて、次のゾーンにはかからない。です。 再修正します。 式で書くと、 100nステップで"11"*[(log(4√n)+1)]*2を(100n)^2ステップから借りる時、 (100(n+1))^2 -(100n)^2 =(10000(n+1)^2) -10000n^2 =10000n^2 +20000n +10000 -10000n^2 次のゾーンまでは少なくとも20000n空いているから、 2*[(log(4√n)+1)]*2 < 20000nが言えて、次のゾーンにはかからない。です。 >>540 全ての偶数は、2で割る事を繰り返せば奇数にたどり着くから、 全ての奇数で成立することが証明できれば、全ての自然数で成り立ちます。 全ての整数で成り立つかどうかは分からない。 >>541 2^n-1は、2進数で表すと1111…ですね。 試しに3(11)でおこなうと、次ステップは5(101)になります。 7(111)でおこなうと、次ステップは11(1101)になります。 5と11の関係は、101を右シフトして+1しているので、5*2+1=11です。 そこで、次の命題1を考えます。 ・x以下で1にたどり着けば、2x+1以下も1にたどり着く 次に、次の命題2を考えます。 ・x以下で1にたどり着けば、4x+2以下も1にたどり着く まず、これをすべての偶数で証明します。 ・2以下の偶数で1にたどり着けば、4*2+2=10以下の偶数も1にたどり着く は真です。 ・x以下の偶数で1にたどり着けば、4*x+2以下の偶数も1にたどり着く を真としたとき、 x+2は2で割れるので、(x+2)/2 < x、 4*(x+2)+2も2で割れるので、2*(x+2)+1 < 4*x+2、よって ・x+2以下の偶数で1にたどり着けば、4*(x+2)+2以下の偶数も1にたどり着く も真で、数学的帰納法で証明されました。 次に、命題2を奇数で証明したいので、2倍した偶数を考えます。 xを例にとると、xを2倍して、 ・2x以下の偶数で1にたどり着けば、4*2x+2以下の偶数も1にたどり着く 2で割って ・x以下の数で1にたどり着けば、4*x+1以下の数も1にたどり着く 4*x+1 > 2*x+1なので、命題1 ・x以下で1にたどり着けば、2x+1以下も1にたどり着く も証明されました。 これで、5(101)->11(1101)->23(11101)->……が1にたどり着くことが証明できたので、 2^n-1も1にたどり着くことが証明できました。 >>534 さん、これどうですかね。 、、、 , , _ ,. -┬i^i、._ ィ`,、,、,、,、,.、'、 . / | | .|=ゞ=、 __l/\ v~/!| l. l l l \\{f‖ミゞ, ,ィ≪:lf^i もういい…! /ヽ. ノ「,ト、「.lヘ‐iヾ|rー~r〉〉,こlレ' / `ヽ//| ト、ヽlイ| |/|{王王王王}ト、 | レニ| lニゝ冫! l!L_, , ,ー, , , ,_」シ’、 もう… ヽ __|ーL|┴^ーヽ>'^ヾ二三シ´\\ ,ゝ,/ .}二二二二二二二二二lヽ. ヽ \ 休めっ…! l/ |ト、./´\ ||. レ'´ ̄`ヽ || ! 、\ ||. / :| || |.l l゙!.|i |ヽ) |l/ / 休めっ…! || `ヘ)U'J /-─ ,イ.| || _ /-─ / ヽ| 太郎っ…! || r‐-゙=っ`ヽ,.--r-─ ''"´ ̄`ヽ / } ||. {三二 | │ / / ||. ヾ=--一'`ーゝ _,. く ノ| 再開ではないですが、気になっている事があります。 x0から始まるコラッツ列が無限大に発散するとき、以下の式は成り立つのでしょうか。 lim[s->∞](1+1/3x_1)…(1+1/3x_s) > lim[y->∞](1+1/y)^y ≒ 2.718 自分としては、各x_sが定数な分だけ、左辺が大きいと思うのですが…… 成り立つとすると、>>504 と矛盾するのではないかという気がします。 (ε=0.1とおいて、有限積では1.1を越えないのに、無限積にすると2.718を超える) 自信がないので、ご意見お待ちしています。 各x_sが定数ってどういうこと? x_sはsが増えるにしたがって大きくなるじゃねーの? 左辺はsが増えても、それ以前の項のx_sは変わらないという意味で定数と書きました。 一方右辺はyが増えると、初項から全てのyが増加します。 よくわからんが無限和が有限になることもあるように無限積も有限になる可能性がある? 無限積も有限になる可能性があるというのは、 lim[y->∞](1+1/y)^y ≒ 2.718 からも明らかです。 問題はこれより左辺 lim[s->∞](1+1/3x_1)…(1+1/3x_s) が大きいと思われる事です。 定数だからって理由だけでは大小は決められないでしょ。 積の形だから惑わされるんじゃない? おれもあんまり自信ないが 両辺logとって和の形にすればx_sになんらかの制限がなければ 大小は論じられないという結論になりそうな気がする。 定数だから単純に 1/100 > 1/∞ だと思ったんですけどねえ。 まずΣ[n->∞] (1/2)^n = 1でしょ? この式が両辺log取った結果の式だとすれば元の式は Π[n->∞] e^((1/2)^n) = e みたいな感じになるんじゃないのかな?(微妙に自信ないが) 要するにx_sが非常に急速に大きくなるなら lim[s->∞](1+1/3x_1)…(1+1/3x_s) はそんなに大きくならない可能性も十分あると思うが。 e^(1/2)*e^(1/4)*e^(1/8)*… と (1+1/3x_1)*(1+1/3x_2)*(1+1/3x_3)*… を比べて(1+1/3x_s)の減少スピードが速ければ lim[s->∞](1+1/3x_1)…(1+1/3x_s) はeに届かないって事ですか…… あと一つだけネタがあるので、しばしお待ちください。 ループする方です。 + + ∧_∧ + (0゜・∀・) ワクワクテカテカ (0゜∪ ∪ + と__)__) + ・前準備1 例えばx_sが7,11,17,13,5,17,13,5……とループするなら、先頭2項は外して,17,13,5,17,13,5……にします。 例ではx_3=x_0になります。 ・前準備2 x_0~x_s-1がループ1周期として(x_0=x_s)、コラッツパターンXsと左端を伸ばすパターンYsのビット長は [logYs] = [log(x_0*(3/2)^s)] [logXs] = [log(x_0*(3/2)^s)+log(1+1/3x_0)…(1+1/3x_s-1)] です。このときの[logYs]と[logXs]のずれが1とすると、周期を重ねるごとに[logXs]と[logYs]の差は 2log(1+1/3x_0)…(1+1/3x_s-1)、3log(1+1/3x_0)…(1+1/3x_s-1)、……と増大するので、 ずれも際限なく増大していきます。 ・ループして、コラッツパターンXsと左端を伸ばすパターンYsのずれがずっと0の場合 []は切り上げです。 logはlog_2です。 [logXs] - [logYs] = 0 から始めて [log(x_0*(3/2)^s)+log(1+1/3x_0)…(1+1/3x_s-1)] - [log(x_0*(3/2)^s)] = 0 切り上げを外して -1 < log(1+1/3x_0)…(1+1/3x_s-1) < 1 logを外して 1/2 < (1+1/3x_0)…(1+1/3x_s-1) < 2 ループ1周期の(1+1/3x_0)…(1+1/3x_s-1)をXとおくと、X>1なので、 X*X*X*……はいずれ2を超えて、上の式と矛盾します。 ・ずれがあってループした場合 ずれは増大していくので、ずれが3になったところをsとします。 そして、Xsを3ビット下位へシフトしてずれを消します。これをXs'とおきます。 Xs'=x_0*(3/2)^s*(1+1/3x_0)…(1+1/3x_s-1)/8 です。 [logXs'] - [logYs] = 0 から始めて [log(x_0*(3/2)^s)+log(1+1/3x_0)…(1+1/3x_s-1)/8] - [log(x_0*(3/2)^s)] = 0 切り上げを外して -1 < log(1+1/3x_0)…(1+1/3x_s-1)/8 < 1 logを外して 1/2 < (1+1/3x_0)…(1+1/3x_s-1)/8 < 2 ここで、 x_0からx_s-1のうちで最小のものをx_mとおいて、 (1+1/3x_0)…(1+1/3x_s-1) < ((1+1/3x_m)^3x_m)^(s/3x_m) < (1+1/3x_m)^3x_m < e なので、 (1+1/3x_0)…(1+1/3x_s-1)/8 < e/8 ≒ 0.339 となって1/2を下回って矛盾します。 よって、4-2-1ループを除いて、ループする数はない と言えるのではないかと思うのですが、どうでしょうか。 と思ったら s > 3x_m の時はループの可能性が残りますね。 妥協策としては、 (これも証明がいるけど)ループ1周期でずれ1をs、ループ3周期でずれ3を3sとしたら、 s > x_mでループの可能性があります。 コラッツは5*2^60までは反例がないので、 ループがあるとしたら、ループ周期は5*2^60(≒500京!)より大きい が言えると思います。 ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.5 2024/06/08 Walang Kapalit ★ | Donguri System Team 5ちゃんねる