#コラッツ予想を考えてみた
コラッツ予想。
理系なら名前は知っているのではないでしょうか。
数学オタクなら一度は証明を試みたのではないでしょうか?
簡単に考え直したのでそれを忘備録として残しておきます.
##コラッツ予想とは
1937年にローター・コラッツにより提唱された予想です。
また角谷の問題などと呼ばれていたりします.
###主張の内容
関数$f(x)$を以下のように定める
f(x) = \left\{ \begin{array}{ll}
\frac{x}{2} & (x:\text{偶数}) \\
3x+1 & (x:\text{奇数})
\end{array} \right.
このとき, すべての自然数$n$に対して
$$
f^k(n)=1
$$
となる自然数$k$が存在する. ($f^k(n):=f\circ f\circ \cdots \circ f(n)$ ($k$個の$f$からなる合成写像))
まあ、日本語で書くと「どんな自然数$n$でも、偶数なら$2$で割り、奇数なら$3$倍して$1$足すということ繰り返したらいつか$1$になるやろ」
って感じです。
###現在までの進捗
$2^{68}$までの範囲で反例がないことが示されている.
テレンスタオ大先生が「ほとんどすべての$n$で成立する」ことを示しました。
###どの分野の問題に落とし込めるのか
もちろん整数論に落とし込むことが可能です. すると指数型のディオファントス方程式の整数解を求める問題も含みそれだけでえぐいくらい難しい問題であることが想像できます。
ほかにも、グラフ理論に落とすことも可能です。
ただし、そこからのアプローチで示せるのかどうかはいまだにわかりません。
##どのようにして帰納法で考えるのか
まず、帰納法は覚えていますでしょうか?
$k=1$で成立
$k=n$で成立すると仮定
このとき$k=n+1$で成立することが確認できればすなわちすべての自然数で成立する。
といった証明のテクニックの一つですね。
ただテクニックと書きましたが大学数学を学ぶと、帰納法はほぼ自然数の公理。つまり数学の基本原則とだいたい同じであることが分かったりしてワクワクします。
###少し特殊な帰納法
今回は少しだけ違う帰納法で示していきます。
こんなやりかたです。
$k=1$で成立
$k$は$n$以下すべてで成立すると仮定
このとき$k=n+1$で成立することが確認できればすなわちすべての自然数で成立する。
たまに受験数学でも見るテクニックですね。仮定が広くなっているので扱いやすいです。
####なぜこんな帰納法で考えるのか
$n$以下すべてで成立と仮定しているため
ある自然数$t$が存在して
$n+1 > f^t(n+1)$
を示せばよくなるからです。
つまるところ、$=1$となる$k$を探すよりも簡単になるのです。
###とりあえずやってみる.
まず偶数と奇数で考えましょう。
Case1: $n=2k $ のとき
$2k>f(2k)=k$なのですべての偶数で成立.
Case2: $n=2k+1$ のとき
$f(2k+1)=6k+4$, $f(6k+4)=3k+2$
このとき$3k+2$が偶数か奇数かわかりません。
なのでこれ以上先に進めない...
しかし場合分けを考えれば先に進むことができます。
###場合分けのやりかた
この $3k+2$ の $3k$ が奇数か偶数かわからないわけです。
なので次の$2$つに場合分けをしましょう。
$(i)$: $k=2s$ のとき $2k+1=4s+1$
$(ii)$: $k=2s+1$ のとき $2k+1=2(2s+1)+1=4s+3$
つまり, 最初 $2k$, $2k+1$と場合分けしましたが, 最初から
$2k$, $4k+1$, $4k+3$と場合分けしてもよいわけです。
でこれで考えると
$4k+1>f(f(f(4k+1)))=f(f(12k+4))=f(6k+2)=3k+1$となり $4k+1$の形であればコラッツ予想が成立しそうなことが分かりました!!
しかし,
$f(f(f(f(4k+3))))=f(f(f(12k+10)))=f(f(6k+5))=f(18k+16)=9k+8$ となりまた先に進めません。
なのでまた同じように場合分けを行います。
しかしやってみればわかりますが、$8k+3$も$8k+7$も解けません。
なのでそれぞれ場合分けして...
と同じようなことを繰り返し繰り返すわけです。
こんな単純作業...やりたくないですよね?
なのでプログラムでやらせましょう。
###注意点
注意点として次が気になります
$Ak+B$より小さいってどうやって判定するの...?
今までの具体例であれば明らかに小さかったですが, 例えば
$17k+5$ と $16k+1234567890$はどちらが小さいんでしょうか?
この処理を考えないといけませんが, 今回は$k$ の係数が小さければ小さいと判定することにします。
なぜなら上の例だと
$k>1234567885$（移項しただけ）であれば成立するわけで、ある種の上限を与える結果となり、コラッツ予想の解明という目標からずれていません。
上限が決まればその範囲を全検すればよいわけですからね。
##プログラムでの実装
def kora(li,num):#liはAk+BのBを集めたリストで、numはA
ans=[]
for i in range(len(li)):
x=num
y=li[i]
for j in range(10000):
if x%2!=0:
if x<num:
break
elif x==num and y<li[i]:
break
else:
ans.append(li[i])
break
else:
if y%2==0:
x//=2
y//=2
else:
x*=3
y*=3
y+=1
return ans
###プログラムの説明(簡単に)
上の操作を繰り返し行うだけです。
$k$ の係数は必ず$2$の累乗となるので$Ak+B$の$B$だけリストで管理することにします.
###結果
2k+Bの形で帰納法を用いて証明できないBの集合
>>>[1]
4k+Bの形で帰納法を用いて証明できないBの集合
>>>[3]
8k+Bの形で帰納法を用いて証明できないBの集合
>>>[3, 7]
16k+Bの形で帰納法を用いて証明できないBの集合
>>>[7, 11, 15]
32k+Bの形で帰納法を用いて証明できないBの集合
>>>[7, 15, 27, 31]
64k+Bの形で帰納法を用いて証明できないBの集合
>>>[7, 15, 27, 31, 39, 47, 59, 63]
128k+Bの形で帰納法を用いて証明できないBの集合
>>>[27, 31, 39, 47, 63, 71, 79, 91, 95, 103, 111, 123, 127]
256k+Bの形で帰納法を用いて証明できないBの集合
>>>[27, 31, 47, 63, 71, 91, 103, 111, 127, 155, 159, 167, 191, 207, 223, 231, 239, 251, 255]
512k+Bの形で帰納法を用いて証明できないBの集合
>>>[27, 31, 47, 63, 71, 91, 103, 111, 127, 155, 159, 167, 191, 207, 223, 231, 239, 251, 255, 283, 287, 303, 319, 327, 347, 359, 367, 383, 411, 415, 423, 447, 463, 479, 487, 495, 507, 511]#38個あるよ
1024k+Bの形で帰納法を用いて証明できないBの集合
>>>[27, 31, 47, 63, 71, 91, 103, 111, 127, 155, 159, 167, 191, 207, 223, 231, 239, 251, 255, 283, 303, 319, 327, 359, 383, 411, 415, 447, 463, 479, 487, 495, 511, 539, 543, 559, 603, 615, 623, 639, 667, 671, 679, 703, 719, 743, 751, 763, 767, 795, 799, 831, 839, 859, 871, 879, 895, 927, 935, 959, 991, 1007, 1019, 1023]
1048576k+Bの形(2**20)で帰納法を用いて証明できないBの集合
>>>[27, 31, 47, 63, 71, 91, 103, 111, 155, 159, 167, 223, 251, 283,..., 1048319, 1048347, 1048423, 1048559, 1048571, 1048575]#27328個あったよ
###結果を見た気づき
どうやらこの帰納法で証明しようとすると
$2^xk+(2^x-1)$の形は無理そう
だけどほとんどすべての$n$で成立するというのは何となく正しそうなのは分かる。
なぜなら
$1048576k+B$の形は$B$の候補として$2^{20}$通りあるのに証明できないのが$27328$個しかない。
実に約$2.6$%の数しかない。逆に言うと約$97.4$%の数でコラッツ予想は正し「そう」なのだ。(帰納法はどんな$n$でも仮定の下成立する。を示さないとなんにも意味がない。証明として機能しないから注意してください。つまるところ、こんな主張を数学者の前でやったら鼻で笑われます。アマチュアとして楽しむ範囲でのしょぼしょぼ議論です(面白いとは思うんですけどね))
##新たに出た疑問
$27$ がしぶとく残っているが, $27$ と言えばコラッツ予想愛好家の中で愛される数だ。
何かしらの関係があるのだろうか?
また、$Ak+27$の形が証明できるような$A$の最少はどこなのだろうか。
プログラムで調べてみた。プログラムの説明は省略(見てもらえばわかると思う)
###新しいプログラムによる考察
k=int(input())
check_li=[k]
number=2
for i in range(5,1000):
check=kora(check_li,number)
if k in check:
print(str(2**i)+"k+"+str(k)+"は証明できません")
number*=2
else:
print(str(2**i)+"k+"+str(k)+"は証明できます。ちなみにi="+str(i)+"です。")
break
###結果
32k+27は証明できません
64k+27は証明できません
128k+27は証明できません
256k+27は証明できません
...
144115188075855872k+27は証明できません
288230376151711744k+27は証明できません
576460752303423488k+27は証明できます。ちなみにi=59です。
やば。もう少しほかの値でもやってみましょう
$31$のとき
...
72057594037927936k+31は証明できません
144115188075855872k+31は証明できません
288230376151711744k+31は証明できません
576460752303423488k+31は証明できません
1152921504606846976k+31は証明できます。ちなみにi=60です。
$47$ のとき
...
18014398509481984k+47は証明できません
36028797018963968k+47は証明できません
72057594037927936k+47は証明できません
144115188075855872k+47は証明できません
288230376151711744k+47は証明できます。ちなみにi=58です。
$1023$のとき
...
8192k+1023は証明できません
16384k+1023は証明できません
32768k+1023は証明できません
65536k+1023は証明できません
131072k+1023は証明できません
262144k+1023は証明できません
524288k+1023は証明できません
1048576k+1023は証明できません
2097152k+1023は証明できません
4194304k+1023は証明できます。ちなみにi=22です。
なるほど。$2^x-1$は長くなるというわけではなさそうですね。
###簡単な考察
この方法で完全な証明を望むのは無謀だろう。
だけど、面白そう。
また結構残る数として
$27, 31, 47, 63, 71, 91, 103, 111, 155, 159, 167, 223, 251, 283,...$があるがこれらは素数か3の倍数であることが多そうだ。(上に書いた中では例外は$155$のみ)。
これはたまたまではなさそうな気がする。
##まとめ
帰納法を使いましたが今回は証明として機能していませんのでまったく意味がありませんでした。無念。
ただ、新しい問題と出会えた気がします。
コンピュータを用いれば新しい性質や世界が見えきます。
数学の、特に整数の勉強している人ほど、プログラムを勉強するとさらに数学を楽しめると思います。
そしてコラッツ予想はやっぱりむじゅかしい。