Computer Transformation(3) - カメヲラボ

前回作った漸化式を使って、k=1,2,3...の場合にどのような式で表すことが出来るか調べてみる。

k=1のとき
$a_2=2^0-a_1=2^0$

k=2のとき
$a_3=2^1-a_2=2^1-2^0$

k=3のとき
$a_4=2^2-a_3=2^2-2^1+2^0$

k=4,5,6のとき
$a_5=2^3-2^2+2^1-2^0\\a_6=2^4-2^3+2^2-2^1+2^0\\a_7=2^5-2^4+2^3-2^2+2^1-2^0$

これで一般項を求めることが出来そうだ。
注意する点は、kが偶数のときと奇数のときの正負だけ。

(Ⅰ)k=2i+1のとき

$a_i=\frac{2(2^{2i}-1)}{2^2-1}-\frac{1(2^{2i}-1)}{2^2-1}=\frac{2^{2i}-1}{3}$

なので、

$a_k=\frac{2^{k-1}-1}{3}$

(Ⅱ)k=2iのとき

$a_i=\frac{1(2^{2i}-1)}{2^2-1}-\frac{2(2^{2(i-1)}-1)}{2^2-1}=\frac{2^{2(i-1)}+1}{3}$

から、

$a_k=\frac{2^{k-1}+1}{3}$

となることがわかる。2式を比べてみると、1を足すか引くかの差しかない。これは最短コードを目指すための大きなヒントになるので覚えておいてほしい。

さて、これらの式はわざわざ分ける必要が無く、2/3=0.6666...(<1)ということを考えれば、(Ⅱ)の式を適用し小数点以下を切り捨てることによって奇数項も求めることが出来る。つまり、入力nに対する出力は、

$floor(\frac{2^{n-1}+1}{3})$

で求められるということになる。