スレッド

会話

揺らぐ藻【嘘カウンター1】
@yuragumo
コラッツ予想、もう説明資料書くの面倒になったからゲーム作るのに戻ろう。 やり方書いとくから、これ見て証明して賞金１億円＋５００ドル貰った人、自分だけのものにしてくれても良いし、気遣ってくれるなら何百万円かくれても良いしで、もう後はこういう作業好きな人にお願いしますわ！
午前1:53 · 2021年9月19日Twitter Web App
1
件のリツイート
揺らぐ藻【嘘カウンター1】
@yuragumo
返信先:
@yuragumo
さん
前提：コラッツ予想（自然数1以上に対して、偶数の時は2で割る、奇数の時は3倍して1を足すを繰り返すと、必ず最後は1→4→2のループになる） 結論として、これは「真」である。 これを証明するためには、組み合わせが有限である事を証明すればいい。
1
1
揺らぐ藻【嘘カウンター1】
@yuragumo
まずこの証明の基礎となる考え方。 自然数をプログラマーおなじみのビットセット（2進数）に変換して3桁ずつ区切ってこのセットの変化を持って処理する。 この後、組み合わせ表的な使い方するので、そっちベースなら8進数でも可。 （例：123（10進数）→1「001」7「111」3「011」）
1
揺らぐ藻【嘘カウンター1】
@yuragumo
これは面倒だけど作ってた表。 これは1桁目は必ずこの数値の組み合わせ内になり、繰り上がりが発生する場合は2桁目以降にその値が持っていかれる形になる。
画像
1
揺らぐ藻【嘘カウンター1】
@yuragumo
ただ、2で割るのは所謂ビットセットの右1シフトと同義なので、偶数に関しては別枠扱いとして、1桁目も2桁目以降と共通で使える表に当てはめても良い。 これは2桁目以降で使う表。
画像
1
揺らぐ藻【嘘カウンター1】
@yuragumo
さて、ここまで書いて察しの良い方は気づいてくれたかもしれないけど、コラッツ予想の奇数。 「3倍した値」に「1を足す」という性質。 これ、そのまま2桁目以降において 「3倍した値」に「この表の繰り上がり数（n+1桁目と記載した部分）を足す」 って形で全く同じに使えるのよね。
1
揺らぐ藻【嘘カウンター1】
@yuragumo
今回の証明においては、奇数が出た時にこの繰り上がりが行われる部分で2進数で見た時の最上位ビット（桁）が繰り上がる回数が、偶数で桁が繰り下がる回数を超えなければ良いので、どういうパターンで組み合わせが遷移するのかをまとめ、前後の桁合わせて3桁分を繋げば有限であることの証明が出来る。
1
揺らぐ藻【嘘カウンター1】
@yuragumo
なので、要素としては「n+1桁目（8パターン）」「n桁目（8パターン）」「繰り上がり数（3パターン）もしくはn-1桁目（8パターン）」を総当りすれば、それで答えが出る。 繰り上がり数は、先述の表でも分かる通り0、1、2のどれかになり、3以上の値は出てこない（n-1桁目が24以上にならない）から。
1
揺らぐ藻【嘘カウンター1】
@yuragumo
ちなみに1桁目の繰り上がり数には常に「1」を当てる。 要はこのコラッツ予想って、8進数とか2進数でのコンピューターライクな考え方なら割と簡単に解けて、10進数ベースで考えるから却ってややこしくなっちゃう話なのよね。
1
揺らぐ藻【嘘カウンター1】
@yuragumo
ちなみに、別解。 備考として最初の2桁は例外視して完全にアルゴリズム的な使い方をしてもいい。 最初の例だと（123（10進数）→3「011」7「110」と「11」）みたいな。 この2桁＋1桁の繰り上がりないし、1桁＋2桁先の加算については、完全に有限オートマトン的な感じにしちゃっても影響しない。
1
揺らぐ藻【嘘カウンター1】
@yuragumo
この辺りをこうなりますよ的な資料込みで書こうと思うと量が凄く多くなってとっても面倒だし、当てはまりそうな数学の定理はほぼ知らないので、なんか良いように当てはめたら数学的な証明って形で出来るんじゃないでしょうか。 以上、論理的説明終了（QED）。

Twitterを使ってみよう

今すぐ登録して、タイムラインをカスタマイズしましょう。
Appleのアカウントで登録
電話番号またはメールアドレスで登録
By signing up, you agree to the Terms of Service and Privacy Policy, including Cookie Use.

トレンド

いまどうしてる？

COVID-19
ライブ
新型コロナウイルス感染予防 マスクの効果について
音楽 · トレンド
NiziU
32,578件のツイート
日本のトレンド
アニリベ
6,040件のツイート
新R25編集部
昨日
学校だと“手を動かす”と褒めてくれるけど... みんなが中高生に伝えたい「学校では教えてくれない大切なこと」
ケータイ Watch
2021年9月17日
「iPhone 13」シリーズ、予約受付スタート！　ドコモ/au/ソフトバンク/楽天の価格出揃う
さらに表示