第3問

実数列

a_0,a_1,\ldots

が良い列であるとは、(i)

a_0

が正整数、(ii) 任意の非負整数

i

で

a_{i+1}=2a_i+1

または

a_{i+1}=\frac{a_i}{a_i+2}

、(iii) ある正整数

k

で

a_k=2014

となることをいう。

a_n=2014

となる良い列が存在するような最小の正整数

n

を求めよ。

ステップ 1/4: 二つの操作を線形化する

\frac1{a_{i+1}+1}=\frac1{2(a_i+1)}\quad\text{or}\quad\frac1{a_{i+1}+1}=\frac12\left(\frac1{a_i+1}+1\right)

詳しい解説

この逆数の恒等式は二つの遷移から直接得られる。反復すれば、目標値に1を足した逆数は、初期値に1を足した逆数の二進的なアフィン結合で表される。