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 Ａ
- 0b0101 → Ａ
- 0b0110 → 0b0011 ⇒ Ａ
- 0b1001 ⇒ 0b0001 1100 → 0b0111 ⇒ 0b0001 0110 → 0b1011 ⇒ 0b0010 0010 → 0b0001 0001 ⇒ 0b0011 0100 → 0b1101 ⇒ 0b0010 1000 → 0b0101 ⇒ Ａ
- 0b1101 ⇒0b0010 1000 → 0b0101⇒ Ａ
- 0b1111 ⇒ 0b0010 1110 → 0b0001 0111 ⇒ 0b0100 0110 → 0b0010 0011 ⇒ 0b0110 1010 → 0b0011 0101 ⇒ 0b1010 0000 → 0b0101 ⇒ Ａ
0b0001 = 0b0010 = 0b0100 = 0b1000
0b0011 = 0b0110 = 0b1100 全消しアリ
0b0101 = 0b1010 全消しアリ
0b0111 = 0b1110 全消しアリ
0b1001 全消しアリ
0b1011 全消しアリ
0b1101 全消しアリ
0b1111 全消しアリダイヤキュート
*1:数学に詳しい人助けて欲しいけど、難しいこと言われてもわからない可能性大
