1read 100read
2013年19数学181: コラッツ予想がとけたらいいな (109)
TOP カテ一覧 スレ一覧 2ch元 削除依頼 ▼
2つの封筒問題スレ 4 (881)
自分で見つけた食べかすの様な証明を載せていくスレ (107)
(難問)eが二次方程式の解ではない事を証明せよ (239)
【自治スレ】猫対策本部 (411)
》╋|||《数学オリンピック 25》|||╋《 (284)
非ノイマン式を考えよう (101)
コラッツ予想がとけたらいいな
1 :2012/10/14 〜 最終レス :2013/09/29 525 名前:132人目の素数さん[sage] 投稿日:2012/09/03(月) 18:24:27.22 http://d.hatena.ne.jp/righ1113/ コラッツ予想について、証明を考えてみました。 ご指摘ご意見ご感想など、ぜひよろしくお願いします。
2 : , '´ _. -‐'''"二ニニ=-`ヽ、 / /:::::; -‐''" `ーノ / /:::::/ \ / /::::::/ | | | | | |:::::/ / | | | | | | | |::/ / / | | || | | ,ハ .| ,ハ| | |/ / / /| ,ハノ| /|ノレ,ニ|ル' | | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。 . | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。 | l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。 | ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて | /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。 | (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は? | / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら? | |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \ . | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \ | /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 | | |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、 | |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄| | /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_| | |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
3 : , '´ _. -‐'''"二ニニ=-`ヽ、 / /:::::; -‐''" `ーノ / /:::::/ \ / /::::::/ | | | | | |:::::/ / | | | | | | | |::/ / / | | || | | ,ハ .| ,ハ| | |/ / / /| ,ハノ| /|ノレ,ニ|ル' | | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。 . | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。 | l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。 | ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて | /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。 | (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は? | / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら? | |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \ . | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \ | /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 | | |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、 | |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄| | /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_| | |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
4 : , '´ _. -‐'''"二ニニ=-`ヽ、 / /:::::; -‐''" `ーノ / /:::::/ \ / /::::::/ | | | | | |:::::/ / | | | | | | | |::/ / / | | || | | ,ハ .| ,ハ| | |/ / / /| ,ハノ| /|ノレ,ニ|ル' | | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。 . | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。 | l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。 | ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて | /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。 | (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は? | / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら? | |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \ . | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \ | /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 | | |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、 | |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄| | /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_| | |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/
5 : 豆岡高校
6 : スレ立てありがとうございます。
7 : __ノ)-'´ ̄ ̄`ー- 、_ , '´ _. -‐'''"二ニニ=-`ヽ、 / /:::::; -‐''" `ーノ / /:::::/ \ / /::::::/ | | | | | |:::::/ / | | | | | | | |::/ / / | | || | | ,ハ .| ,ハ| | |/ / / /| ,ハノ| /|ノレ,ニ|ル' | | | / / レ',二、レ′ ,ィイ|゙/ . | \ ∠イ ,イイ| ,`-' | | l^,人| ` `-' ゝ | このスレ レス数が少ないから上げとくわね。 | ` -'\ ー' 人 でも何れけされる運命ね。 | /(l __/ ヽ、 | (:::::`‐-、__ |::::`、 ヒニニヽ、 | / `‐-、::::::::::`‐-、::::\ /,ニニ、\ | |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \ . | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \ | /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 | | |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、 | |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄| | /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_| | |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/ | /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
8 : 最初に偶数はアウト(1に収束) 4の倍数になったらアウト この辺の証明は省略 1を除く奇数3・5・7・9… の偶数番目は(3n+1)/2の中で4の倍数で省く 3・7・11… の奇数番目は(3n+1)/2を2セットの中で4の倍数なので省く 7・15・23… の奇数番目は3セットの中で4の倍数なので省く 以下その連続 数学的証明の仕方はしらね(・д・`) n=8x-1 (8x-1)+4x=(3n+1)/2 後は任せた
9 : 偶数nにおいては「奇数×2のα乗」なので奇数になる 奇数nにおいて n=2x-1(n>0)としたときxが奇数であれば(3n+1)/2をすると偶数となる n=4x-1(n>0)としたときxが奇数であれば(3n+1)/2を2回すると偶数となる n=8x-1(n>0)としたときxが奇数であれば(3n+1)/2を3回すると偶数となる ↓ n=(2y)x-1(n>0かつ奇数,y>0,x>0かつxは奇数)のときに(3n+1)/2をy回すると偶数となる nが有限であればn>y,n>xが成り立つので偶数になる nが偶数ならばn/2となりn>n/2 nが奇数ならばn=2x+1とおき (3n+1)/2=3x+2 このとき3x+2が偶数であればx=2yとおき (6y+2)/2=3y+1=(3n+1)/4 n>1なのでn>(3n+1)/4
10 : 訂正 奇数nにおいて n=(2のy乗)x-1のときに(3n+1)/2をy回すると偶数になる
11 : 自分のことで手がいっぱいだがそっとエールを送りたい
12 : こちらの過去スレも参考になるよー 【検証】コラッツの予想(1-1000) http://2chnull.info/r/math/1240289175/1-1001
13 : nが奇数→n+1を素因数分解する 上記での2の乗数をy,その他を全てかけたものをxとする n=(2^y)x-1 ← n=(2のy乗)x-1であってるか分からないけど (3n+1)/2をしたときに出る値mは m=3x(2^y-1)-1 mに対しても偶数であれば/2,奇数であれば上記 nに何ステップ入れたとしてもその数値がnに戻るにはx,yがともに1でなければならない よってn=1以外の奇数でループ不可
14 : ・・・で、いいのかな?
15 : >奇数nにおいて >n=(2のy乗)x-1のときに(3n+1)/2をy回すると偶数になる これは成り立たないよ 例:7=4*2-1、11=4*3-1だが 7,22,11,34,17,52,26,... というか、そんなに簡単に証明できたら難問になってないからw
16 : >>15 7=2^3-1では?
17 : 単なる思いつきだけど話の種にでも 自然数全体からなる集合をNとする。NからNへの、この問題の操作を表す関数をfとおく。 すなわち、nが奇数ならf(n)=3n+1、nが偶数ならf(n)=n/2と定める。 Nの部分集合Aで、f(A)⊂Aを満たすものを「コラッツ不変集合」と呼ぶことにする。 すなわち、Aのどの要素nに対してもf(n)∈Aが成り立つような集合Aのことである。 特にf(A)=Aを満たすものを「コラッツ強不変集合」と呼ぶことにする。 すなわち、コラッツ不変であり、かつ「どのn∈Aに対してもあるm∈Aが存在してf(m)=n」を満たす集合Aのことである。 例 N自身はコラッツ強不変集合 {1,2,4}はコラッツ強不変集合 {1,2,4,8,…,2^k}(k≧3)はコラッツ不変だがコラッツ強不変でない より一般に、(1,2,4以外の)ある自然数から始めて1になるまでに現れる全ての自然数の集合はコラッツ不変だが、コラッツ強不変でない 例えば{13,40,20,10,5,16,8,4,2,1} 「コラッツ予想が正しい」⇔「全てのコラッツ不変集合が{1,2,4}を含む」が成り立つ…と思う。
18 : あ、最後の命題は「空でない全てのコラッツ不変集合が…」に訂正
19 : チラ裏の続き >>17 と同じ記号で Nの任意の部分集合Aに対し、Aを含む最小のコラッツ不変集合が存在する。 A∪f(A)∪f(f(A))∪f(f(f(A)))∪… がそれである。 ・φ,Nはコラッツ不変 ・コラッツ不変集合の任意個の和集合はコラッツ不変 ・コラッツ不変集合の任意個の共通部分はコラッツ不変 が成り立つことが容易に分かる。 よって、コラッツ不変集合全体を開集合(または閉集合)としてNに位相が定まる。(どっちがいいんだろう?) コラッツ不変集合を閉集合と定義した場合、上で挙げた「Aを含む最小のコラッツ不変集合」はAの閉包に一致する。
20 : どちらの位相でもfは連続(証明略) 実例を見ると、「コラッツ不変⇔閉集合」の方がそれっぽい気がする。 wikipediaの「コラッツの問題」 http://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%A9%E3%83%83%E3%83%84%E3%81%AE%E5%95%8F%E9%A1%8C にあるような図で考えると、閉集合は下に閉じている感じで、開集合は上に延びていく感じになる。 例えばn∈Nに対し、「有限回の操作でnになる数全体」は開集合。特に、これはnを含む最小の開集合である。
21 : と、ここまで書いてみたはいいけど、結局「集合XとXからXへの写像fの組」についての一般論の域をほとんど出てない…どうしたものか。 位相の言葉による言い換えが2つほど得られたので一応書いておく。 「コラッツ予想が正しい」⇔「Nが連結」 (左⇒右)1を含む最小の開集合をAとすると、Aは「有限回の操作で1になる数全体」と一致し、予想が正しければA=Nである。 このことから、1を含む連結成分はNとなり、Nは連結。 (右⇒左)再び1を含む最小の開集合をAとすると、Aは「有限回の操作で1になる数全体」と一致し、これよりAは閉集合でもあることが分かる。 Aは開かつ閉で空でないから、連結性よりA=N 。これは、全ての自然数が有限回の操作で1になることを意味し、したがって予想は正しい。□ 「ループが有限個かつ無限に大きくなる列は無い」⇔「Nはコンパクト」 (左⇒右)任意に開被覆{U_λ}をとる。有限個のループから1つずつ数をとり、a_1,…,a_nとすると、 a_i∈U_(λ_i)(i=1,…,n)となるようにλ_iが選べて、{U_(λ_i)|i=1,…,n}が有限部分被覆となる。 (右⇒左)ちょっと長くなるので概略で。 対偶を示す。 無限に大きくなる列があればそれをa_1,a_2,…とする。 ループが無限個あれば各ループから一つずつ数をとり、a_1,a_2,…とする。(選択公理?) どちらの場合も、a_iを含む最小の開集合をU_iとおくと、{U_i}を用いて有限部分被覆を持たない開被覆を構成できる。
22 : 調べたらさらに古いスレが コラッツ予想 http://logsoku.com/thread/science2.2ch.net/math/1072595845/
23 : 2進整数環 Z_2 の部分集合 S を以下の規則で構成する。 α = 3^(-1) ( ∈ Z_2 ) とする。 1) 1 ∈ S 2) n ∈ S ⇒ 4n - 1 ∈ S 3) n ∈ S ⇒ α(4n - 1) ∈ S 4) n ∈ S ⇒ 2αn ∈ S 5) 以上の規則で生成される数のみが S の要素である。 コラッツ予想は、S が自然数全体 N を含むことと同値。 --------------------------------------------------------- で、何がいえるかというと・・・いや、それは
24 : Z_2に拡張できるってのは俺も考えたことがあるな。 で、拡張について考えてみたら以下のことが分かった。 以下、Z_2に拡張したとして議論するが、他になんらかの拡張があったとしても(多分)同様。 Qを有理数体とする。 @Z_2∩Qの元から始めて操作するとZ_2∩Qの元しか現れず、Z_2\Qの元から始めて操作するとZ_2\Qの元しか現れない。 囁O半は自明。後半は背理法。 x∈Qが現れたとすると、その一つ前は2xか(x-1)/3なので、一つ前も有理数。 繰り返すと、結局最初の数が有理数ということになり矛盾。□ AZ_2\Qではループは存在しない。 啾∈Z_2から何回か操作してaに戻るとする。このとき、aはある方程式g(x)=xの解になる。 ここでg(x)は、xに「3倍して1を足す」「2で割る」を何回か繰り返して得られる多項式であり、したがって有理数係数の1次式である。 よって、g(x)=xの解は有理数。□
25 : Aの所改行し忘れた… そんなわけで、有理数より大きく広げる必要は無いんじゃないかなーとか思ったり。
26 : __ノ)-'´ ̄ ̄`ー- 、_ , '´ _. -‐'''"二ニニ=-`ヽ、 / /:::::; -‐''" `ーノ / /:::::/ \ / /::::::/ | | | | | |:::::/ / | | | | | | | |::/ / / | | || | | ,ハ .| ,ハ| | |/ / / /| ,ハノ| /|ノレ,ニ|ル' | | | / / レ',二、レ′ ,ィイ|゙/ 私は只の数ヲタなんかとは付き合わないわ。 . | \ ∠イ ,イイ| ,`-' | 頭が良くて数学が出来てかっこいい人。それが必要条件よ。 | l^,人| ` `-' ゝ | さらに Ann.of Math に論文書けば十分条件にもなるわよ。 | ` -'\ ー' 人 一番嫌いなのは論文数を増やすためにくだらない論文を書いて | /(l __/ ヽ、 良い論文の出版を遅らせるお馬鹿な人。 | (:::::`‐-、__ |::::`、 ヒニニヽ、 あなたの論文が Ann of Math に accept される確率は? | / `‐-、::::::::::`‐-、::::\ /,ニニ、\ それとも最近は Inv. Math. の方が上かしら? | |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \ . | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \ | /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 | | |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、 | |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄| | /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_| | |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/ | /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
27 : 分母が5の既約分数で調べてみたら、いくつかループがあった。それぞれ 1/5 19/5 23/5 187/5 347/5 を含むもの(これらはそのループ中で最小の数)。まだ小さい初期値でしか調べてないから、もっとあるかも。 下2つは、両方とも「*3+1」を17回、「/2」を27回で計44回の操作でループする。なんかありそう。 負の数でも調べてみたら、少なくとも-1/5から-299/5までは、全て-1/5を経由して1/5のループに到達した。 なんか普通の自然数と雰囲気似てる気がする。
28 : >>27 整数で考えると3n+5になるのか それから187はループじゃないっぽい もっと大きい数でもやってみたら 大体1か19か187のループに入る 低確率で347(例:443)、23はほとんどない
29 : 阿呆の書き込みは軽蔑に値するだけ。 狢 >389 名前:粋蕎 ◆C2UdlLHDRI :2012/11/23(金) 20:18:33.20 > 低脳撲滅主義の下では現低脳が絶える時に低脳上限上昇による新低脳が生まれる故の無限淘汰地獄。 > 低脳撲滅主義に於いて低脳認定基準を設けても時代と共に基準は改正されるので無駄な事である。 > つまり猫改め描改め狢は学力的弱肉強食主義である。行き過ぎた撲滅主義は文化衰退を招く。 >
30 : http://uploda.cc/img/img50b15832de2ac.bmp 26までの数からの変化をまとめてみた
31 : 狢 >454 名前:粋蕎 ◆C2UdlLHDRI :2012/11/24(土) 19:51:25.34 > あーあ、独逸みたいな三大政党化を期待しとったが期待外れじゃな。 > 一大政党では独裁を生み > 二大政党では思考不足の極論選択を生み > 三大政党で初めて民衆は思考勘案し吟味選択する。 > じゃが此の分じゃ単に民衆は釣られる対象にしかならんな、あれじゃ野合と言われても仕方ない。 >
32 : >>30 まだまだだな http://uploda.cc/img/img50b1fb425dba0.jpg はみ出てるけど奇数のみ399まで
33 : 私は某女子短大で教えているが、女子学生はキャンパス内では全員例外なく全裸になり、 学生証を安全ピンで乳首に刺して止めておくべきだ。 やらなければこちらがブスッと刺す。血が出るかも。 生理の時は私がタンポンを入れたり抜いたりしてやる。血が付くかも。 云う事聞かない奴は逆さ吊りだ。トイレに行きたくなっても行かせない。 クリスマスは私と女子学生の乱交パーティーだ 。勿論女子学生同士の愛も OK. 女子学生は皆食べ頃だ。参加しない奴には単位を出さない。 等と云った妄想を毎日朝から晩までしている。 授業中もチンコが立ちっぱなしで困る。
34 : ペアノの公理系で解けるのかな なんか此の手の数列の問題で超越的手法じゃないと証明できないやつあったよね
35 : ABC予想を解くのに使われた「遠アーベル幾何」というものの話を最近聞いたんだが、なんかコラッツ予想にも使えそうな感じがした。 体における和と積の複雑さに対して効力を発揮するとかなんとか。 難しすぎてまだまだ俺の手には負えそうにないが。
36 : >>35 そのアイデアいただき〜ッ!
37 : ε⌒ ヘ⌒ヽフ ( ( ・ω・) ブーブーお前解けないのかコラーッ しー し─J
38 : __ノ)-'´ ̄ ̄`ー- 、_ , '´ _. -‐'''"二ニニ=-`ヽ、 / /:::::; -‐''" `ーノ / /:::::/ \ / /::::::/ | | | | | |:::::/ / | | | | | | | |::/ / / | | || | | ,ハ .| ,ハ| | |/ / / /| ,ハノ| /|ノレ,ニ|ル' | | | / / レ',二、レ′ ,ィイ|゙/ . | \ ∠イ ,イイ| ,`-' | | l^,人| ` `-' ゝ | このスレには馬と鹿と豚さんしかいないのね。 | ` -'\ ー' 人 | /(l __/ ヽ、 | (:::::`‐-、__ |::::`、 ヒニニヽ、 | / `‐-、::::::::::`‐-、::::\ /,ニニ、\ | |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \ . | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \ | /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 | | |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、 | |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄| | /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_| | |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/ | /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
39 : __ノ)-'´ ̄ ̄`ー- 、_ , '´ _. -‐'''"二ニニ=-`ヽ、 / /:::::; -‐''" `ーノ / /:::::/ \ / /::::::/ | | | | | |:::::/ / | | | | | | | |::/ / / | | || | | ,ハ .| ,ハ| | |/ / / /| ,ハノ| /|ノレ,ニ|ル' | | | / / レ',二、レ′ ,ィイ|゙/ . | \ ∠イ ,イイ| ,`-' | | l^,人| ` `-' ゝ | このスレには馬と鹿と豚さんばかりね。 | ` -'\ ー' 人 | /(l __/ ヽ、 | (:::::`‐-、__ |::::`、 ヒニニヽ、 | / `‐-、::::::::::`‐-、::::\ /,ニニ、\ | |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \ . | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \ | /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 | | |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、 | |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄| | /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_| | |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/ | /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
40 : コラッツ予想を2進数で考えたいと思います。 初期値7->22->11->34->17->52->26->13 ->40->20->10->5->16->8->4->2->1 を例にとって、奇数のみを並べると以下のようなパターンができます。 これを「コラッツ・パターン」と名付けましょう。 1次元のセルオートマトンとも見なせます。 (普通の2進数とは上位下位を逆に、下位ビットを左にしています。) 111 7 1101 11 10001 17 01011 13 000101 5 0000001 1 セルオートマトンと見なした時は以下のルールで下へ伸びていきます。 (1)「1」の塊は、次ステップで両端が離れる 「11」は「1001」に、「111」は「10101」になります。 (2)単独の「1」は、次ステップで「11」になる (3)「11011」のような、次ステップで左「1」と右「1」が 重なる場合は、右(上位)へ繰り上がる 「11011」は次ステップで「1000101」になります。 (4)最後に、左端に+1する
41 : 次に、ルール(4)を削除したパターンを考えてみます。 左端がえんえんと左へ伸びていきます。 00000111 000010101 000111111 0010111101 01110110001 10100101011 さらに、元のパターンとの差をとります。 00000___ 00001 000101 0011001 01001001 110110101 「左端を伸ばすパターン」+「差のパターン」=「元のコラッツパターン」 「差のパターン」<「元のコラッツパターン」───(イ) となります。
42 : ここで、各パターンの右端に注目してみます。 「元のパターン」の右端は、ある傾きの直線をとります。 一方、「差のパターン」の右端は、それより大きい傾きで進行します。 二つの傾きを重ねると、あるところで交差・逆転します。 すると、大小関係が逆転するので(イ)式と矛盾します。 これを回避するには、二つの傾きが交差する前に、コラッツ操作が1に収束するしかありません。 こうなるイメージです。 o x o x o x o x o x ox くわしくは、 http://d.hatena.ne.jp/righ1113/ (4)コラッツ・パターン からをご覧ください。
43 : あげてみる http://cdn-ak.f.st-hatena.com/images/fotolife/r/righ1113/20120606/20120606043249.jpg
44 : __ノ)-'´ ̄ ̄`ー- 、_ , '´ _. -‐'''"二ニニ=-`ヽ、 / /:::::; -‐''" `ーノ / /:::::/ \ / /::::::/ | | | | | |:::::/ / | | | | | | | |::/ / / | | || | | ,ハ .| ,ハ| | |/ / / /| ,ハノ| /|ノレ,ニ|ル' | | | / / レ',二、レ′ ,ィイ|゙/ . | \ ∠イ ,イイ| ,`-' | | l^,人| ` `-' ゝ | このスレは馬と鹿と豚さんばかりね。 | ` -'\ ー' 人 | /(l __/ ヽ、 | (:::::`‐-、__ |::::`、 ヒニニヽ、 | / `‐-、::::::::::`‐-、::::\ /,ニニ、\ | |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \ . | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \ | /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 | | |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、 | |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄| | /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_| | |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/ | /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
45 : >>40-43 仮に1を初期値とするコラッツ・パターンを作るとしたら、 1 01 001 0001 00001 ということであってる? これは明らかに傾き1。 これを見るに、「元のコラッツ・パターン」の傾きが必ずしもlog[2](3/2)になるとは限らないんじゃないかと。 「+1」の影響が意外と大きい。
46 : >>45 初期値1のコラッツ・パターンはそれで合っています。 これで良いのです。 「元のパターン」の右端は、『コラッツ操作が1に収束するまでは』傾きlog[2](3/2)の直線をとります。 でした。言葉足らずでした。 そしてこれが背理法の要です。 >>42 の > 二つの傾きを重ねると、あるところで交差・逆転します。 > すると、大小関係が逆転するので(イ)式と矛盾します。 > これを回避するには、二つの傾きが交差する前に、コラッツ操作が1に収束するしかありません。 は1行追加して、 二つの傾きを重ねると、あるところで交差・逆転します。 すると、大小関係が逆転するので(イ)式と矛盾します。 これを回避するには、二つの傾きが交差する前に、コラッツ操作が1に収束して、 『「元のパターン」の右端傾きが1になるしかありません。』 です。
47 : こうなると大小関係が逆転して矛盾するから、 o x o x o x o x o x ox xo こうなるしかありません。 o x o x o x o x o xここで1に収束 o x o x o x
48 : __ノ)-'´ ̄ ̄`ー- 、_ , '´ _. -‐'''"二ニニ=-`ヽ、 / /:::::; -‐''" `ーノ / /:::::/ \ / /::::::/ | | | | | |:::::/ / | | | | | | | |::/ / / | | || | | ,ハ .| ,ハ| | |/ / / /| ,ハノ| /|ノレ,ニ|ル' | | | / / レ',二、レ′ ,ィイ|゙/ . | \ ∠イ ,イイ| ,`-' | | l^,人| ` `-' ゝ | このスレは馬と鹿と豚さんばかりね。 | ` -'\ ー' 人 | /(l __/ ヽ、 | (:::::`‐-、__ |::::`、 ヒニニヽ、 | / `‐-、::::::::::`‐-、::::\ /,ニニ、\ | |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \ . | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \ | /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 | | |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、 | |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄| | /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_| | |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/ | /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
49 : 1だけが特別ってのも変だと思う。 他の数でも+1が上手く作用して、部分的に傾きが大きくなることもある。 27なんかはそれが多く起こって長く続くんだろう。
50 : うーん変ですか…… 1だけが特別というのは 1だけが4-2-1ループする唯一の奇数という コラッツ予想の特徴をよく表していると思うのですが……
51 : あ
52 : 傾きの大小だけで交わるかどうかを判断することはできない。 例えば、y=(x-1)/xはx>0の範囲で増加するが、xをどれだけ大きくしても1を超えることはない。 実際、「差のパターン」の差分を計算してみると、確かにlog[2](3/2)より大きくはなるがlog[2](3/2)に収束しそうな感じがした。
53 : がーん そんなあ。 確かにy=(x-1)/xの傾き1/x^2は、y=1の傾き0よりも大きいけど、 二つのグラフは交わりませんね。 ということは 「差のパターン」は「元のコラッツパターン」に漸近するんですかね?
54 : だんだん平行になっていく、ぐらいじゃないかなあ 直感的には「差のパターン」は「元のコラッツパターン」よりずいぶん小さい気がする
55 : 数学板でちゃんとした投稿が大半を占めている貴重なスレなので お礼にこのスレに関連する情報を1つ書いておくね。知ってたらゴメン。 コラッツ予想に関して、最近までの主要な結果(一般化も含め)や昔の論文の復刻を纏めた次の本が 2年ちょい前にアメリカ数学会(American Mathematical Society)から出版された。 Jeffery C. Lagarias "The Untimate Challenge: The 3x+1 Problem", ISBN: 978-0-8218-4940-8 AMSの会員ならAMSのホムペから少し安く買えるけど、会員以外でもアメリカのAmazonとかで買えるはず。 CoxeterやConwayやRichard Guyら錚々たる連中の昔の論文もリプリントされていて読めるので コラッツ大好きな人はこの本を持ってるとちょっとハッピーだと思う。
56 : >>54 うわああああああああ >>55 情報ありがとうございます! さっそく見てみます!
57 : 有理数への拡張を詳しく考えてみた 分母が奇数のものだけを考え、分子が奇数なら「3倍して1足して2で割る」、分子が偶数なら「2で割る」という操作をする。 例えば1/5から始めると、 1/5→4/5→2/5→1/5→… とループする。 ここで、分子に奇数が現れたら○、偶数が現れたら×と書くことにすると、上記のループは「○××」が繰り返してることになる。 そこで、逆に「○××」で元に戻る数が他にあるかを考える。 初期値をxとすると、 x→(3x+1)/2→(3x+1)/4→(3x+1)/8 と変化するはずだから、方程式 (3x+1)/8=x が得られ、これを解くと解はx=1/5のみ。 よって、「○××」が繰り返されるループは1/5を初期値とするもののみであることがわかる。 同様にして、○×からなる有限列を一つ指定すれば、それに応じて有理数が一つ定まる。 得られた有理数が実際に指定してループを辿るかは非自明だが、おそらく辿る。
58 : 「×○×」や「××○」を指定しても、初期値が変わるだけで「○××」と同じループが得られる。 そこで、これは「○××」が円形に並んでいるものと考えられる。 この考えから、次のことがわかる。 定理 n個の奇数とm個の偶数からなるループの個数は、n個の○とm個の×からなる円順列の個数に等しい。 例 奇数2個、偶数4個からなるループを考える。 ○2個、×4個からなる円順列は、 ○× ○× ○× ○× ×× ×× ×× ○× ×○ (半時計周りに並んでいるとする) の3通り。左上の○に対応する数は、それぞれ1/11,7/55,1/5となる。 これらは、実際に指定した偶奇を辿ってループすることが確かめられる。 奇数n個、偶数m個からなるループについて方程式を作ると、 (3^n*x+a)/2^(n+m)=x (aは正の整数) という形になる。これを解くと、 x=a/(2^(n+m)-3^n) となる。したがって、ループを構成する数は、分母が2^(n+m)-3^n(の約数)であるような分数として書ける。 とりあえずここまで
59 : http://cdn-ak.f.st-hatena.com/images/fotolife/r/righ1113/20130214/20130214184540.jpg 7から始まるコラッツ数列を強制的にループさせてみると、 3周目で「左端を伸ばすパターン」と「差のパターン」が交差した。 ここから何か言えないだろうか。
60 : __ノ)-'´ ̄ ̄`ー- 、_ , '´ _. -‐'''"二ニニ=-`ヽ、 / /:::::; -‐''" `ーノ / /:::::/ \ / /::::::/ | | | | | |:::::/ / | | | | | | | |::/ / / | | || | | ,ハ .| ,ハ| | |/ / / /| ,ハノ| /|ノレ,ニ|ル' | | | / / レ',二、レ′ ,ィイ|゙/ . | \ ∠イ ,イイ| ,`-' | | l^,人| ` `-' ゝ | このスレには馬と鹿と豚さんしかいないのね。 | ` -'\ ー' 人 | /(l __/ ヽ、 | (:::::`‐-、__ |::::`、 ヒニニヽ、 | / `‐-、::::::::::`‐-、::::\ /,ニニ、\ | |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \ . | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \ | /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 | | |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、 | |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄| | /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_| | |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/ | /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
61 : http://science2.2ch.net/test/read.cgi/math/1072595845/ http://science6.2ch.net/test/read.cgi/math/1240289175/
62 : コラッツ操作を式であらわすと 初期値をx、ステップ数をn、nステップ後の奇数をx_nとして x(3/2)^n + 3^(n-1)/2^n + p_1*3^(n-2)/2^n-1 +...+ p_1*p_2*...p_(n-2)*3^1/2^2 + p_1*p_2*...p_(n-1)/2 = p_1*p_2*...p_n*x_n となる。 左辺第一項x(3/2)^nが「左端を伸ばすパターン」、 左辺残りが「差のパターン」、 右辺p_1*p_2*...p_n*x_nが「元のコラッツパターン」に対応している。 p_nはコラッツ操作で偶数が2回以上続いた時の2のべき。 「差のパターン」のp_nの積の部分は例えば 1,1,2,2,2,4,4,8,8,8,8,16... のように増加していく。 ここから先に進まない……
63 : 「差のパターン」3^(n-1)/2^n + p_1*3^(n-2)/2^n-1 +...+ p_1*p_2*...p_(n-2)*3^1/2^2 + p_1*p_2*...p_(n-1)/2 をf(n)とおく。 「差のパターン」の右端グラフは2進数目盛上にあるので log{f(n)}になる。底は2。 これの2階差分u_(n+1) - 2u_n + u_(n-1)を取ると、 log{f(n+1)} - 2log{f(n)} + log{f(n-1)} = log{ f(n+1)*f(n-1) / f(n)^2 } f<0だから、この式は正。 2階差分が正だから、「差のパターン」の右端グラフは下(左)に凸。 この結果と先にあげた 「左端を伸ばすパターン」右端傾きより「差のパターン」右端傾きが大きい を合わせて 二つの右端グラフが交差する、と言えるのではないだろうか。
64 : × f<0 ○ f>0
65 : あ、やべ。 logの中が1より小さかったらlogは負になるんだ。 考え直します。
66 : log{ f(n+1)*f(n-1) / f(n)^2 }の中が1より大きいか考える。 n=5でf(n)が5項ある場合を考える。nが増えても同様。 (a+b+c+d+e+f)*(a+b+c+d) / (a+b+c+d+e)^2 a+b+c+d+e=Aと置くと (A+f)*(A-e) / A^2 = {A^2+A(f-e)-fe} / A^2 e = (1/2)*p_1*p_2*...p_(n-1) f = (1/2)*p_1*p_2*...p_(n-1)*p_n なので、p_n=1の場合、分子がA^2-feとなって 分数式 < 1。 p_n=2の場合、f=2eだから分子がA^2+Ae-fe、A>fだから 分数式 > 1。 p_n=4,8,16,...も同様に 分数式 > 1。 よってlog{ f(n+1)*f(n-1) / f(n)^2 }は p_n=1の場合、負。 p_n=2以上の場合、正。 「差のパターン」の右端グラフは 偶数が1回しかない時、上に凸で、偶数が2回以上の時、下に凸という、 なにも進展しない結果になった。 コラッツ操作で、偶数が2回以上続くほうが多い、とか言えないかなあ。。。
67 : ネットを見てると、よく 「4x+1となる数については調べなくてよい」 とありますが、これは数学的帰納法の一部分であって、 「4x+1はコラッツ操作で1に収束する」が証明された訳ではないですよね。 何故こんな事を聞くかというと、4x+3もコラッツ操作で4x'+1に接続されるので、 予想が解けちゃうなー、と思ったので。
68 : 科学技術フェスタで、奇数の時3n+1にする代わりに3n-1にすると、ループが3種類できて その3種類の頻度はほぼ同じになるっぽい(証明はできてない)、という発表を高校生がやっとった。
69 : い
70 : 全ての数がコラッツ操作で小さくなれば、 コラッツ予想は証明されます。 値が2xの場合は2で割って小さくなります。 同様に値が4x+1や16x+3でもコラッツ操作を続けると小さくなります。 これを全ての数で言えないかを今考えています。
71 : こんな数学的帰納法を考えています。 ・x = 1で成り立つ ・x < kで成り立つと仮定したとき、 x = kでも成り立つ 値が4x+1や16x+3の場合はコラッツ操作をおこなうと小さくなるので、 上記の方法が使えます。 すぐ小さくならない値k1については、 ・x=k1とそれに連結される数を除くx<k2で成り立つと仮定したとき、 x=k2でも成り立つ するとk1はk2に連結するのでx=k1でも成り立つ という方法が考えられます。 図にするとこんな感じです。 k2 /\ / k3 k1 k2>k3となるk2は、全ての数が4x+1を通過することから すぐ見つけられます。 あとはk1とk3がつながってループする事がなければ良いわけです。
72 : あと、すぐ小さくならない値が複数個連結される可能性もあります。 図にするとこんな感じです。 /\ /\.../ ↓ /\.../ | / | ↑................................................┘最後はループする
73 : 式であらわします。 すぐ小さくならないk1がすぐ小さくならないk2に連結されるとします。 k1の側は、例えばk1=27+2^5*xとおくと、2ステップ後にちょびっと小さくなるので、その値は ((3*k1+1)/2*3+1)/4 = (9*k1+5)/8 = 31 +3^2*2^2*x1 −−−@ となります。 k2の側は、k2から後ろ向きにnステップ伸びるとして、 コラッツ逆操作「2のべき乗をかけて1引いて3で割る」をおこないます。 n=1の場合は (k2*2^p1 -1)/3 n=2の場合は ((k2*2^p1 -1)/3*2^p2 -1)/3 = k2*2^(p1+p2)/3^2 -2^p2/3^2 -1/3 一般化して (1/3^n)( k2*2^(p1~pn) -2^(p2~pn) -3*2^(p3~pn) -...-3^(n-2)*2^pn -3^(n-1) ) −−−A となります。( p1+p2+...+pn を p1~pn と略記) 連結されるので、@とAをイコールで結びます。 3^n*( 31 +3^2*2^2*x1 ) = k2*2^(p1~pn) -2^(p2~pn) -3*2^(p3~pn) -...-3^(n-2)*2^pn -3^(n-1)
74 : n=1の場合は 2*47 +3^3*2^2*x1 = k2*2^p1 => p1=1となって 47 +3^3*2*x1 = k2 n=2の場合は 3*(2*47 +3^3*2^2*x1) = k2*2^(p1+p2) -2^p2 => p2=1 2*71 +3^4*2*x1 = k2*2^p1 => p1=1となって 71 +3^4*x1 = k2 第一項は31から始まるコラッツ数列になること、 pnはそのときの2で割る回数になるところがポイントです。 一般化すると、以下になります。 CO31 は31から始まるコラッツ数列です。 CO31 +3^(n+2)*x1/2^(p1~p(n-2)) = k2
75 : k2を固定します。ここではk2=71+2^7*x2とおいてみます。 CO31 +3^(n+2)*x1/2^(p1~p(n-2)) = 71+2^7*x2 2^(p1~p(n-2))*(CO31 -71) = 2^(7+p1~p(n-2))*x2 -3^(n+2)*x1 この式の形 c = 2^a * x1 - 3^b * x2 を考えることによって 何か言えるのではと思うわけです。
76 : >>74 の後半は間違っていました。 第一項が分数になることもあります。 コラッツ数列ぽいことはぽいのですが......
77 : ここでちょっと内容を変えて、 コラッツ操作ですぐ小さくなる値とそうでない値をまとめます。 すぐ小さくなる値を「良い値」、そうでない値を「悪い値」と呼びましょう。 全ての数を2進数の下位ビットで場合分けして、良い/悪いを調べます。 (2進数は左が下位) 2進数 良い/悪い どう小さくなるか 0… 良い 2x → x 10… 良い 4x+1 → 3x+1 1100… 良い 16x+3 → 3^2x+2 1101… 11010… 良い 32x+11 → 3^3x+10 11011… ★悪い 27+2^5x
78 : 1110… 11101… 良い 32x+23 → 3^3x+20 11100… 111000… 1110000… 良い 2^7x+7 → 3^4x+5 1110001… ★悪い 71+2^7x 111001… 1110010… 11100101… ★悪い 167+2^8x 11100100… 良い 2^8x+39 → 3^5x+38 1110011… ★悪い 103+2^7x 1111… 11110… 111101… ★悪い 47+2^6x 111100… 1111000… 良い 2^7x+15 → 3^4x+10 1111001… 11110010… 良い 2^8x+79 → 3^5x+76 11110011… ★悪い 207+2^8x 11111… ★悪い 31+2^5x
79 : 「11011…」「1110001…」「11100101…」「1110011…」 「111101…」「11110011…」「11111…」が悪い値ですが、 「1110001…」と「11100101…」は、次ステップで「11011…」になるので 考えなくて良いです。 よって、「11011…」「1110011…」 「111101…」「11110011…」「11111…」 の五つの場合を考えれば良い事になります。
80 : う
81 : 一つ定理が出来たので書きます。 コラッツ操作でxがsステップで小さくなれば、 3^s < 2^lを満たすx+2^l*yもsステップで小さくなる。 コラッツ操作で奇数→奇数までを1ステップと数えます。 証明は、まず、xがsステップで小さくなれば、その時の2で割った合計をl0と置くとき、 3^s < 2^l0が成り立つ事を言います。―――@ sステップ後の数は、それぞれのステップで2で割った回数をpnとすると、 (3^s/2^(p1~ps))*x + 3^(s-1)/2^(p1~ps) + 3^(s-2)/2^(p2~ps) + ... + 1/2^ps < x (3^s/2^(p1~ps))*x < x 3^s < 2^(p1~ps) = 2^l0 よって@は成り立つ。
82 : 次に、3^s < 2^lを条件(A)としたx+2^l*yもsステップで小さくなる事を証明する。 @とAを重ねると次の三つの場合がある。 2^l0 < 2^l, 2^l0 = 2^l, 2^l0 > 2^l 2^l0 < 2^lの場合、xのsステップ後をx1とおいて、x+2^l*y―(sステップ後)→x1+3^s*2^(l-l0)y x > x1, 2^(l-(l-l0))*y > 3^s*yだから、x+2^l*y > x1+3^s*2^(l-l0)yが成り立つ。 2^l0 = 2^lの場合、x+2^l*y―(sステップ後)→x1+3^s*y x > x1, 2^l*y > 3^s*yだから、x+2^l*y > x1+3^s*yが成り立つ。 2^l0 > 2^lの場合、x+2^l*y―(sステップ後)→2^(l0-l)*x1+3^s*y 2^l*y > 3^s*y。x > 2^(l0-l)*x1を言いたいので、次の補題を考える。 3^s < 2^l が成り立てば、xはsステップ後、計l回2で割った時点で小さくなる。―――B
83 : Bを証明する。コラッツパターンを使う。 http://cdn-ak.f.st-hatena.com/images/fotolife/r/righ1113/20130603/20130603020241.jpg コラッツパターンより、 log[2]x > log[2]x -(l0-s) + s*log[2](3/2)―――C log[2]x > log[2]x+1 -(l0-s) + s*log[2](3/2)―――D が言えればよい。 3^s < 2^l0 -> s*log3 < l0*log2 -> log[2]3 < l0/s とlog[2]3 -1 = log[2](3/2)から、 l0/s -1 > log[2](3/2) -> l0-s > s*log[2](3/2) log[2]x > log[2]x -(l0-s) + s*log[2](3/2) Cが言えた。 Cが言えたから条件3^s < 2^lより、log[2]x > log[2]x -(l-s) + s*log[2](3/2)が言える。 これとl0-1 ≧ lより、log[2]x > log[2]x+1 -(l0-s) + s*log[2](3/2) Dが言えた。 CDが証明できたので、Bも成り立ち、 2^l0 > 2^lの場合も x+2^l*y > 2^(l0-l)*x1+3^s*yが成り立つ。 以上です。
84 : __ノ)-'´ ̄ ̄`ー- 、_ , '´ _. -‐'''"二ニニ=-`ヽ、 / /:::::; -‐''" `ーノ / /:::::/ \ / /::::::/ | | | | | |:::::/ / | | | | | | | |::/ / / | | || | | ,ハ .| ,ハ| | |/ / / /| ,ハノ| /|ノレ,ニ|ル' | | | / / レ',二、レ′ ,ィイ|゙/ . | \ ∠イ ,イイ| ,`-' | | l^,人| ` `-' ゝ | このスレは馬と鹿と豚さんばかりね。 | ` -'\ ー' 人 | /(l __/ ヽ、 | (:::::`‐-、__ |::::`、 ヒニニヽ、 | / `‐-、::::::::::`‐-、::::\ /,ニニ、\ | |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \ . | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \ | /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 | | |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、 | |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄| | /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_| | |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/ | /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
85 : __ノ)-'´ ̄ ̄`ー- 、_ , '´ _. -‐'''"二ニニ=-`ヽ、 / /:::::; -‐''" `ーノ / /:::::/ \ / /::::::/ | | | | | |:::::/ / | | | | | | | |::/ / / | | || | | ,ハ .| ,ハ| | |/ / / /| ,ハノ| /|ノレ,ニ|ル' | | | / / レ',二、レ′ ,ィイ|゙/ . | \ ∠イ ,イイ| ,`-' | | l^,人| ` `-' ゝ | このスレは馬と鹿と豚さんばかりね。 | ` -'\ ー' 人 | /(l __/ ヽ、 | (:::::`‐-、__ |::::`、 ヒニニヽ、 | / `‐-、::::::::::`‐-、::::\ /,ニニ、\ | |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \ . | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \ | /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 | | |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、 | |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄| | /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_| | |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/ | /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/
86 : Bの証明に不備があったので修正します、Bを少し弱めます。 3^s < 2^l < 2^l0が成り立てば、xはsステップ後、 計l回2で割った時点で同じか小さくなる。―――E これを証明します。 logの底は2です。 sステップ後のコラッツ値をxsとおいて対数を取ると 以下が成り立ちます。 log(xs) = log(x) -(l-s) +s*log(3/2) +log(1+1/3x)…(1+1/3x_s-1) >>83 より log(x) > log(x) -(l-s) + s*log(3/2)―――C log(x) > log(x)+1 -(l-s) + s*log(3/2)―――D が成り立ちます。切り上げて [log(x)] ≧ [log(x) -(l-s) + s*log(3/2)]―――F [log(x)] ≧ [log(x)+1 -(l-s) + s*log(3/2)]―――G コラッツパターンより [log(x) -(l-s) + s*log(3/2)] = [log(x) -(l-s) +s*log(3/2) +log(1+1/3x)…(1+1/3x_s-1)] [log(x) -(l-s) + s*log(3/2)] +1 = [log(x) -(l-s) +s*log(3/2) +log(1+1/3x)…(1+1/3x_s-1)] FGに代入 [log(x)] ≧ [log(x) -(l-s) +s*log(3/2) +log(1+1/3x)…(1+1/3x_s-1)] 切り上げを外して log(x) ≧ log(x) -(l-s) +s*log(3/2) +log(1+1/3x)…(1+1/3x_s-1) 以上でEが証明できました。
87 : 話題がコロコロ変わってすみません。おさらいです。 コラッツ予想を2進数で考えます。 コラッツ数列の奇数のみを並べると以下のようなパターンができます。 これをコラッツパターンと名付けます。 (下位ビットが左) 111 7 1101 11 10001 17 01011 13 000101 5 0000001 1 コラッツパターンは以下のルールで下へ伸びていきます。 (1)「1」の塊は、次ステップで両端が離れる 「11」は「1001」に、「111」は「10101」になります。 (2)単独の「1」は、次ステップで「11」になる (3)「11011」のような、次ステップで左「1」と右「1」が 重なる場合は、右(上位)へ繰り上がる 「11011」は次ステップで「1000101」になります。 (4)最後に、左端に+1する sステップ後値の初期値0位置からの距離をLnとおきましょう。 例の5ステップ目はLn=7となります。
88 : 次に、ルール(4)を削除したパターンを考えてみます。 左端がえんえんと左へ伸びていきます。 00000111 000010101 000111111 0010111101 01110110001 10100101011 左端を伸ばすパターンと名付けます。 sステップ後値の初期値0位置からの距離をLlとおきましょう。 例の5ステップ目はLl=6となります。
89 : 例からも分かるように、Ln=Llの時とLn=Ll+1の時があります。 これ以外はないことを証明します。 コラッツパターンのルールより、1ステップ後の右端は+0 or +1です。 左端に+1しているから、Ln≧Llです。 なので、Ln=Llから1ステップ後Ln=Ll+1になるところを考えてみます。 http://cdn-ak.f.st-hatena.com/images/fotolife/r/righ1113/20130713/20130713165031.jpg 図より、Ln=Ll→Ln=Ll+1になることはありえるが、その次のステップで Ln=Ll+1→Ln=Llになるので、2以上ずれることはありません。 Ln=Ll or Ln=Ll+1です。
90 : sステップ後値の初期値0位置からの距離Lnは、 コラッツパターンを2進数で書いているのでlog[2]の対数目盛と見なして、 sステップ後コラッツ値のlog[2]を取れば良いことになります。 コラッツ操作27→41を変形すると (27*3+1)/2 = 41 = (27+1/3)*3/2 = 27*(1+1/(3*27))*3/2 logをとって log41 = log27 +log(1+1/(3*27)) +log(3/2) コラッツ操作41→31を変形すると (41*3+1)/4 = 31 = (41+1/3)*3/4 = 41*(1+1/(3*41))*3/4 logをとって log31 = log41 +log(1+1/(3*41)) +log(3/2) -log2 = log27 + log(1+1/(3*27))(1+1/(3*41)) +2*log(3/2) -log2 よって一般化するとLnは以下になります。 引き算の部分はコラッツパターンでは右によせているので消えます。 Ln = [log(x) +s*log(3/2) +log(1+1/3x)…(1+1/3x_s-1)] 左端を伸ばすパターンの式は、初期値に次々と3/2をかければ良いので log( x*(3/2)^n ) = log(x) +s*log(3/2) となります。切り上げてLl = [log(x) +s*log(3/2)]です。
91 : よって、>>89 より最大でもLn=Ll+1なので、 [log(x) +s*log(3/2) +log(1+1/3x)…(1+1/3x_s-1)] = [log(x) +s*log(3/2)] +1 切り上げを外して log(1+1/3x)…(1+1/3x_s-1) < 2 logをとって (1+1/3x)…(1+1/3x_s-1) < 4 となります。
92 : もしコラッツ予想で4-2-1以外のループがあったら (1+1/3x)…(1+1/3x_s-1) の中のループ1周期の積をXとおいて X*X*X*… となりますが、X>1なので、いずれ X*X*X*… > 4 となって (1+1/3x)…(1+1/3x_s-1) < 4 と矛盾します。 よって コラッツ予想で4-2-1以外のループは存在しない ことが証明できました。
93 : >>89 の画像の上から2番目の図で、 コラッツパターンは11、左端を伸ばすパターンは01 となることはないか?
94 : ちょっとまってください
95 : 一通り検証したけど、そこ以外は間違いはなさそう 本質的に難しいのはここなのかも 直接修正できなくても、Ln-Llが上から抑えられさえすればおk
96 : >>93 >>95 ありがとうございます。 指摘の部分ですが、すぐにできそうにないです。 >>89 の画像の上から2番目の図で、 コラッツパターンが0011、左端を伸ばすパターンは**01の時は、 同じように次々ステップでずれはなくなります。 コラッツパターンが0111、1011、1111の時はどうしよう……
97 : 修正できました。流れは以下です。 初めてコラッツパターンと左端を伸ばすパターンがずれる所を考える ずれるステップをsとおく ↓ s-1,s-2,s-3のずれはない ↓ 特定のパターン(2つ)しかあらわれない ↓ その特定のパターンはsでずれて、s+1,s+2,s+3ではずれない ↓ 次にずれる時s2も、s2-1,s2-2,s2-3のずれはない
98 : 特定のパターン1つ目です。 コラッツパターン 左端を伸ばすパターン s-3 **1 ***1 s-2 *11 **11 s-1 0101 **101 s 0000[1] *1111 s+1 **011 101101 s+2 **1001 ***0001 s+3 *11011 *****11 特定のパターン2つ目です。s+2でまたずれるのでs'と置きなおしています。 コラッツパターン 左端を伸ばすパターン s-3 **1 ***1 s-2 *11 **11 s-1 0101 *1001 s 0000[1] 11011 s+1 **011 ***101 s+2 -> s' **100[1] **1111 s+3 -> s'+1 *11011 *101101 s+4 -> s'+2 **00101 *******1 s+5 -> s'+3 ***1111 ******11 Ln=Ll or Ln=Ll+1が言えます。
99 : ぐじゃりましたね。こうです。 http://cdn-ak.f.st-hatena.com/images/fotolife/r/righ1113/20130803/20130803214250.jpg
100read 1read 1read 100read TOP カテ一覧 スレ一覧 2ch元 削除依頼 ▲
圏論による世界の記述 (181)
7ってなんかお姉さんっぽくね? (139)
初等幾何学の難問(中学レベル) (183)
ホモトピー,ホモロジー,ホモロジー代数コホモロジー (172)
さてテストが迫ってきたのだが (729)
数研・チャート式について語ろう (291)
--log9.info------------------
【キモ女装】千葉つかさスレッド2【出禁祈願】 (143)
戦国BASARAシリーズのスレ (117)
【コスプレ】一人暮らししてるレイヤー【自由人】 (203)
一番可愛いメイド (217)
第一章Schatzkiste 失われた屋根裏 (281)
【宣伝乙トカ】北海道 くりころり【イワナイノ】 (820)
【痛い】遊戯王レイヤースレ2【推奨】 (123)
【秋葉原】魔女メイドカフェEnchant【ACEグループ】 (150)
【茨城】県民イベント事情 (122)
【南港行くやつは敵】馬姫(桜樹姫乃)専用晒しスレ (559)
メイドに本気で恋してしまったみたいです・・・ (208)
アイドルプロデュースカフェ 喫茶全力 (239)
秋葉原@ほぉ〜むcafe【新人】を語るスレその7 (790)
秋葉原@ほぉ〜むcafe【ドンキ】を語るスレ (500)
小倉メイドカフェ★シューティングスター☆6星目 (911)
【猫耳】名古屋・大須のリリラドール3【カフェ】 (355)
--log55.com------------------
Jリーグ動画総合スレ Part4
〜 ドメサカaaなてすとすれ Part2〜
松本山雅FCのサポーターに対する感想
ジュビ騙554
琉球と鹿児島にJ2を教えるスレ
【分かりやすいし公平】新しいPK戦のルール考えた【画期的】
松江シティFC Part6
。○ 小さな 幸せ ○。