Pongeponge

読者です 読者をやめる 読者になる 読者になる

3n+1問題もしくはコラッツ問題

ポケモンカード BW6【コラッタ】【C】 PMBW6-F046-C ≪フリーズボルト≫

3n+1問題(コラッツ問題)というのがあるらしい。

子供でも分かり易い問題で、
 ある整数n(n>1)が偶数の時はn/2、奇数の時は3n+1して何度も計算していく。
どんなnを選んでも、計算していくと最終的に1になるんだろうか?
 …という問題。


例えば、n = 5とする。

5は奇数なので、3×5+1 = 16
16は偶数なので、16/2 = 8
8は偶数なので、8/2 = 4
4は偶数なので、4/2 = 2
2は偶数なので、2/2 = 1 終了。

もう一つ、例として14を選んでみる。

計算書くのめんどくさいので、「→」はn/2、「⇒」は3n+1を計算してる。
\(14 → 7 ⇒ 22 → 11 ⇒ 34 → 17 ⇒ 52 → 26\)
\(→ 13 ⇒ 20 → 10 → 5 ⇒ 16 → 8 → 4 → 2 → 1\)

なんでこんな事になるんだろうと、しばらく考えてた。

思いついたのは、

  • 奇数になると、次は必ず偶数
    • 3n+1は、つまり奇数(3)×奇数(n)=奇数(3n)をして、出た奇数(3n)に1を足すから偶数になる
  • 素因数分解役に立たないpoi!
  • nが\(2^{m}\)になると、あとはずっと\(\frac{n}{2}\)つまり\(n\times2^{-1}\)を計算するハメになり1になる


 それでモニョモニョ考えた挙句、2進数表記すれば分かり易いんじゃないかと思いつく。
理由としては、偶数の時に1/2するっていうのは右1シフトと同じだから。
例としてn=5を使う。
0b0000 0101 (5)
0b0001 0000 (⇒16)
0b0000 1000 (→8)
0b0000 0100 (→4)
0b0000 0010 (→2)
0b0000 0001 (→1)


 見ればわかるとおり、最下位ビットが0であれば右1シフトする。
さらに3n+1の計算結果は偶数になるので、最下位ビットが必ず0になり、次に桁を減らせる。

例えば5(0b0101)のような

交互に0と1が並ぶ奇数は3n+1すると0がずらっと並ぶ。
だからそういう奇数は1になる。

うーん

どんな数であろうと、最下位4ビットが0011~1111の間にあるなら、???1 0000になって4ビット全消しがおきる。
そうするとテトリスみたいに上の5ビット目から8ビット目が降ってきて、その新しい最下位4ビットが0011~1111の間にあるならまた全消し…
そのくりかえしが起きたうえで、最終的に0001 0000になって全消しの後1になるんじゃなかろうか。
証明の仕方は、どう書いていいかよくわからんけど。

箇条書きで書くと*1

  • 任意の数n(n>1の整数)を選ぶ
  • nを2進数化する
  • 最下位4bitが0011~1111の間である場合、計算していくと必ず10000になる…(1)
  • 最下位4bitが右4シフトで全消しになって花火が上がる
  • 5bitめから8bitめが新しい最下位4ビットになる…(2)
  • (1)から(2)を繰り返す
  • 桁が減っていって0011~1111の4bitだけになる
  • (1)から、0011~1111は計算していくと10000になる
  • 右4シフトで0001だけ残る
  • よって、任意の数n(n>1の整数)は計算していくと1になる


こんな感じかなぁ?
以下メモ

  • 0b0010 → 0b0001
  • 0b0011 ⇒ 0b1010 → 0b0101 ⇒ 0b0001 0000 → 0b0001 A
  • 0b0101 → A
  • 0b0110 → 0b0011 ⇒ A
  • 0b1001 ⇒ 0b0001 1100 → 0b0111 ⇒ 0b0001 0110 → 0b1011 ⇒ 0b0010 0010 → 0b0001 0001 ⇒ 0b0011 0100 → 0b1101 ⇒ 0b0010 1000 → 0b0101 ⇒ A
  • 0b1101 ⇒0b0010 1000 → 0b0101⇒ A
  • 0b1111 ⇒ 0b0010 1110 → 0b0001 0111 ⇒ 0b0100 0110 → 0b0010 0011 ⇒ 0b0110 1010 → 0b0011 0101 ⇒ 0b1010 0000 → 0b0101 ⇒ A


0b0001 = 0b0010 = 0b0100 = 0b1000
0b0011 = 0b0110 = 0b1100 全消しアリ
0b0101 = 0b1010 全消しアリ
0b0111 = 0b1110 全消しアリ
0b1001 全消しアリ
0b1011 全消しアリ
0b1101 全消しアリ
0b1111 全消しアリダイヤキュート

*1:数学に詳しい人助けて欲しいけど、難しいこと言われてもわからない可能性大