コラッツ予想のからくりのまとめ

アルゴリズム
スポンサーリンク
スポンサーリンク

説明不足覚悟で”とても簡単”に言うと次となる。

n/2が2進数では右に1ビットシフトとなる。
3n+1を無限に繰り返すと2のべき乗に収束する。
この2つの組み合わせで結果的にn=1に到達する。

簡単に言うと

日本語版

上記は画像なので同じ文を記述して置く。

コラッツ予想とは、
上記の式に対して
すべての正の整数のどれかのnで開始し
結果を次のf(n)の入力として繰り返しても、
最終的に1に到達する
(正確には1→4→2→1→…と無限ループになる)
と言う予想です。
“2”より”3″が大きいのに、
増加し続けずに減少して”1″に到達してしまう。
このように矛盾した結果にたどり着くのは、何故なのか?

簡単に言うと
偶数(2で割った余り:modが0)時のn÷2(n/2)が
2進数では”右に1ビットシフト“であり、
最下位ビットの”0″を切り捨てて行くが、
数値の要素である“1”を含むビットパターンは変わらない

奇数(2で割った余り:modが1)時の3n+1の”3n”は
nのすべての桁を等しく3倍するが、
“+1″は下位の桁にのみ作用し、
上位の桁より下位の桁が速く増加する。
nは奇数なので3倍しても奇数となり
それに”+1″すると必ず偶数となるため、
nの下位の桁に2のべき乗を含む(2の0乗=1は奇数なので除外)。
このため、3n+1を無限に繰り返すと
2のべき乗に収束
する。
2のべき乗は、2進数で見ると
“1”が立っているビットが1つのみで、
下位の桁には”0″が続く

この2つの組み合わせで結果的にn=1に到達する
n/2でビットパターンが変わらないことにより、
3n+1の無限に繰り返しが成り立ちます。

その後も1→4→2→1→…と無限に2のべき乗を繰り返すため、
無限に存在するすべての正の整数がn=1に到達することを
表しています。

詳細は、下記の「関連投稿」を参照ください。

英語版(2022-02-26追記)

The Collatz Karakuri(Mechanism)

If n/2 is a binary number, it shifts 1 bit to the right.
Repeating 3n+1 infinitely converges to a power of 2.
As a result, n=1 is reached by these combinations.

#CollatzKarakuri #CollatzProblem #CollatzConjecture #Collatz #コラッツ予想のからくり

The Japanese version is the original.
It’s a slightly modified machine translation, so there may be some weird parts.
In that case, please advise “this kind of expression is better”.

Put simply.
n÷2 (n / 2) when even (remainder divided by 2: mod is 0) In binary, it is ” 1 bit shift to the right “, The least significant bit ” 0 ” is truncated, The bit pattern containing the numerical element ” 1 ” does not change.

“3n” of when odd (remainder divided by 2: mod is 1) triples all digits of n equally, but “+1” acts only on the lower digits, increasing the lower digits faster than the upper digits
Since n is an odd number, it will be an odd number even if it is multiplied by 3, and if it is “+1”, it will always be an even number.
Even numbers include a power of 2 in the lower digits (excluded because 2 to the 0th power = 1 is an odd number).
Therefore, if 3n + 1 is repeated infinitely, it converges to a power of 2.
The power of 2 has only one bit in which “1” stands when viewed in binary.
The lower digits are followed by “0”.

As a result, n = 1 is reached by these combinations.
By not changing the bit pattern at n / 2,
Infinite repetition of 3n + 1 holds.

After that, it repeats 1 → 4 → 2 → 1 → … infinitely to a power of 2, which means that all infinitely existing positive integers reach n = 1.

特徴&論理&からくり&結論のまとめ

特徴

コラッツ予想の式から以下の特徴が抽出できる。

  • [特徴1]偶数と奇数の2種類の数値を扱うこと
  • [特徴2]n/2が2進数では”右に1ビットシフト”であること
  • [特徴3]到達点の”1″、および、”1→4→2→1→…”の無限ループの各数値が、2のべき乗(1=20, 2=21, 4=22)であること

