コラッツ予想をプログラマーが検証してみた #1 要件を確認する

プログラミング
スポンサーリンク

コラッツ予想は数学の未解決問題の1つであるが、プログラマー視点から検証した結果どうなるのか?
まずは、要件から確認していく。

コラッツ予想とは?

コラッツ予想は、コラッツ問題や3n+1問題などと呼ばれることもある、数学の未解決問題の1つとのことだ。
2021年7月7日に多大な懸賞金がかけられた記事が、PCWatch(https://pc.watch.impress.co.jp/docs/news/yajiuma/1336495.html)に掲載されたことで、私は初めてこのコラッツ予想を知ったのだ。

コラッツ予想

任意の正の整数をnとして入力したとき

  • nが偶数の場合は2で割る。その結果を次のnとする。
  • nが奇数の場合は3倍して1を足す。その結果を次のnとする。

この計算を繰り返した時、すべてのどの正の整数nで開始しても、最終的に1に到達する(正確には1→4→2→1→4→2→1→…と無限ループになる)と言う予想がある。

私のファーストインプレッションは、偶数と奇数の2種類を扱うため、『「2進数」との相性がよさそうだな、ちょっと挑戦してみようかな?』ぐらいの感覚で検証を始めてみた。

要件を確認する

プログラマーたるもの、要件/要求仕様を確認するのは常である。
要件自体は非常に簡単で、用語の定義と各演算式の入力と出力を理解すれば良い。

  1. 任意の正の整数
    0や小数や分数や負の数を含まない、n=1,2,3,4,5,6,… の数である。
  2. 偶数
    2で割ったときの余り(mod)が0であり、n=2,4,6,… の数である。
    nが偶数の時「n÷2」を実施した結果は、1,2,3,…となり奇数の場合偶数場合がある。
  3. 奇数
    2で割ったときの余り(mod)が1であり、n=1,3,5,… の数である。
    nが奇数の時「3n+1」で「3n」を実施した結果は、3,9,15,…と必ず奇数となり、それに「+1」した結果は、4,10,16,…と必ず偶数となる。

フローチャートにしてみる

上記の要件から、フローチャートを作成してみると次となる。

フローチャート1

プログラミング的には、上記で正しいのだが、nが奇数のループ(右側のループ)が連続して発生しても良いよう見えてしまう
nが奇数の時、「3n+1」の結果は必ず偶数なので、下記のように書いた方が人が理解する上では良いかもしれない。

フローチャート2

次回に続く

要件を確認したので、次の投稿では、「2進数」を用いて検証してみる。

関連記事

#2 Excelで作ってみた
#3 さらに角度を変えて検証したら・・・!!!
#4 最後に

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

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

#1 特徴&論理編
#2 からくり編
#3 結論&証明編
コラッツ予想のからくりのまとめ (2021/12/20追記)

コメント

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