第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)

详细分析

这个倒数恒等式直接由两种允许的转移得到。迭代它，可将目标值加一的倒数表示为初值加一的倒数的二进制仿射组合。