コラッツ予想がとけたらいいな
■ このスレッドは過去ログ倉庫に格納されています
525 名前:132人目の素数さん[sage] 投稿日:2012/09/03(月) 18:24:27.22 http://d.hatena.ne.jp/righ1113/ コラッツ予想について、証明を考えてみました。 ご指摘ご意見ご感想など、ぜひよろしくお願いします。 コラッツの問題で、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 になります。 コラッツパターン:…11111 左端を伸ばすパターン:…10101 コラッツパターン:…00011 左端を伸ばすパターン:…00001 の遷移は 11111 s-1 111101 s 1110001 s+1 1101011 s+2 10101 s-1 11111 s 111101 s+1 1110001 s+2 00011 s-1 001001 s 011011 s+1 00001 s-1 00011 s 001001 s+1 となって、どちらもずれはなくなります。 >>199 >0 < log(1+1/3x0)…(1+1/3x(s-2)) < log(3/2) が成り立ちます。 ここが間違ってる。 log(1+1/3x0)…(1+1/3x(s-2)) ≧ log(3/2) の可能性もある。たとえば、log(x0)+(s-1)*log(3/2) の小数部分が「0.000000001未満」であって、しかも 0.9 > log(1+1/3x0)…(1+1/3x(s−2)) ≧ log(3/2) であるようなケースを考えると、Ll(s-1)=Ll(s)も成り立つしLn(s-1)=Ll(s-1)も成り立つ。 具体例は必要ないかもしれんが、一応。 log(x0)+(s-1)*log(3/2)=2014.0000000001… log(1+1/3x0)…(1+1/3x(s-2))=0.80… というケースがあったとすると、 0.9 > log(1+1/3x0)…(1+1/3x(s−2)) > log(3/2) であり、しかも Ll(s-1)=[log(x0)+(s-1)*log(3/2)]=[2014.0000000001…]=2014 Ll(s)=[log(x0)+s*log(3/2)]=[2014.0000000001…+0.5849625…]=2014 Ln(s-1)=[log(x0)+(s-1)*log(3/2)+log(1+1/3x0)…(1+1/3x(s-2))]=[2014.0000000001…+0.80…]=2014 となる。すなわち、Ll(s-1)=Ll(s)も成り立つしLn(s-1)=Ll(s-1)も成り立つ。 何か他の事情により、このようなケースが実際には起こらない可能性もあるが、 その場合は、そのことを証明しなければならない。 2chで穴を埋めてからarxivに投稿しようかな、と考えています。 ステップをさかのぼるとうまくいくのではないかと、まだ考え中です。 コラッツパターンと左端を伸ばすパターンがずれるステップを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)未満です。 これを.0〜.17と.17〜.415に分けます。 .17〜.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)) < 0.83 が成り立ちます。 0 < Ax(s-2) < 0.83 とします。 .0〜.17と.17〜.415のコラッツ値をy,xとおいて、ステップをさかのぼると、 Ays、Axsは単調増加なので、どこかで両方が0.7を下回ります。 そのステップをtとおきます。 Ayt < 0.7、Axt < 0.7 です。 Ay(t-1) < 0.7、Ax(t-1) < 0.7 でした。 Ax(t-1) + log(1+1/3xt)…(1+1/3x(s-2)) = Ax(s-2)なので log(1+1/3xt)…(1+1/3x(s-2)) < 0.13 です。 全てのxが1000とすると、 log(1+1/3/1000)^270 = 0.129 < 0.13 なので 全てのyが1000より大きいならば log(1+1/3yt)…(1+1/3y(s-2)) < 0.13、 Ay(s-2) < 0.83 となります。 コラッツ値が1000より大きいときは、 A(s-2) < 0.83 が成り立つことがわかりました。 >>12 のスレにいたもんだが、割数列について今更発見があったので報告しとく 自然数a,bに対し、 [a,b]が割数列 ⇔ b≡2(-1)^a (mod 6) 単純な式だけど、5年前はこれに気付かなかった さらに 自然数a,bに対し、 [a,b]が完全割数列 ⇔ (6a-4)+((-1)^a)(6-b)≡0 (mod 18) 自然数a,b,cに対し、 [a,b,c]が割数列 ⇔ (6b-4)+((-1)^b)(6-c)≡6(-1)^a (mod 18) が見つかった。こうやって式で表せば何かわかるかもと思ったけど、今のところサッパリ ぶれぶれですみませんが、また証明を戻して、>>99 特定のパターンを列挙する方向でいきたいと思います。 ちょっと先になります。今brainf*ckやってるので…… まだ穴を埋められませんが、今は、 コラッツパターンと左端を伸ばすパターンのずれがなくなる事を言うのに、 双方の上位nビットの全パターンを調べる という事を考えています。コンピュータを使おうと思っています。 予告とは違う物になりましたが、できたので書きます。 【言いたい事】 コラッツパターンと左端を伸ばすパターンのずれが有限値に収まる 新しいシミュレーションを2つ考えます。 【シミュレーションA】 1.nビットの初期値x0Aを用意する。 2.x0Aを下位へ1ビットシフトして(末尾は捨てる)、x0Aに加える。 3.最下位ビットに1加える。(下位からの繰り上がりが常に有る事を想定) 4.n+1ビットになっていたら、最下位ビットを捨ててnビットにする。 5.2~4を繰り返す。 得られる値をxsAとする。 【シミュレーションB】 1.nビットの初期値y0Bを用意する。 2.y0Bを下位へ1ビットシフトして(末尾は捨てる)、y0Bに加える。 (下位からの繰り上がりは常に無い) 3.n+1ビットになっていたら、最下位ビットを捨ててnビットにする。 4.2~3を繰り返す。 得られる値をysBとする。 xsA、ysB、コラッツパターン値xs、左端を伸ばすパターン値ys の大小関係を考えます。 コラッツパターンは、下位からの繰り上がりが有ったり無かったりするので、 Upper_nbit xs < xsA です。Upper_nbitは上位nビットを取るものです。 左端を伸ばすパターンは、下位からの繰り上がりが有ったり無かったりするので、 ysB < Upper_nbit ys です。 Upper_nbit ys < Upper_nbit xsは自明なので、まとめると、 ysB < Upper_nbit ys < Upper_nbit xs < xsA となります。 2つのシミュレーションA,Bを比べて、ずれが有限値に収まれば、 2つのシミュレーションA,Bにはさまれた xs,ysのずれも有限値に収まる、と言えます。 (続く) ysB ≦ Upper_nbit ys ≦ Upper_nbit xs ≦ xsA でした。 2つのシミュレーションA,Bのずれが有限である事を言うのに、 プログラムを使います。Haskellでやります。 ---------- module CollatzPatt where type Bit = Int plusDisplace :: [Bit] -> [Bit] plusDisplace x = zipWith (+) x ((tail x) ++ [0]) movesUp :: [Bit] -> [Bit] movesUp [x0] = case x0 of 0 -> [0] 1 -> [1] 2 -> [0,1] 3 -> [1,1] movesUp (x0:x1:xs) = case x0 of 0 -> 0 : movesUp (x1:xs) 1 -> 1 : movesUp (x1:xs) 2 -> 0 : movesUp ((x1+1):xs) 3 -> 1 : movesUp ((x1+1):xs) plusOne :: [Bit] -> [Bit] plusOne (x:xs) = ((x+1):xs) snd0or1 :: Int -> [Bit] -> Int snd0or1 n x = if n == length x then 0 else 1 bitCutdown :: Int -> [Bit] -> [Bit] bitCutdown n x = if n == length x then x else tail x colPattA :: ([Bit],Int) -> ([Bit],Int) colPattA (x,_) = let a = plusDisplace x b = movesUp a c = plusOne b d = movesUp c s = snd0or1 bitLen d e = bitCutdown bitLen d in (e,s) colPattB :: ([Bit],Int) -> ([Bit],Int) colPattB (x,_) = let a = plusDisplace x b = movesUp a s = snd0or1 bitLen b c = bitCutdown bitLen b in (c,s) loopTp :: [([Bit],Int)] -> [([Bit],Int)] loopTp x = loopTp' 2 x where loopTp' n x = if any (== fst (last x')) (init $ map fst x') then x' else loopTp' (n+1) x where x' = take n x bitLen = 9 collatzPatternA :: [([Bit],Int)] collatzPatternA = loopTp $ iterate colPattA ([1,1,1,1,1,1,1,1,1],0) collatzPatternB :: [([Bit],Int)] collatzPatternB = loopTp $ iterate colPattB ([0,0,0,0,0,0,0,0,1],0) ---------- n=9ビットで、欲しい結果が得られました。 結果です。 ---------- *CollatzPatt> collatzPatternA [([1,1,1,1,1,1,1,1,1],0),([1,1,1,1,1,1,1,0,1],1),([1,1,1,1,1,0,0,0,1],1),([1,1,1 ,1,0,1,0,1,1],0),([1,1,0,0,0,0,1,0,1],1),([1,0,1,0,0,1,1,1,1],0),([0,0,1,1,0,1,1 ,0,1],1),([1,0,0,0,1,0,0,0,1],1),([0,1,0,1,1,0,0,1,1],0),([0,0,1,0,1,1,0,0,1],1) ,([1,1,1,1,0,0,1,1,1],0),([1,1,0,1,1,0,1,0,1],1),([0,0,1,0,0,0,0,0,1],1),([1,1,1 ,0,0,0,0,1,1],0),([1,0,1,0,0,1,0,0,1],1),([0,0,0,1,1,1,0,1,1],0),([0,1,0,1,0,0,1 ,0,1],1),([0,0,0,0,1,1,1,1,1],0),([0,0,1,0,1,1,1,0,1],1),([1,1,1,0,1,0,0,0,1],1) ,([1,1,0,0,0,1,0,1,1],0),([0,1,0,1,1,1,0,0,1],1),([0,0,0,1,1,0,1,1,1],0),([0,1,0 ,0,0,1,1,0,1],1),([0,1,0,1,0,0,0,0,1],1),([0,0,0,0,1,0,0,1,1],0),([0,0,1,1,0,1,0 ,0,1],1),([1,1,0,0,0,0,1,1,1],0),([0,1,0,0,1,0,1,0,1],1),([0,0,1,1,1,1,1,1,1],0) ,([1,0,1,1,1,1,1,0,1],1),([0,1,1,1,1,0,0,0,1],1),([0,1,1,1,0,1,0,1,1],0),([1,1,0 ,0,0,0,1,0,1],1)] *CollatzPatt> collatzPatternB [([0,0,0,0,0,0,0,0,1],0),([0,0,0,0,0,0,0,1,1],0),([0,0,0,0,0,1,0,0,1],1),([0,0,0 ,0,1,1,0,1,1],0),([0,0,1,0,0,0,1,0,1],1),([0,1,1,0,0,1,1,1,1],0),([0,0,1,1,0,1,1 ,0,1],1),([1,0,0,0,1,0,0,0,1],1),([1,0,0,1,1,0,0,1,1],0),([0,1,0,0,1,1,0,0,1],1) ,([1,1,0,1,0,0,1,1,1],0),([0,0,0,1,1,0,1,0,1],1),([0,1,0,0,0,0,0,0,1],1),([1,1,0 ,0,0,0,0,1,1],0),([0,1,0,0,0,1,0,0,1],1),([1,1,0,0,1,1,0,1,1],0),([0,1,1,0,0,0,1 ,0,1],1),([1,0,0,1,0,1,1,1,1],0),([0,1,1,1,0,1,1,0,1],1),([0,1,0,0,1,0,0,0,1],1) ,([1,1,0,1,1,0,0,1,1],0),([0,0,1,0,1,1,0,0,1],1),([0,1,1,1,0,0,1,1,1],0),([0,1,0 ,1,1,0,1,0,1],1),([1,1,0,0,0,0,0,0,1],1),([0,0,1,0,0,0,0,1,1],0),([1,1,0,0,0,1,0 ,0,1],1),([0,0,1,0,1,1,0,1,1],0),([1,1,1,0,0,0,1,0,1],1),([0,1,0,1,0,1,1,1,1],0) ,([1,1,1,1,0,1,1,0,1],1),([1,1,0,0,1,0,0,0,1],1),([0,0,1,1,1,0,0,1,1],0),([1,0,1 ,0,1,1,0,0,1],1),([1,1,1,1,0,0,1,1,1],0),([1,1,0,1,1,0,1,0,1],1),([0,0,1,0,0,0,0 ,0,1],1),([0,1,1,0,0,0,0,1,1],0),([0,0,1,0,0,1,0,0,1],1),([0,1,1,0,1,1,0,1,1],0) ,([0,0,0,1,0,0,1,0,1],1),([0,0,1,1,0,1,1,1,1],0),([1,0,0,0,1,1,1,0,1],1),([0,0,1 ,0,1,0,0,0,1],1),([0,1,1,1,1,0,0,1,1],0),([0,1,1,0,1,1,0,0,1],1),([1,0,0,0,1,0,1 ,1,1],0),([0,0,1,1,1,0,1,0,1],1),([1,0,1,0,0,0,0,0,1],1),([1,1,1,0,0,0,0,1,1],0) ,([1,0,1,0,0,1,0,0,1],1),([1,1,1,0,1,1,0,1,1],0),([1,0,0,1,0,0,1,0,1],1),([1,0,1 ,1,0,1,1,1,1],0),([1,0,0,0,1,1,1,0,1],1)] ---------- collatzPatternAは、第33項が[1,1,0,0,0,0,1,0,1]となって、 第4項と一致します。その後は繰り返しになります。 collatzPatternBは、第54項が[1,0,0,0,1,1,1,0,1]となって、 第42項と一致します。その後は繰り返しになります。 collatzPatternAとBの第2要素を使って、2つのパターンのずれを比べます。 0ならば繰り上がり無しで、1ならば繰り上がり有りです。 #は、そこから繰り返しになっているという意味です。 *CollatzPatt> map snd collatzPatternA [0,1,1,0,1,#0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1] *CollatzPatt> map snd collatzPatternB [0,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1, 0,1,1,0,1,0,1,0,1,#1,0,1,0,1,1,0,1,0,1,0,1] 2つのパターンの第2要素を羅列します。繰り返しを並べていきます。 @はずれが1になっている所です。それ以降のはみ出た部分は、次の行にまわしています。 [0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,@1] [0,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,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,0,1,1,0,1,0,1,0,1,1,0,@1] 0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1]1,0,1,0,1,1,0,@1,0,1,0,1]★ここへ戻る 0,1,1,0,1,0,1,1,0,1,0,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,1,0,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,1,0,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,1,0,1,0,1,0,1]1,0,1,0,1,1,0,1,0,1,0,1]1,0,1,0,1,@1,0,1,0,1,0,1] 0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,@1] 0,1,0,1,0,1]1,0,1,0,1,1,0,1,0,1,0,1]1,0,1,0,1,1,0,1,0,1,0,@1] 0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,@1] 1]1,0,1,0,1,1,0,1,0,1,0,1]1,0,1,0,1,1,0,1,0,1,0,1]1,0,1,0,@1,1,0,1,0,1,0,1] 0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,@1] 1,1,0,1,0,1,0,1]1,0,1,0,1,1,0,1,0,1,0,1]1,0,1,0,1,1,0,@1,0,1,0,1] 0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,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,1,0,1,0,1,0,@1] 0,1]0,1,1,0,1,0,1,1,0,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,1,0,1,0,1,0,1]1,0,1,0,1,1,0,1,0,1,0,1]1,0,1,0,1,@1,0,1,0,1,0,1] 0,1,1,0,1,0,1,1,0,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]1,0,1,0,1,1,0,1,0,1,0,1]1,0,1,0,1,1,0,1,0,1,0,@1] 0,1,1,0,1,0,1,1,0,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,1,0,1,0,1,0,1]1,0,1,0,1,1,0,1,0,1,0,1]1,0,1,0,@1,1,0,1,0,1,0,1] 0,1,1,0,1,0,1,1,0,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]1,0,1,0,1,1,0,1,0,1,0,1]1,0,1,0,1,1,0,1,0,@1,0,1] 0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,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,0,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,0,1,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,1,0,1,0,1,0,1]1,0,1,0,1,1,0,@1,0,1,0,1]★↑ 👀 2つのパターンのずれも、大きい繰り返しになる事が分かりました。 ずれは最大でも2なので、 ysB ≦ Upper_nbit ys ≦ Upper_nbit xs ≦ xsA より、 コラッツパターンと左端を伸ばすパターンのずれが有限値に収まる 事が言えました。 >>228 にミスがありました。 しばしお待ちください。 n=9ビットでは、ずれが無限大になってしまうので、 n=10にします。 *CollatzPatt> collatzPatternA [([1,1,1,1,1,1,1,1,1,1],0),([1,1,1,1,1,1,1,1,0,1],1),([1,1,1,1,1,1,0,0,0,1],1),( [1,1,1,1,1,0,1,0,1,1],0),([1,1,1,0,0,0,0,1,0,1],1),([1,1,0,1,0,0,1,1,1,1],0),([0 ,0,0,1,1,0,1,1,0,1],1),([0,1,0,0,0,1,0,0,0,1],1),([0,0,1,0,1,1,0,0,1,1],0),([1,1 ,1,0,0,1,1,0,0,1],1),([1,1,0,1,1,0,0,1,1,1],0),([0,0,1,0,1,1,0,1,0,1],1),([1,1,1 ,0,0,0,0,0,0,1],1),([1,1,0,1,0,0,0,0,1,1],0),([0,0,0,1,0,0,1,0,0,1],1),([1,0,1,1 ,0,1,1,0,1,1],0),([0,1,0,0,1,0,0,1,0,1],1),([0,0,1,1,1,0,1,1,1,1],0),([1,0,1,0,0 ,1,1,1,0,1],1),([0,0,1,1,0,1,0,0,0,1],1),([1,1,0,0,0,0,1,0,1,1],0),([0,1,0,0,1,1 ,1,0,0,1],1),([0,0,1,1,0,1,0,1,1,1],0),([1,0,0,0,0,0,1,1,0,1],1),([1,0,0,0,1,0,0 ,0,0,1],1),([0,1,0,1,1,0,0,0,1,1],0),([0,0,1,0,1,0,1,0,0,1],1),([1,1,1,1,1,1,1,0 ,1,1],0),([1,1,1,1,1,0,0,1,0,1],1),([1,1,1,1,0,1,1,1,1,1],0),([1,1,0,0,1,1,1,1,0 ,1],1),([0,1,1,0,1,1,0,0,0,1],1),([0,1,0,0,1,0,1,0,1,1],0),([0,1,1,1,1,1,1,0,0,1 ],1),([0,1,1,1,1,1,0,1,1,1],0),([1,1,1,1,0,0,1,1,0,1],1),([1,1,0,1,1,0,0,0,0,1], 1),([1,0,0,1,0,1,0,0,1,1],0),([1,1,1,1,1,0,1,0,0,1],1),([1,1,1,1,0,0,0,1,1,1],0) ,([1,1,0,1,0,1,0,1,0,1],1),([0,0,0,0,0,0,0,0,0,1],1),([1,0,0,0,0,0,0,0,1,1],0),( [1,0,0,0,0,0,1,0,0,1],1),([0,1,0,0,0,1,1,0,1,1],0),([0,1,0,1,0,0,0,1,0,1],1),([0 ,0,0,0,1,0,1,1,1,1],0),([0,0,1,1,1,0,1,1,0,1],1),([1,0,1,0,0,1,0,0,0,1],1),([0,0 ,0,1,1,1,0,0,1,1],0),([0,1,0,1,0,1,1,0,0,1],1),([0,0,0,0,0,1,0,1,1,1],0),([0,0,0 ,1,1,1,0,1,0,1],1),([0,1,0,1,0,0,0,0,0,1],1),([0,0,0,0,1,0,0,0,1,1],0),([0,0,1,1 ,0,0,1,0,0,1],1),([1,1,0,0,1,1,1,0,1,1],0),([0,1,1,0,1,0,0,1,0,1],1),([0,1,0,0,0 ,1,1,1,1,1],0),([0,1,0,1,0,1,1,1,0,1],1),([0,0,0,0,1,1,0,0,0,1],1),([1,0,0,1,0,0 ,1,0,1,1],0),([1,1,1,0,1,1,1,0,0,1],1),([1,1,0,0,1,1,0,1,1,1],0),([0,1,1,0,0,0,1 ,1,0,1],1),([1,0,1,0,1,0,0,0,0,1],1),([0,0,0,0,0,1,0,0,1,1],0),([0,0,0,1,1,0,1,0 ,0,1],1),([1,0,1,0,0,0,0,1,1,1],0),([0,0,1,0,0,1,0,1,0,1],1),([1,1,1,0,1,1,1,1,1 ,1],0),([1,0,0,1,1,1,1,1,0,1],1),([1,1,0,1,1,1,0,0,0,1],1),([1,0,0,1,1,0,1,0,1,1 ],0),([1,1,0,0,0,0,0,1,0,1],1),([1,0,1,0,0,0,1,1,1,1],0),([0,0,1,0,1,0,1,1,0,1], 1),([1,1,1,1,1,0,0,0,0,1],1),([1,1,1,1,0,1,0,0,1,1],0),([1,1,0,0,0,1,1,0,0,1],1) ,([1,0,1,0,1,0,0,1,1,1],0),([0,0,0,0,1,1,0,1,0,1],1),([0,0,1,0,0,0,0,0,0,1],1),( [1,1,1,0,0,0,0,0,1,1],0),([1,0,1,0,0,0,1,0,0,1],1),([0,0,0,1,0,1,1,0,1,1],0),([0 ,1,1,1,0,0,0,1,0,1],1),([0,1,1,0,1,0,1,1,1,1],0),([1,0,0,0,0,1,1,1,0,1],1),([1,0 ,0,1,0,1,0,0,0,1],1),([0,1,1,1,1,1,0,0,1,1],0),([1,1,1,1,0,1,1,0,0,1],1),([1,1,1 ,0,0,1,0,1,1,1],0),([1,0,1,1,1,1,0,1,0,1],1),([0,1,1,1,0,0,0,0,0,1],1),([0,1,1,0 ,1,0,0,0,1,1],0),([1,0,0,0,1,0,1,0,0,1],1),([0,1,0,1,1,1,1,0,1,1],0),([0,0,1,1,1 ,0,0,1,0,1],1),([1,1,0,1,0,1,1,1,1,1],0),([0,0,0,0,1,1,1,1,0,1],1),([0,0,1,0,1,1 ,0,0,0,1],1),([1,1,1,1,0,0,1,0,1,1],0),([1,1,0,1,1,1,1,0,0,1],1),([1,0,0,1,1,1,0 ,1,1,1],0),([1,1,0,1,0,0,1,1,0,1],1),([0,0,0,1,1,0,0,0,0,1],1),([1,0,1,0,0,1,0,0 ,1,1],0),([0,0,1,1,1,0,1,0,0,1],1),([1,1,0,1,0,0,0,1,1,1],0),([0,0,0,1,0,1,0,1,0 ,1],1),([1,0,1,1,1,1,1,1,1,1],0),([0,1,1,1,1,1,1,1,0,1],1),([1,1,1,1,1,1,0,0,0,1 ],1)] *CollatzPatt> collatzPatternB [([0,0,0,0,0,0,0,0,0,1],0),([0,0,0,0,0,0,0,0,1,1],0),([0,0,0,0,0,0,1,0,0,1],1),( [0,0,0,0,0,1,1,0,1,1],0),([0,0,0,1,0,0,0,1,0,1],1),([0,0,1,1,0,0,1,1,1,1],0),([1 ,0,0,1,1,0,1,1,0,1],1),([0,1,0,0,0,1,0,0,0,1],1),([1,1,0,0,1,1,0,0,1,1],0),([0,1 ,1,0,0,1,1,0,0,1],1),([1,0,0,1,1,0,0,1,1,1],0),([0,1,0,0,1,1,0,1,0,1],1),([1,0,1 ,0,0,0,0,0,0,1],1),([1,1,1,0,0,0,0,0,1,1],0),([1,0,1,0,0,0,1,0,0,1],1),([1,1,1,0 ,0,1,1,0,1,1],0),([1,0,1,1,0,0,0,1,0,1],1),([1,1,0,0,1,0,1,1,1,1],0),([0,1,1,1,1 ,0,1,1,0,1],1),([0,1,1,0,0,1,0,0,0,1],1),([1,0,0,1,1,1,0,0,1,1],0),([0,1,0,1,0,1 ,1,0,0,1],1),([1,1,1,1,1,0,0,1,1,1],0),([1,1,1,0,1,1,0,1,0,1],1),([1,0,0,1,0,0,0 ,0,0,1],1),([1,0,1,1,0,0,0,0,1,1],0),([1,0,0,1,0,0,1,0,0,1],1),([1,0,1,1,0,1,1,0 ,1,1],0),([1,0,0,0,1,0,0,1,0,1],1),([1,0,0,1,1,0,1,1,1,1],0),([0,1,0,0,0,1,1,1,0 ,1],1),([1,0,0,1,0,1,0,0,0,1],1),([1,0,1,1,1,1,0,0,1,1],0),([1,0,1,1,0,1,1,0,0,1 ],1),([1,1,0,0,0,1,0,1,1,1],0),([0,1,0,1,1,1,0,1,0,1],1),([1,1,0,1,0,0,0,0,0,1], 1),([0,0,0,0,1,0,0,0,1,1],0),([0,0,1,1,0,0,1,0,0,1],1),([0,1,0,0,1,1,1,0,1,1],0) ,([1,0,1,0,1,0,0,1,0,1],1),([1,1,1,1,1,0,1,1,1,1],0),([1,1,1,0,0,1,1,1,0,1],1),( [1,0,1,1,0,1,0,0,0,1],1),([1,1,0,0,0,0,1,0,1,1],0),([0,1,0,0,1,1,1,0,0,1],1),([1 ,1,0,1,0,1,0,1,1,1],0),([0,0,0,0,0,0,1,1,0,1],1),([0,0,0,0,1,0,0,0,0,1],1),([0,0 ,0,1,1,0,0,0,1,1],0),([0,1,0,0,1,0,1,0,0,1],1),([1,1,0,1,1,1,1,0,1,1],0),([0,0,1 ,1,1,0,0,1,0,1],1),([0,1,0,1,0,1,1,1,1,1],0),([1,1,1,1,0,1,1,1,0,1],1),([1,1,0,0 ,1,1,0,0,0,1],1),([0,0,1,1,0,0,1,0,1,1],0),([1,0,0,1,1,1,1,0,0,1],1),([1,0,1,0,1 ,1,0,1,1,1],0),([1,1,1,0,0,0,1,1,0,1],1),([1,0,1,0,1,0,0,0,0,1],1),([1,1,1,1,1,0 ,0,0,1,1],0),([1,1,1,0,1,0,1,0,0,1],1),([0,1,0,0,0,0,0,1,1,1],0),([1,0,0,0,0,1,0 ,1,0,1],1),([1,0,0,0,1,1,1,1,1,1],0),([0,0,1,0,1,1,1,1,0,1],1),([1,1,1,0,1,1,0,0 ,0,1],1),([0,1,0,0,1,0,1,0,1,1],0),([1,0,1,1,1,1,1,0,0,1],1),([1,1,0,1,1,1,0,1,1 ,1],0),([0,0,1,1,0,0,1,1,0,1],1),([1,0,0,1,1,0,0,0,0,1],1),([1,0,1,0,0,1,0,0,1,1 ],0),([1,1,0,1,1,0,1,0,0,1],1),([0,0,0,1,0,0,0,1,1,1],0),([0,1,1,0,0,1,0,1,0,1], 1),([1,0,0,1,1,1,1,1,1,1],0),([0,1,0,1,1,1,1,1,0,1],1),([1,1,0,1,1,1,0,0,0,1],1) ,([0,0,0,1,1,0,1,0,1,1],0),([0,1,0,0,0,0,0,1,0,1],1),([1,1,0,0,0,0,1,1,1,1],0),( [0,1,0,0,1,0,1,1,0,1],1),([1,0,1,1,1,0,0,0,0,1],1),([1,1,0,1,0,1,0,0,1,1],0),([0 ,0,0,0,0,1,1,0,0,1],1),([0,0,0,0,1,0,0,1,1,1],0),([0,0,1,1,0,1,0,1,0,1],1),([1,0 ,0,0,0,0,0,0,0,1],1),([1,0,0,0,0,0,0,0,1,1],0),([0,0,0,0,0,0,1,0,0,1],1)] collatzPatternAは、第115項が[1,1,1,1,1,1,0,0,0,1]となって、 第3項と一致します。その後は繰り返しになります。 collatzPatternBは、第93項が[0,0,0,0,0,0,1,0,0,1]となって、 第3項と一致します。その後は繰り返しになります。 collatzPatternAとBの第2要素を使って、2つのパターンのずれを比べます。 0ならば繰り上がり無しで、1ならば繰り上がり有りです。 #は、そこから繰り返しになっているという意味です。 *CollatzPatt> map snd collatzPatternA +[0,1,1,#0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,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,0,1,1,0,1,0,1,0,1,1,0,1,0,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,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1] *CollatzPatt> map snd collatzPatternB [0,0,1,#0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0 +,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1 ,0,1,0,1,1,0,1,0,1,1,0,1] 2つのパターンの第2要素を羅列します。繰り返しを並べていきます。 @はずれが1になっている所です。それ以降のはみ出た部分は、次の行にまわしています。 [0,1,1,#0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,@1,0 [0,0,1,#0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,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,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,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,1,0,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,1,0,1, 0,1,1,0,1,0,1,0,1,1,0,1,0,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,0,1,1,0,1,0,1,0,1,1,0,1,0,1,@1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0 #0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,@1,0 0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,@1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1 ,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,@1,0,1,1,0,1,0,1,1,0,1 ,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,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,0,1,1,0,1,0,1,0,1,1,0,1,0,@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,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,@1,0 ,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,0,1,1,0,1,0,1,0,1,1,0,1,0,@1,1,0,1,0 ,0,1,0,1,1,0,1,0 ,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,@1 ,1,0,@1,0 ,0,1,0,@1,1,0,1,0,1,1,0,1] ,1,1,0,1,0,1,0,1, 1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,@1,0 ,1,0,1,0,1,1,0,1]#0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,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,0,1,1,0,1,0,1,0,1,1,0,1,0,1,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,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,@1,0,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,0,1,@1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0 ,0,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,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,@1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1 #0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,@1,0 ,0,1,0,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,0,1,1,0,1,0,1,0,1,@1,0,1,0,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,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,@1 ,0,1,0,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,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,@1,0 #0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,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,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,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,1,0,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,1,0,1, 0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,@1]★にLoopする ,0,1,0,1,1,0,1,0,1,1,0,1]#0,1,0,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,@1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,0 2つのパターンのずれも、大きい繰り返しになる事が分かりました。 ずれは最大でも2なので、 ysB ≦ Upper_nbit ys ≦ Upper_nbit xs ≦ xsA より、 コラッツパターンと左端を伸ばすパターンのずれが有限値に収まる 事が言えました。 xsA、ysB、コラッツパターン値Xs、左端を伸ばすパターン値Ys の大小関係を考えます。 Xs = X0*(3/2)^s*(1+1/3x0)...(1+1/3xs-1) Ys = X0*(3/2)^s です。 コラッツパターンは、下位からの繰り上がりが有ったり無かったりするので、 Xs < xsA * 2^pxs + (2^pxs-1)(下位を1埋め) です。 2^pxsはコラッツパターンと桁をそろえるものです。 px0 = [X0と右端を合わせる] pxs = | pxs-1 +1 [右端の繰り上がり有り] | pxs-1 [右端の繰り上がり無し] 左端を伸ばすパターンは、下位からの繰り上がりが有ったり無かったりするので、 ysB * 2^pys < Ys です。 Ys < Xsは自明なので、まとめると、 ysB * 2^pys < Ys < Xs < xsA * 2^pxs + (2^pxs-1) となります。 2つのシミュレーションA,Bを比べて、ずれが有限値に収まれば、 2つのシミュレーションA,Bにはさまれた Xs,Ysのずれも有限値に収まる、と言えます。 素朴な疑問だけど、3x+1したら綺麗に1→4→2→1に収束するのに 3x-1したら少なくとも3つぐらいのループに分かれてしまう この「+1」の意味って何なんだろうな 奇数を偶数にするためとか そんなことを言っているんじゃないですよね(>_<) >>251 もちろん、偶数にするための+1なんだろうけど 「3x+1」したら綺麗に1個のループ(1→4→2→1)に収束 「3x-1」したら複数のループに収束(収束と言っていいのか?) という風に性質が全く異なる 高々「+1」か「-1」の違いなのにね コラッツ問題の証明には、この辺りの理由の解明が必要だと思う 私なりの考えを書いてみました。数学は素人なので数学の表現は最低クラス だと思いますがこの板の諸兄におかれましては何卒よろしくご査収の上 ご批評賜れば幸いです。 http://koubeichizoku.doujin.so/collatz/collatz.htm >>254 70年間解かれなかった問題に解答しようというんだからかなり難解なものにならざるを得ないけど、 ワイルズがフェルマーの定理に与えた解答にくらべれば100分の1くらいの難易度だと思う >>255 修正おわりました。ご査収、ご批評の程よろしくお願い申し上げます。 m(_ _)m >>250 例えば (7×3+1)÷2=11、(29×3+1)÷2÷2÷2=11 で、7×4+1=29、つまりある奇数を4倍して1を足した奇数は このる奇数と同じ値へと変化します。 奇数xを初項とする漸化式 an+1=an×4+1であらわされる数列の一般項が たまたま、(y×2^n-1)÷3だからです。 コラッツ予想はこの数列の一般項を求める関数の反対写像にあたっているのです。 ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.1 2024/04/28 Walang Kapalit ★ | Donguri System Team 5ちゃんねる