簡易版コラッツ予想

記事の内容

１．コラッツ予想の証明（賞金がかかって話題になったやつ）に挑戦したいのですが、超難しいので、その足掛かりとして、「偶数なら２で割る、奇数なら１を足す」という簡易版を証明してみます。たぶんできました。

動機

コラッツ予想は、奇数だった時に「３倍して１を足す」操作が複雑で問題を難しくしているので、この操作をまず「２ｎー１倍して１を足す」操作という風に一般化しておいて、いちばん直感的に簡単そうな「１倍して１を足す」（＝ただ１を足すだけ）という簡易版コラッツ予想を証明することができないか、と考えました。

実際に適当な数でこれをやってみると、簡単に成立しそうです。直感的にも成立しそうです。

本記事では、筋道を立ててそれを証明しています。本来のコラッツ予想に対するアプローチの仕方を考えるための手掛かりになるのではと考えました。

簡易版コラッツ予想

簡易版コラッツ予想は、以下のような内容になります。

・偶数なら２で割る、奇数なら１を足す（＝操作）
・この操作を繰り返していると、どの正の整数からはじめても、必ず１になる

「ある操作を続けると、すべての正の整数が１になる」

ということは、１に対してこれとは「逆の操作」を繰り返していけば、すべての正の整数をあらわすことができる、という事です。

これを証明してみます。

逆の操作

操作１．２倍する
操作２．ー１する

このとき、２倍する操作は何回も連続してできるけれど、ー１する操作は連続してできない（操作するたびに奇数と偶数が変わってしまうため）という特性があります。

このため、この操作を任意の回数繰り返して出てくる数は定量化できて、

S(n) = S(n-1)-N(n)　ただし　S(n)＞N(n)≧1（n、S(0)は任意の数）　とおくと
2^(S(n))-2^(S(n-1))-...-2^(S(1)) ...①
2^(S(n))-2^(S(n-1))-...-2^(S(1))-1 ...②

とあらわせます。

これがつまり、簡易コラッツ予想の逆操作から出てくるすべての数ということになります。

直感的に、①が偶数、②がそれにー１した奇数となるのは明白なので、「①が全ての偶数をあらわせる」ことを証明すれば、簡易コラッツ予想は攻略できそうです。

以下は、その証明をやってみます。

Ｓ(n)=aと置いて、①の最大値と最小値を見てみます。

操作の回数は、条件内なら自由にコントロールできるので、
最大値は、マイナスの項目をぜんぶとっぱらって

①(最大値)=2^a

最小値は、マイナスの項目が最大になるように

①(最小値)=2^a -2^(a-1) -2^(a-2) -2^(a-3)...-2^1 ...③
=2^a - Σ(2^k,k=1,a-1)
=2^a-(2^a-2)/(2-1)
=2

となります。

③を見ると、①は最大値2^a、最小値2、その間の数は、2^nを足し合わせて構成される、ということが分かります。

より具体的には、最小値を出すために目一杯つけたマイナスの項目を、自由な組み合わせで省いてゆけばいいので、2,4,8,16,32...の自由な組み合わせを足し合わせたもので構成されている、という事になります。

これは２進数コードの要領で、任意の偶数にすることが可能です。

たとえば、2^nの自由な組み合わせで2^nまでの偶数2^n/2個をあらわすことができると仮定します。すると、次の2^(n+1)までの偶数も2^n/2個あり、2^nと足し合わせることでちょうどすべての数を表すことができるため、ひとつの仮定を証明できればすべてのnについて同じことが言えます。

（一例：16までの偶数は2,4,8の組み合わせで2, 4, 6(2+4), 8, 10(8+2), 12(8+4), 14(8+2+4)と表され、16の次の32までの偶数は16と前述の数列を足し合わせれば18から30まで表されます。以降の偶数も同様に表すことができます）

また、2^aは任意の大きさにすることができるので、以上の事から①はすべての偶数になります。

よって、簡易コラッツ予想は正しいということになります。

（簡易コラッツ予想の証明おわり。）

本来のコラッツ予想の証明は、もうちょっとかかりそうです。