コラッツ予想がとけたらいいな
■ このスレッドは過去ログ倉庫に格納されています
525 名前:132人目の素数さん[sage] 投稿日:2012/09/03(月) 18:24:27.22 http://d.hatena.ne.jp/righ1113/ コラッツ予想について、証明を考えてみました。 ご指摘ご意見ご感想など、ぜひよろしくお願いします。 わかったよ 証明できるかも 学校の先生に聞いてみる 無限大に発散するほう、できました。 コラッツ値xsが無限大に発散するとします。 xs = x0 *3^s/2^l *(1+1/3x0)…(1+1/3x_s-1) xs < x0 *(3/2)^s s<lなので かっこの部分を考えます。 (1+1/3x0)…(1+1/3x_s-1)… > (1+1/3x0)…(1+1/(3x0*(3/2)^(s-1)))… > 1 +1/3x0 +1/3x0(3/2) +…+1/3x0(3/2)^(s-1) +… 等比数列の和 1+1/x0 < (1+1/3x0)…(1+1/3x_s-1)… 左辺第二項を大きくして、イコールになるところをα0とおく 1+α0/x0 = (1+1/3x0)…(1+1/3x_s-1)… @ 同様にx1からスタートして 1+α1/x1 = (1+1/3x1)…(1+1/3x_s-1)… A Aを@に代入 (1+1/3x0)(1+α1/x1) = 1+α0/x0 きれいにして (3α0-1)x1 = α1(3x0+1) x1=(3x0+1)/2^qを代入して (3α0-1)(3x0+1) = 2^q * α1(3x0+1) x0の部分が消えて α1 = α0 * 3/2^q * (1-1/3α0) xsが発散する → q=1が多い、αsが大きくなるとかっこの効果も弱まる → αsも発散する 一方、無限大に発散するコラッツ列でx0を最小値にとれば、 x0からx∞まで等比数列で下から押えられる と仮定する。 xs > x0*a^s B (1+1/3x0)…(1+1/3x_s-1)… < (1+1/3x0)…(1+1/(3x0*a^(s-1)))… ≒ 1 +1/3x0 +1/3x0a +…+1/3x0a^(s-1) +… 不等号が成り立つようにaを少し小さくする (1+1/3x0)…(1+1/3x_s-1)… = 1+α0/x0 < 1+1/x0 *a/3(a-1) コラッツ列をグラフにした時に、下に凸な点を考える。 x0より後でx0の次に小さいxm1で 1+αm1/xm1 < 1+1/xm1 *a/3(a-1) xm1より後でxm1の次に小さいxm2で 1+αm2/xm2 < 1+1/xm2 *a/3(a-1) このプロセスはいくらでも続けられるので、 αmは発散するが、a/3(a-1)は一定なので矛盾する。 あとはBを証明すれば良い。 傾きaは、x0 *a^s < xsを満たすので、 log(a) < log(xs/x0)/s = log(x0 *3^s/2^l *(1+1/3x0)…(1+1/3x_s-1) /x0)/s = log3 -l/s +logA/s (1+1/3x0)…(1+1/3x_s-1) = Aとおく コラッツパターンより l-s < log(xs)なので、 l/s < log(xs)/s +1 = log(x0)/s +log3 -l/s +logA/s +1 l/s < log(x0)/2s +log(3)/2 +logA/2s +1/2 l/sはsが大きくなると小さくなるので、傾きaはsが大きくなると大きくなる。 (直線x0-xm1の傾きより、x0-xm2、x0-xm3…の傾きのほうが大きい。 aを直線x0-xm1の傾きにとれば、コラッツ値はそれより上にある。) 以上で コラッツ予想で無限大に発散する数はない ことが証明できました。 >>106 の l-s < log(xs) は自明じゃなかったです。 修正します。 修正できました。証明したい補題は以下です。 無限大に発散するコラッツ列でx0を最小値にとれば、 x0からx∞まで等比数列で下から押えられる xs > x0*a^s B コラッツパターンにおいて、左端の傾きをd1、 右端の傾きをd2(=log1.5)とおきます。 sステップ後の左端までの距離l-sは l-s = s*d1 で、左端から右端までの距離log(xs)は log(xs) = log(x0) +s*d2 -s*d1 です。 s*d1≦log(x0)の区間では s*d1≦log(x0) +sd1 -sd1 < log(x0) +sd2 -sd1 ∵ d1 < d2 l-s < log(xs) が成り立ちます。 s0 < s < sgまでxs > x0*a^sが成り立つ事がわかりました。 あとはこれをs∞まで広げれば良いわけです。 s0からsgの間に傾きaを上回る二点xf,xf+1が存在する 事が言えます。もしなかったらコラッツ値のグラフが傾きa直線とぶつかって 矛盾するからです。 xf,xf+1でも同様に xs > xf * b^t s < sh が言えます。変形して > x0 * a^f * b^t > x0 * a^(f+t) ∵ a<b 成り立つ区間がs < sgからs < sg < shにのびました。 このプロセスを繰り返せばs∞までxs > x0*a^sが言えます。 Bが証明できました。 >>109 の s0からsgの間に傾きaを上回る二点xf,xf+1が存在する をちゃんと説明すると、 http://cdn-ak.f.st-hatena.com/images/fotolife/r/righ1113/20131006/20131006025445.jpg 図のように s0からsgの間に、コラッツ値x0,x1,x2,x3をとる x1,x2,x3とx0との傾きは、sが大きくなるに従って大きくなるので、 x0-x1傾き < x0-x2傾き < x0-x3傾き ⇒ x0-x1傾き < x2-x3傾き よって s0 < s < sgまでxs > x0*a^s s < sh xs > xf * b^t において a < b が言えます。 >>115 コラッツ操作で9232を通過する数がどうして多いか、ということですか。 自分は偶数を省いてやってたので気づきませんでした。 調べてみます。 xを最大値に持つ数の個数をコンピュータで調べました。 500000くらいまで調べました。以下の事が分かりました。 ・ほとんど0個 ・1/5ぐらいで5個とか ・1/3000ぐらいで50個とか ・225988を最大値に持つ数は386個 ・250504を最大値に持つ数は1759個 ・560356を最大値に持つ数は500個 ・575728を最大値に持つ数は550個 ・695464を最大値に持つ数は612個 9232の1579個を超える数も見つかりました。 ごくまれに大きい個数が出てくるみたいです。 なぜこんなに偏っているのかは謎です…… ソースコードです。Haskellです。 Prelude> :l tree *CTree> map colmaxcnt [1..100] のように使います。 -- tree.hs start module CTree where data CTree = Leaf Int | Node CTree Int CTree deriving (Eq,Show) collatz :: Int -> Int collatz 1 = 1 collatz x | odd x = x * 3 + 1 | otherwise = x `div` 2 -- 木を引数まで成長させる growm :: Int -> CTree -> CTree growm _ (Leaf 0) = Leaf 0 growm y (Leaf x) | x > y = Leaf 0 | even(x)&&((mod (x-1) 3)==0) = (Node (Leaf $ div (x-1) 3) x (Leaf $ x*2)) | otherwise = (Node (Leaf 0) x (Leaf $ x*2)) growm y (Node t1 x t2) = (Node (growm y t1) x (growm y t2)) flatten :: CTree -> [Int] flatten (Leaf x) = [x] flatten (Node t1 x t2) = flatten(t1) ++ [x] ++ flatten(t2) -- 空でないリストから収束した値を返す conver :: Eq a => [a] -> a conver [x] = x conver (x1:x2:xs) = if x1==x2 then x1 else conver (x2:xs) -- 最終結果 colmaxcnt :: Int -> Int colmaxcnt 4 = 2 colmaxcnt x = if (any (x<) col) then 0 else chk where col = takeWhile (1/=) (iterate collatz x) chk = length $ filter (\x->x/=0) $ flatten $ conver $ iterate (growm x) (Leaf x) 9232 が目立ってみえるのは、単に小さい初期値でしか調べてないから 9232未満の6分の1程度が9232に恋をして散ってしまう、というのは特筆すべきことだと思うけど。 無限大の証明ですが、間違っていました(>_<) αは有限値をとるみたいです。 >>103-110 は無しでお願いします。 新しい証明を考え中です。 あ、でも>>87-99 の 4-2-1以外のループは存在しない証明は自信あります。 【検証】コラッツの予想(1-1000) http://r-2ch.com/t/math/1240289175/ (>>12 と同じ)にあった割数列というのを調べている。 これで全ての3の倍数の奇数を表わせないかなと。 気になるレスを抜き出してみる。 106 4 年前 ざっと計算機を回してみた感じでは、 任意の3の倍数でない奇数xに対して3の倍数yが存在して、 x∈collatz_set(y) が成り立ちそうに見える。 80 ID: 2009/05/15 20:59 108 4 年前 もし>>106 が成り立てば、コラッツの予想は3の倍数だけ調べればいいってことになって、 コラッツ素数の概念にもそれなりに意味が出てくる。 個人的には、そうであって欲しいところだ。 80 ID: 2009/05/15 21:25 110 4 年前 3で割り切れない数を9で割った余りは、1,2,4,5,7,8のどれかだけど、これは 1*2^6≡1 2*2^5≡1 4*2^4≡1 5*2^1≡1 7*2^2≡1 8*2^3≡1 (mod 9) のように、どれも2を適当な回数掛けることで、9で割ると1余る偶数にできる。 ここから1を引いて3で割れば3の倍数である奇数になる。 >>106 の予想は正しい。 132人目の素数さん ID: 2009/05/16 00:38 285 4 年前 >>283 ありがとう!ここから何か出てこないかな・・ 一つ、完全割数列→完全割数列に関しての操作を見つけた。 長さnの完全割数列→長さn+1の完全割数列 まず、長さnの完全割数列を、初項に0をつけたn+1型で表す。 長さnの完全割数列でできる最終値を9で割ったあまりが・・ 3 ・・ [4,+2]or[1,-2]をつける 6 ・・ [2,+2]or[3,-2]をつける 0 ・・ [6,+2]or[5,-2]をつける 分かりづらいと思うので例を。 21≡3(mod 9) 21=[0,6] このとき、[4,6+2]と[1,6-2]が存在する。 ちなみに、[0,1,…,]みたいに、2項目(本来の初項)が1か2のときは2で引けない。 このときは本来の初項に6を足した[0,7,…,]から考える。本来の初項に6の倍数を加減してもOKなので。 170 ID: 2009/07/22 22:04 289 4 年前 全ての完全割数列を列挙できるかはゴメン、証明してないや。 でも、ちょっとやればできる気がする。今度時間ができたとき確信を得てみるよ。 >どの数から始めても、コラッツ数列は一意に定まるからね。 確かにそうだね。これ書いた時は、一意でないものがあればそいつは1421以外のループをもつのかと なんとなく思っていたけど、割数列を基に1スタートで逆にたどっていくならば どこかでループしてしまうような値にはたどり着かないもんね。 ループしてしまうならば1にたどり着かないのだから。 「完全割数列で全ての3の倍数の奇数を表せる」だけ分かれば良いか。 170 ID: 2009/07/22 23:40 この問題が長年解かれないのは解こうとするのがアマばかりなのも一因だと思うよ フェルマー・ワイルズの定理みたいに、これが解けたら重要な予想が証明できるってことがあるといいんだけど。何かあるんだったっけ? >>135 違うよ。もうアマしか残ってないだけだよ。 かつて簡単に解けるだろうとコラッツ予想に手を出して時間を浪費した、 数多の研究者の屍で山が築かれたから。 __ノ)-'´ ̄ ̄`ー- 、_ , '´ _. -‐'''"二ニニ=-`ヽ、 / /:::::; -‐''" `ーノ / /:::::/ \ / /::::::/ | | | | | |:::::/ / | | | | | | | |::/ / / | | || | | ,ハ .| ,ハ| | |/ / / /| ,ハノ| /|ノレ,ニ|ル' | | | / / レ',二、レ′ ,ィイ|゙/ . | \ ∠イ ,イイ| ,`-' | | l^,人| ` `-' ゝ | | ` -'\ ー' 人 私は死なないわよ。 | /(l __/ ヽ、 でも最近一寸太ったかしら。 | (:::::`‐-、__ |::::`、 ヒニニヽ、 Windows ver.10 で | / `‐-、::::::::::`‐-、::::\ /,ニニ、\ 元の痩せた姿にしてよね。 | |::::::::::::::::::|` -、:::::::,ヘ ̄|'、 ヒニ二、 \ . | /::::::::::::::::::|::::::::\/:::O`、::\ | '、 \ | /:::::::::::::::::::/:::::::::::::::::::::::::::::'、::::\ノ ヽ、 | | |:::::/:::::::::/:::::::::::::::::::::::::::::::::::'、',::::'、 /:\__/‐、 | |/:::::::::::/::::::::::::::::::::::::::::::::::O::| '、::| く::::::::::::: ̄| | /_..-'´ ̄`ー-、:::::::::::::::::::::::::::::::::::|/:/`‐'::\;;;;;;;_| | |/::::::::::::::::::::::\:::::::::::::::::::::::::::::|::/::::|::::/:::::::::::/ | /:::::::::::::::::::::::::::::::::|:::::::::::::::::::::O::|::|::::::|:::::::::::::::/ まず、>>133 の各変換に名前をつけ、式であらわす。 A:[4,2] B:[1,-2] C:[2,2] D:[3,-2] E:[6,2] F:[5,-2] そしてG:[+6] H:[-6] 981[7,1...]⇒15[1,1...]⇒81[2,3,1...]のように、 まずHをおこなってC(A,E)をおこなう変換は頭にHをつけて HA,HC,HEであらわす。 変換前のコラッツ値をxとおくと変換後は、 HA:[4,2] x/3-2 B:[1,-2] x/3/2-1/2 HC:[2,2] x/3/4-3/4 D:[3,-2] 2x/3-1 HE:[6,2] 4x/3-7 F:[5,-2] 8x/3-3 G:[+6] 64x+21 となる。 ◆注意点1 HC:117[5,1...]⇒ナシ[-1,1...]⇒9[2,1...]のように、 H後にマイナスになる場合がある。 ◆注意点2 HC:981[7,1...]⇒15[1,1...]⇒C:⇒81[2,3,1...]のように、 A,C,EはHA,HC,HEとしてもあらわれる。 各変換でどのような数があらわれるか見ていく。 B:[1,-2] x/3/2-1/2は21+72xを【3+12x】にうつす。 (例 21/3/2-1/2=3) HC:[2,2] x/3/4-3/4は117+288xを【9+24x】にうつす。 D:[3,-2] 2x/3-1は69+72xを【45+48x】にうつす。 HA:[4,2] x/3-2は213+288xを【69+96x】にうつす。 F:[5,-2] 8x/3-3は45+72xを【117+192x】にうつす。 HE:[6,2] 4x/3-7は309+288xを【405+384x】にうつす。 G:[+6] 64x+21は3+6xを【213+384x】にうつす。 【3+12x】【9+24x】【45+48x】【69+96x】【117+192x】【405+384x】【213+384x】 と割数列1項[6]であらわされる【21】を加えて、 全ての3の倍数の奇数は完全割数列で表わされる。 変換でマイナス値を経由するとか、あやしいところもあるので >>133 を書き換えます。 長さnの完全割数列→長さn+1の完全割数列 まず、長さnの完全割数列を、初項に0をつけたn+1型で表す。 長さnの完全割数列でできる最終値を9で割ったあまりが・・ 3 ・・ A:[6,-4]orB:[1,-2]をつける 6 ・・ C:[4,-4]orD:[3,-2]をつける 0 ・・ E:[2,-4]orF:[5,-2]をつける 元の初項が負になる場合はあらかじめG:[+6]をおこなう。 >>141 を証明します。 A〜FとGの各変換で[3の倍数の奇数]を[3の倍数の奇数]に写す 事を証明します。 A:[6,-4] 3 mod 9かつ奇数から変換前の数xは 18t+3 さらに割数列の初項が4以下は変換できないから (18t+3)*3+1= 54t+10 tが奇数の場合を除外、 さらに3=[1,…]だからt=0も除いて、 x=36t+3、t=1,2,3,… これが変換前の数。 A[6,-4]の変換関数は (((3x+1)*2^-4-1)/3*2^6-1)/3 = 4x/3-7。 変換後の数は4x/3-7 にx=36t+3 を代入して 48t-3= 45,93,… は3の倍数の奇数である。 A書き直します。 A:[6,-4] 3 mod 9かつ奇数から変換前の数xは 18t+3 さらに3=[1,4]だからt=0も除いて、 x=18t+3、t=1,2,3,… これが変換前の数。 A[6,-4]の変換関数は (((3x+1)*2^-4-1)/3*2^6-1)/3 = 4x/3-7。 変換後の数は4x/3-7 にx=18t+3 を代入して 24t-3= 21,45,69,… は3の倍数の奇数である。 B:[1,-2] 3 mod 9かつ奇数から変換前の数xは 18t+3 さらに割数列の初項が4以下は変換できないから (18t+3)*3+1= 54t+10⇒27t+5 tが偶数の場合を除外、 x=18(2t+1)+3、t=0,1,2,3,… これが変換前の数。 B[1,-2]の変換関数は (((3x+1)*2^-2-1)/3*2^1-1)/3 = x/6-1/2。 変換後の数はx/6-1/2 にx=18(2t+1)+3 を代入して 6t+3= 3,9,15,… は3の倍数の奇数である。 C:[4,-4] 6 mod 9かつ奇数から変換前の数xは x=9(2t+1)+6、t≧0 C[4,-4]の変換関数は (((3x+1)*2^-4-1)/3*2^4-1)/3 = x/3-2。 変換後の数はx/3-2 にx=9(2t+1)+6 を代入して 3(2t+1)+0= 3,9,15,… は3の倍数の奇数である。 D:[3,-2] 6 mod 9かつ奇数から変換前の数xは x=9(2t+1)+6、t≧0 D[3,-2]の変換関数は (((3x+1)*2^-2-1)/3*2^3-1)/3 = 2x/3-1。 変換後の数は2x/3-1 にx=9(2t+1)+6 を代入して 3*2(2t+1)+3= 9,21,33,… は3の倍数の奇数である。 E:[2,-4] 0 mod 9かつ奇数から変換前の数xは 9(2t+1) さらに割数列の初項が4以下は変換できないから 9(2t+1)*3+1= 54t+28⇒27t+14 tが奇数の場合を除外、 9(4t+1)*3+1= 108t+28⇒27t+7 tが偶数の場合を除外、 x=9(4(2t+1)+1)、t=0,1,2,3,… これが変換前の数。 E[2,-4]の変換関数は (((3x+1)*2^-4-1)/3*2^2-1)/3 = x/12-3/4。 変換後の数はx/12-3/4 にx=9(4(2t+1)+1) を代入して 6t+3= 3,9,15,… は3の倍数の奇数である。 F:[5,-2] 0 mod 9かつ奇数から変換前の数xは x=9(2t+1)、t≧0 F:[5,-2]の変換関数は (((3x+1)*2^-2-1)/3*2^5-1)/3 = 8x/3-3。 変換後の数は8x/3-3 にx=9(2t+1) を代入して 48t+21= 21,69,117,… は3の倍数の奇数である。 G:[+6] 3の倍数の奇数から変換前の数xは x=3(2t+1)、t≧0 G:[+6]の変換関数は ((3x+1)*2^6-1)/3 = 64x+21。 変換後の数は64x+21 にx=3(2t+1) を代入して 384t+213= 213,597,981,… は3の倍数の奇数である。 A~G全ての変換で[3の倍数の奇数]から[3の倍数の奇数]に写る事がわかったので >>141 が証明できました。 各変換でどのような数があらわれるか見ていく。 B:[1,-2] x/3/2-1/2はx=21+72tを【3+12t】にうつす。 E:[2,-4] x/3/4-3/4はx=117+288tを【9+24t】にうつす。 D:[3,-2] 2x/3-1はx=69+72tを【45+48t】にうつす。 C:[4,-4] x/3-2はx=213+288tを【69+96t】にうつす。 F:[5,-2] 8x/3-3はx=45+72tを【117+192t】にうつす。 A:[6,-4] 4x/3-7はx=309+288tを【405+384t】にうつす。 G:[+6] 64x+21はx=3+6tを【213+384t】にうつす。 【3+12t】【9+24t】【45+48t】【69+96t】【117+192t】【405+384t】【213+384t】 と割数列[6]であらわされる【21】を加えて、 全ての3の倍数の奇数は、>>141 変換後の完全割数列で表わされる。 全ての3の倍数の奇数は、完全割数列で表わされる事はわかったが、 それが無限の長さの完全割数列かもしれない。 というわけで、命題 「全ての完全割数列は、[6]に初項への6の加減と>>141 を有限回行うことで得られる」 ⇒「無限の長さの完全割数列は存在しない] の証明が必要……だと思う。 狸 >6 名前:KingMathematician ◆LoZDre77j4i1 :2014/07/15(火) 20:00:03.07 > [>>1 ]の親は強制的に[>>1 ]を集団から隔離するべし. > >660 名前:KingMathematician ◆LoZDre77j4i1 :2014/07/15(火) 20:02:50.12 > Re:>>658 (10+a)(10+b)=100+10(a+b)+ab. > うーん、思ってる証明をしても、無限の長さの完全割数列を排除できない気がしてきた…… できました。 あんまり自信ないけど。 いくつか補題を証明します。 <補題1> 3の倍数の奇数から始まるコラッツ列で無限に大きくなるものはない →すべてのコラッツ列で無限に大きくなるものはない <証明> >>132 で、コラッツ列を逆にたどれば3の倍数の奇数にぶつかるから、 あるコラッツ列で無限に大きくなるものがある →3の倍数の奇数から始まるコラッツ列で無限に大きくなるものがある これの対偶を取って証明できる。 <補題2> 無限に大きくなるコラッツ列の割数列で、項が繰り返しになるものはない <証明> 割数列の繰り返し部分をa1,...,anとおいて、その時のコラッツ値を一周期毎にx,y,z,wとおくと 3^n*x +3^(n-1) +3^(n-2)*2^a1 +... +2^a1~a_(n-1) = 2^a1~an*y 3^n*y +3^(n-1) +3^(n-2)*2^a1 +... +2^a1~a_(n-1) = 2^a1~an*z 3^n*z +3^(n-1) +3^(n-2)*2^a1 +... +2^a1~a_(n-1) = 2^a1~an*w から 3^n*(y-x) = 2^a1~an*(z-y) 3^n*(z-y) = 2^a1~an*(w-z) n≧1だから、z=yとなる。これはループするコラッツ列なので、無限に大きくなならない。 <補題3> すべての3の倍数の奇数は、>>141 変換後の割数列であらわされる <証明> >>150 です。 <定理1> 長さnの割数列から長さn+1の割数列への変換 >>141 <証明> >>143-149 です。 無限に大きくなるコラッツ列が存在すると仮定する。 このときの割数列は無限に長いものとなる。 これは、<定理1>に無限に適用でき、無限に逆適用できる。 変換Gであらわされる割数列は同一視して、 図であらわすと、上にも下にも無限に長い二分木(二分木A)となる。 <補題2>より、割数列の項は繰り返しにならないから、二分木の要素はそれぞれ異なるものとなる。 また、有限の長さの割数列では、[6]を根とする下に無限に長い二分木(二分木B)となる。 この二つを比べると、二分木Aのほうが個数が多い。 対応する点を子から親へ変えても、さらに親が存在するから、とりつくせない部分が存在し、 二つの集合は一対一対応がつかない。 二分木Bは可算集合だから、二分木Aは非可算集合である。 <補題3>より、すべての3の倍数の奇数は、<定理1>変換後の割数列であらわされるが、 すべての3の倍数の奇数は可算集合だから、二分木Aと対応がつかないので矛盾する。 よって、無限に大きくなるコラッツ列は存在しない。 コラッツの問題で、4->2->1以外のループが存在しないことって、示されてないよね。調べても出てこなかった アマだと論文を発表する機会がほとんどないからアレだよな >>160 上にも下にも無限に長い二分木は 16 4 17 1 5 18 19 2 3 6 7 20 21 22 23 8 9101112131415 2425262728293031 32... このように番号をふれば、可算集合と一対一対応がつく。 証明、ダメでしたー。 >>162 示されてないですねー でも僕は>>87-99 で 4-2-1以外のループは存在しない事をいったつもりです。 別のやりかたを考えました。 >>141 変換再掲 A:[6,-4] 4x/3-7 B:[1,-2] x/3/2-1/2 C:[4,-4] x/3-2 D:[3,-2] 2x/3-1 E:[2,-4] x/3/4-3/4 F:[5,-2] 8x/3-3 G:[+6] 64x+21 無限に大きくなるコラッツ値のうち最小値をxとおく。 xから>>141 変換をさかのぼることを考える。 割数列は無限に長いので、いくらでもさかのぼれる。 各変換のどれがあてはまるかを考える。 >>141 変換の遷移をw→z→y→x,uとおく。 @まずさかのぼる変換のうちでGはない。 さかのぼった値がxより小さくなるから。 Ay→x、y→u変換で割数列の初項を-2、-4しているから、 yの割数列の初項は5以上。よってz→yはA or F。 BAより、y→xはE or F、Fはy < xとなるからない。 Cz→yがAの場合、w→zがB or Cとなって-2、-4できなくなるからない。 Dz→yがFの場合、w→zはA or F、AはCと同じ。 Fはその手前もFになって、さかのぼる事をくりかえすと コラッツ値がxより小さくなるからない。 よってどの変換も当てはまらないので、無限に大きくなるコラッツ列はない。 以上です。 >>92 では、4-2-1以外のループについて考察しているが、 同様の考察を4-2-1のループで行えば、やはり X*X*X*… が登場して、しかもX>1なので、いずれ X*X*X*… > 4 となって (1+1/3x)…(1+1/3x_s-1) < 4 と矛盾することになる。 つまり、4-2-1というループさえも矛盾していることになる。 つまり、証明のどこかが間違ってる。 と思ったらx_iは奇数しか出てこないのか。 じゃあ4-2-1の場合はX=1になるのか。 スマソ。 >>97-99 はおかしいと思う。次のような状況は起きないのか? ・sステップ目で最初のずれが生じて、Ln−Ll=1 となる。 ・以下、2014ステップの間はずれが生じない。つまり、Ln−Ll=1 がずっと維持される。 ・s2ステップ目で次のずれが生じて、Ln−Ll=2 となる。 ・以下、2014ステップの間はずれが生じない。つまり、Ln−Ll=2 がずっと維持される。 ・s3ステップ目で次のずれが生じて、Ln−Ll=3 となる。 : : : この場合、ずれはどんどん大きくなる。 >>99 の図をよく見たら、ずれが「解消」されてた。 「s+1,s+2,s+3ではずれない」=「新しいずれが生じない(Ln−Ll=1 が維持される)」 だと思ってた。 スマソ。 ちょっと待てよ、そもそも>>87 の例は何を表してるんだ? 下位ビットが左なのであれば、 >01011 13 これは10進法では26であって、13にならない。左端の0は何なのか? >000101 5 これは10進法では40であって、5にならない。左端の000は何なのか? >0000001 1 これは10進法では64であって、1にならない。左端の000000は何なのか? 勝手に左端に0を補完してもいいなら、Lnは好きなように変更できてしまうぞ。 指摘ありがとうございます。 コラッツパターンは>>87 の(1)(2)(3)(4)ルールに合うように、 左端に0を付け足しています。 コラッツ操作で<2で割った回数-1>を蓄積している、とも言えます。 17→52→26→13 <2で割った回数-1>:1 01011 13*2^1 13→40→20→10→5 <2で割った回数-1>:1+2 000101 5*2^3 5→16→8→4→2→1 <2で割った回数-1>:1+2+3 0000001 1*2^6 Lnは好きなように変更できてしまうことはないです。 >>173 0の個数のルールは分かった。だがLnが何なのか分からんw >sステップ後値の初期値0位置からの距離をLlとおきましょう。 >例の5ステップ目はLl=6となります。 「後値」とは何なのか? 「初期値0位置」とはどこなのか? 「初期値0位置からの距離」とは何なのか?――たとえば、a000b という 文字列があったとして、「文字aから文字bまでの距離」とは、 距離の測定の仕方によって「距離は4」とも言えるし「距離は5」とも言える。 つまり、単に「距離」と書いただけでは意味が定まらない。 あと、「例の5ステップ目」とあるが、ステップのカウントの仕方が 書いてないから意味が定まらない。具体的に言えば、一番最初の 「 111 7 」を「0ステップ目」とカウントしているのか 「1ステップ目」とカウントしているのか全く不明。 ついでに、>>88 も意味がわからんw >00000111 >000010101 >000111111 >0010111101 >01110110001 >10100101011 なぜ一番最初に00000が補完してあるのか?なぜ2行目に0000が補完してあるのか? 補完する個数のルールは何なのか?LlもLnと全く同様に意味がわからん。 >>175 把握した。 このルールだと、コラッツ値が 1 に到達してから先のステップでは、 Ln(s)−Ll(s) はどんどん大きくなって+∞に発散してしまうわけだが、 ということは、コラッツ値が 1 になるまでの s だけを考えるということか? あと、>>175 をよく見ると、>>99 のリンク先には無いパターンがあり、>>99 は不完全ということになる。 まず、>>99 のリンク先では、ずれが生じているステップ(赤い「1」が存在する行)が3箇所あり、それは s …00001 …1111 (←「特定のパターン1つ目」のもの。「ずれパターン1」と名づける) s …00001 …11011 (←「特定のパターン2つ目」のもの。「ずれパターン2」と名づける) s ' …1001 …1111 (←「特定のパターン2つ目」のもの。「ずれパターン3」と名づける) となっている(>>99 の図で空白のマスになっている部分は、ここでは「…」で表現した)。 一方で、>>175 では、s = 2 のときに最初のずれが生じ、そのときのパターンは、上の表記法に合わせると s …10001 …1111 となっている。「10001」の部分は、上記の「ずれパターン1,2,3」のいずれでもない。 同じく、>>175 では、s = 5 のときに2回目のずれが生じ、そのときのパターンは s …00001 …01011 となっている。「01011」の部分は、上記の「ずれパターン1,2,3」のいずれでもない。 また、>>99 では、「ずれパターン1」の場合は、一度ずれたら、その後の3ステップは ずれないことになっている。 「ずれパターン2」の場合は、直後の1ステップは ずれなくて、その後のステップで再び ずれることになっている。 しかし、>>175 では、s = 2 が「ずれ」, s = 3, 4 が「ずれなし」, s = 5 が「ずれ」 ということなので、 ずれないステップ数が2ステップであり、>>99 のどのパターンにも合致しない。 そうです。コラッツ値が1になるまでのsを考えます。 「10001」の部分は少し考えさせてください。 s=5のときはコラッツ値が1になっているので考えないです。 >>177 追い討ちをかける形になってしまうが、 多倍長整数を使ってプログラムを組んで実験したら、さらにマズイ例が見つかった。 初期値が 27 のとき、コラッツ値が 1 になるまでの範囲でずれが生じるステップは s = 14, 26, 31, 38, 41 の5回のみ。 s = 41 でコラッツ値が 1 になるので、s = 41 は無視することにする。問題は s = 31 のときであり、s = 31 のときは コラッツ値 = 110000000001 (2進法, 左が下位バイト, 10進法では2051) 伸ばすやつ = 100100010100110000001000110011110111001111111100110111 (2進法, 左が下位バイト, 10進法では 27 * 3^31) となっている。すなわち、 s …00001 …10111 (☆) となっている。「10111」の部分は、「ずれパターン1,2,3」のいずれでもない。なお、このときのコラッツ値は10進法で2051であり、 まだ 1 に到達してないので、無視できない。[続く] [続き] さらに、実は直前の s = 30 のときも問題が起きている。s = 30 のときは コラッツ値 = 11101010101 (2進法, 左が下位バイト, 10進法では1367) 伸ばすやつ = 11000001110111010101101001100101111101111111110111001 (2進法, 左が下位バイト, 10進法では 27 * 3^30) となっている。すなわち、s = 31 と置けば s - 1 …0101 …1001 (★) となっている。s = 31 では ずれが起きていたから、そのことと上記の(★)を>>99 に照らし合わせると、 上記の(★)は「特定のパターン2つ目」「ずれパターン2の直前(青いマスに「10」が書いてある行)」に該当するはず。 そうなると、s = 31 のときは、>>99 によれば s …00001 …11011 でなければならないが、実際には >>178 の(☆) だったから合ってない。すなわち、やっぱり>>99 はおかしい。 ついでに言うと、(★)が「特定のパターン2つ目」「ずれパターン2の直前(青いマスに「10」が書いてある行)」であるのなら、 s = 31 及び s ' = 33 において ずれが生じることになるが、s = 31 はともかく、「33」の方では実際には ずれが生じなくて、 s = 38 にならないと ずれない。 なお、上記のデータはプログラム以外にも「 手作業 & wolfram alpha 」でも チマチマ計算して確認したから間違いないはず。 一応、補足しておくと、s = 30, 31 のときの、「コラッツ値」に補正する0の個数は「12個」になっている。 「伸ばすやつ」は、左端からs個だけ切り捨てるから、結局、 s = 30 00000000000011101010101 ( コラッツ値(補正版) ) 01111101111111110111001 ( 伸ばすやつ(補正版) ) s = 31 000000000000110000000001 ( コラッツ値(補正版) ) 10111001111111100110111 ( 伸ばすやつ(補正版) ) となり、s = 31 で ずれていることが分かる。 また、s = 30 は、>>99 における「特定のパターン2つ目」「ずれパターン2の直前(青いマスに「10」が書いてある行)」 であるはず(しかし、s >= 31 の領域で結果が合わない)。 あっ、既に>>130 にコメントがあった (´・ω・`) スマソ >>130 じゃなくて>>180 だったw (´・ω・`) スマソ ひとまず考えた事は、指摘2パターンも特定のパターンに加える事です。 そうすれば>>97 も有効のままで問題も解消されるはず。 >>184 ただ単に「特定パターンに加えました」っていうだけだと、何も問題は解消されない。 なぜなら、まだパターンの抜けがあるかもしれないから。 それらの「特定のパターン」によって全てのパターンがちゃんと網羅できているのかを、 数学的に厳密に証明しなくちゃいけない。 もちろん、新しく加えた「特定のパターン」が>>97 の構造を壊すようなら失敗だ。 まあ、その前に、「特定のパターン」を全て列挙し直すところから出発かな。 証明を戻して、>>89 に改良を加えたものにします。 2つのパターンがずれるステップをsとおきます。 s-1でコラッツパターンが01、左端を伸ばすパターンが01の時は、 >>89 の図の通り、s+1ステップでずれはなくなります。 s-1でコラッツパターンが11、左端を伸ばすパターンが01の時は、 (>>93 の指摘にもありました) まず左端を伸ばすパターンは *1001 s-1 11011 s *00101 **1111 ***1101 *******1 s+4 こうなります。 コラッツパターンの最大パターンは *1111 s-1 101101 s **10001 *101011 ***00101 ****1111 s+4 となります。 s+4ステップでずれはなくなります。 >>187 このケースは大丈夫っぽい。 >>188 左端を伸ばすパターンの1行目がいきなり > *1001 s-1 となっているが、これはどうして? **101 とか 10001 とかの場合は考えなくていいの? (***11の場合は考えなくてよい、ということは分かるが…) これって3n+1倍の操作を続けるといつかは2のべき乗にぶち当たるっていうことですか? >>189 説明不足ですみませんが、コラッツパターンは最大、左端を伸ばすパターンは最小を調べています。 それでずれがなくなるなら、他のパターンでもずれがなくなるはずですから。 よって**101は*1001より大きいので除外です。 10001はs-2ステップが定義できないので除外です。 >>190 そういう事ではないです。コラッツパターンと左端を伸ばすパターンのずれが最大でも1である事を言っています。 >>191 「最大パターン」と「最小パターン」の意味がよく分からない。 最大・最小というからには、何か指標 X が予め定義されていて、 その指標 X が最大値を取るパターン・最小値を取るパターンについてのみ 考えるということなのだろうが、ここで言う X は何なの? >10001はs-2ステップが定義できないので除外です。 ここもよく分からない。コラッツパターンを無視して、 左端をのばすやつだけを観察すると、どんな初期値に対しても、 「右端に10001が出現するようなステップが無限回でてくる」 ことが証明できる。そのようなステップのうち、2より大きいものを任意に取ってtとするとき、 s = t + 2 に対して、「s-2ステップで10001になっている」と言える。 もちろん、このときのsに対して、コラッツパターンがs-1で11になっているとは限らないが、 少なくとも「除外」とまでは言えないだろう。それとも、何か深い理由があるのかな。 ずれた時のコラッツ値が最大、最小パターンのみを考えるということです。 10001については勘違いしてました。調べなきゃだめですね…… >>193 この方針では「証明できそうにない」ことが分かった。 まず、コラッツパターンの最大値について。>>188 では、コラッツパターンの計算が >101101 s となっているが、これは間違っている。なぜなら、省略されている「*」の状況によっては 「111101」となる可能性があるからだ。コラッツパターンの最大値を考えるなら、採用すべきは 「101101」ではなく「111101」だろう。そして、「111101」が確実に起こるのは、 コラッツパターンが s-1 で *111111 となっている場合だ。 この考え方を突き詰めていくと、*1111 は最大値ではなく、*111111111 も最大値ではなく、 *1111111111111111111111111 も最大値ではない。理想的には ……1111 (左に向かって永遠に1が続く) が最大値となる。しかし、実際には有限桁で終わるものしか考えないので、 結局、コラッツパターンに最大値は無い。 とはいっても、上記の理想的な場合について計算することは無意味ではない。 この場合、計算の仕方は「×3を繰り返す」だけでよく、 「+1」は必要ない(というか、左末尾が無いので、どの桁にも「+1」が適用できない)。 (続く) (続き) 次に、左端を延ばすパターンの最小値について。*1001 は最小値ではなく、 *10001も最小値ではなく、*1000000000000000000000001 も最小値ではない。 理想的には ……0001 (左に向かって永遠に0が続く) が最小値となるが、実際には有限桁で終わるものしか考えないので、 結局、左端を延ばすパターンに最小値は無い。 とはいっても、上記の理想的な場合について計算することは無意味ではない。 この場合、計算の仕方は「×3を繰り返す」だけでよい。 これらの設定のもとで計算をすると、残念ながら 「常にギリギリ1だけ ずれた状態で、永遠に ずれが解消されない」(★) ことが証明できる。従って、理想的な場合についての計算では、証明に失敗する。 (続く) (続き) 実際には有限桁のものしか考えないので、有限桁の場合について考え直す必要がある。 コラッツパターンには最大値がなく、左端を伸ばすパターンには最小値が無いので、 コラッツパターン・左端を伸ばすパターンともに「任意の有限桁」を考えることになり、 つまりは無限通りある全てのパターンについて、いちいち個別に議論しなければならない。 実際には、「出来るだけ大きな、任意の有限桁」についてのみ考えればよいだろう。 この場合に問題となるのは、コラッツパターンの方である。上記の理想的な場合では、 「+1」の操作は無視できたが、有限桁の場合だと、ちゃんと「+1」の操作を考慮に 入れなければならない。 さて、コラッツパターン・左端を伸ばすパターンともに、「出来るだけ大きな有限桁」を 任意に取ろう。すなわち、 コラッツパターン:*111111111111111111111111111111111111111111111111111111111111111111111 (☆) 左端を延ばすやつ:*000000000000000000000000000000000000000000000000000000000000000000001 (☆) のようなイメージである。この状態で計算をすると、初めの方のステップでは、 「+1」の影響がまだ出てなくて、理想的な場合と計算結果は ほとんど変わらない。 特に、右端付近の0と1の並び方は、理想的な場合と完全に一致する(★★)。 ということは、(★)と(★★)により、もしずれが解消されるとしても、 そのタイミングは「かなり遅い」ということになる。 (続く) ずれた… 訂正。 コラッツパターン:*111111111111111111111111111111111111111111111111111111111111111111111 (☆) 左端を延ばす :*000000000000000000000000000000000000000000000000000000000000000000001 (☆) (続き) というわけで、「せいぜい s+4 あたりで、必ず ずれが解消される」などというわけにはいかない。 上記の(☆)において、桁数を多く取れば取るほど、ずれが解消されるタイミングを好きなだけ 「遅く」出来てしまうのだ。 しかし、本当の問題はここでは無い。 ずれが解消されるタイミングが「かなり遅い」のであれば、その頃には「+1」の影響が無視できなくなり、 理想的な場合とは計算結果に狂いが生じてくる。より具体的には、コラッツパターンの方は、 「+1」の影響により、理想的な場合よりも僅かに桁数の増え方が大きくなることが予想される。 そうなると、想定していたタイミングでは「ずれが解消されない」ということが起こり得る。 もっと悪いのは、「むしろ ずれが増大する」という可能性である。 このような状況は、実際に起こり得る。たとえば、もし 1→4→2→1 以外のループが存在するならば、 そのループにおいては、明らかに「ずれがどんどん増大する」ことが分かる。 そして、ずれが増大するメカニズムは、「ループするから」という理由のほかに、 「『+1』の影響が無視できなくなり、そこで計算結果に狂いが生じてくるから」 とも説明できる。こうなってくると、「ずれが解消される」ことを証明するよりも前に、まず 「ループが 1→4→2→1 以外に無い」ことを証明しなければならなくなり、本末転倒となる。 というわけで、この方針では、まず間違いなく、証明できないと思われる。 詳細な説明ありがとうございます。 どうしましょう…… コラッツパターンと左端を伸ばすパターンがずれるステップをsとおきます。 このとき、左端を伸ばすパターンのLl(s-1)=Ll(s)は、 Ll(s-1)=[log(x0)+(s-1)*log(3/2)] Ll(s)=[log(x0)+s*log(3/2)] です。 Ll(s-1)にlog(3/2)を足しても整数部分は変わらないので、 log(x0)+(s-1)*log(3/2)の小数部分は.0以上1-log(3/2)(≒.415)未満です。 また、 Ln(s-1)=[log(x0)+(s-1)*log(3/2)+log(1+1/3x0)…(1+1/3x(s-2))] で、Ln(s-1)=Ll(s-1)ですから、 0 < log(1+1/3x0)…(1+1/3x(s-2)) < log(3/2) が成り立ちます。 s-1の コラッツパターンの式はx0*(3/2)^(s-1)*(1+1/3x0)…(1+1/3x(s-2))で 左端を伸ばすパターンの式はx0*(3/2)^(s-1)なので、 コラッツパターンは左端を伸ばすパターンの1.5倍未満ということになります。 s-1のコラッツパターンの最大値は …11111で 左端を伸ばすパターンの最小値は …00001でしたが、 これに1.5倍の制限がかかって コラッツパターン:…11111 左端を伸ばすパターン:…10101 コラッツパターン:…00011 左端を伸ばすパターン:…00001 になります。 ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.1 2024/04/28 Walang Kapalit ★ | Donguri System Team 5ちゃんねる