Shu wrote: An infinite sequence $x_1,x_2,\ldots$ of positive integers satisfies \[ x_{n+2}=\gcd(x_{n+1},x_n)+2006 \] for each positive integer $n$. Does there exist such a sequence which contains exactly $10^{2006}$ distinct numbers? I think "yes" let $ y_0=2, y_1=4, y_{n+2}=(y_{n+1}-1)(y_n-1) $ Then $ gcd(y_{k+2}-1, y_{k}-1)=gcd(y_{k+1}-1, y_{k}-1)=1 $ Let $ x_k= 2006 y_{t-k} $ for $ k=1, 2, \cdots , t $ while $ t=10^{2006} $ It's easy to check that this sequence satisfies $ x_{n+2}=\gcd(x_{n+1},x_n)+2006 $ Since $ y_0=2, y_1=4, y_2 =3 < y_3 < y_4 < \cdots $ , $ x_1, x_2, \cdots , x_t $ are different numbers $ x_{t-2}=3*2006, x_{t-1}=4*2006, x_{t}=2*2006 $ $ \therefore x_{t+3k}=x_{t+3k+2}=2*2006 $ and $ x_{t+3k+1}= 3*2006 $ for all $ k \ge 0 $ QED