これらの特徴からコラッツ予想の式は”2進数”との親和性が高いことが分かる。

詳細は、徹底解説 コラッツ予想のからくり#1 特徴&論理編 を参照してください。(2022/05/13追記)

論理

コラッツ予想の式から以下の論理が導き出せる

  • [論理A]nを2進数で見たとき、最下位ビット(20の桁)が”0″であれば偶数、”1″であれば奇数である
  • [論理B]”n/2″は2進数では”右に1ビットシフト”であり、数値の要素となる”1″を含んだビットパターンは変わらない
  • [論理C]”3n+1″の結果は必ず偶数となり、下位の桁のグループに2のべき乗を含む
  • [論理D]”3n+1″の”+1″により、上位の桁のグループより下位の桁のグループの方が速く増加する
  • [論理E]”3n+1″を無限に繰り返すと、nそのものが2のべき乗(“1″が立っているビットが1つ)に収束する
    (2022/02/23追記:「論理E:要証明」となっていましたが#3 結論&証明編にて証明済みのため「要証明」部分を削除しました)

詳細は、徹底解説 コラッツ予想のからくり#1 特徴&論理編 を参照してください。(2022/05/13追記)

からくり

コラッツ数列に、[論理A~E]を当てはめ、次のからくりが得られた。

  • [からくり1]nが偶数になる毎に発生する”右に1ビットシフト”により、数値の基準点となる最下位ビット(20の桁)がSTEP:0(開始時)のn の最下位ビットから左にずれる
  • [からくり2]数値の基準点が左にずれるため、”+1″する位置も同様にずれる
  • [からくり3]10進数で見た時はn=”1″に到達した時点を”STEP数”としているが、2進数で見た時は2のべき乗となったときを到達点と判断でき”STEP数”に違いがある
  • [からくり4]”+1″の数値の基準点が開始時のときより左にずれているため、比較的少ないSTEP数で”1″に到達する。

詳細は、徹底解説 コラッツ予想のからくり#2 からくり編 を参照してください。(2022/05/13追記)

結論

[からくり1]と[からくり2]の対策により以下の結論を得た。

  • [結論1] [論理B]により「n/2が”右に1ビットシフト”である」こと、および「数値の要素となる”1″を含んだビットパターンは変わらない」こと、[論理E]の「nそのものが2のべき乗に収束する」ことから、無限に存在するすべての正の整数は”1″に到達する。
  • [結論2] “1→4→2→1→…”の無限ループは、偶数時の”n/2″により同じ値に見えるだけで、その実体は無限ループしているわけではなく、また他の値で無限ループすることも無い。

詳細は、徹底解説 コラッツ予想のからくり#3 結論&証明編 を参照してください。(2022/05/13追記)

連絡先

一連の投稿に対して、賛否のご意見、投稿内容の間違い、ご要望などありましたら、ハッシュタグ「#コラッツ予想のからくり #プログラミングの深淵を求めて」を付けてツイートしてください。

または、Twitter @dratech2020 の投稿に返信ください。

関連投稿

ツール:Excel版(2021/12/25追記)

ツール:ブラウザ(BigInt)版(2021/12/25追記)

ブラウザ(BigInt)版

徹底解説 コラッツ予想のからくり

これらの投稿は下記の「コラッツ予想をプログラマーが検証してみた」の要点のみ抽出し再構築、説明不足だった部分を加筆してまとめたものです。

#1 特徴&論理編
#2 からくり編
#3 結論&証明編

コラッツ予想をプログラマーが検証してみた

#1 要件を確認する
#2 Excelで作ってみた
#3 さらに角度を変えて検証したら・・・!!!
#4 最後に

コラッツ予想のからくり Extra Stage

#1 「1→4→2→1→…のループ」がすべてを飲み込む!? (2022-05-13追記)
#2 コラッツ数列は偶数奇数以外に仕分けできる!? (2022-06-25追記)

コメント

タイトルとURLをコピーしました