We show that only odd, positive $d$ work. Obviously if $d$ is even, then the number will remain even forever, no matter how many $a_k$ we calculate. So we assume $d$ is odd. Note that because $a_0$ is positive, if $d$ is negative then all $a_k$ with $k\geq1$ will be negative or 0. So $d$ is positive, and if $d=1$ then the sequence goes $1, 2, 1$ and $a_2=1$. So we assume now that $d\geq3$. Hence $a_k\geq 1$ for all $k\geq 0$. We show that all $a_k$ are less than $2d$. For if there was some $a_k\geq 2d$, then we choose the least positive such $k$. Then $a_{k-1}=a_k-d\geq d$ and is odd, so $a_{k-2}=2a_{k-1}\geq 2d$. ($a_{k-2}$ cannot equal $a_{k-1}+d$, because then $a_{k-2}$ is even and $a_{k-1}=\frac{a_{k-2}}{2}$ instead.) This contradicts the fact that $a_k$ is the first member of the sequence that is greater than or equal to $2d$ unless $k\leq2$, which is not true because $a_0$ is neither even nor greater than $d$. Now we show that the sequence is reversible; that $a_k$ defines not just $a_{k+1}$ but also $a_{k-1}$. If $a_k\geq d$, then $a_{k-1}$ cannot be $2a_k$ because it would be greater than or equal to $2d$, contradiction. Thus $a_{k-1}=a_k-d$ if $a_k\geq d$. Also, if $a_k<d$, then $a_{k-1}$ cannot be equal to $a_k-d$ because it would be negative. Hence $a_{k-1}=2a_k$. And in either case, the sequence is reversible, if the rule is in place that all members of the sequence are less than $2d$. We know that $a_1$ through $a_{2d}$ are all numbers less than $2d$. Therefore, by the pigeonhole principle, there is some number $a_k$ and some other number $n<2d$ so that $a_k=a_{n+k}$. Thus we can reverse the sequence, so that $a_{k-1}=a_{n+k-1}$, $a_{k-2}=a_{n+k-2}\ldots a_1=a_{n+1}, a_0=a_n=1$. Thus $a_n=1$ for some $n>0$ for all positive odd $d$.

Matematika wrote: We define a sequence $a_n$ so that $a_0=1$ and for all $n \geq 1$ if $a_{n-1}$ is even $a_n=\frac{a_{n-1}}{2}$ else $a_n=a_{n-1}+d$ Find all positive integers $d$ such that there is some poistive integer $i$ for which $a_i=1$ That's, obviously, taken from http://www.artofproblemsolving.com/Forum/viewtopic.php?p=498979&sid=c96f3129a506353e2a9244092d158a3f#p498979

RaleD wrote: That's, obviously, taken from http://www.artofproblemsolving.com/Forum/viewtopic.php?p=498979&sid=c96f3129a506353e2a9244092d158a3f#p498979 Actually, whoever proposed that problem for BMO 2006 must have also taken it from an Italian competition in 2005.

If $d$ is even, then $a_n$ will always be odd; hence, $\{a_n\}$ will be increasing, so $a_n > 1$ for all $n > 1$. If $d$ is odd, define the sequence $\{b_n\}$ so that $b_0 = 1$ and \[b_{n+1} = \begin{cases} \displaystyle \frac{b_n}2 & \textrm { if } b_n \equiv 0 \pmod 2, \\ \frac{b_n + d}{2} & \textrm{ otherwise. } \end{cases} \] $\{b_n\}$ is a subsequence of $\{a_n\}$, since if $a_n = b_m$ and $a_n$ is even, then $a_{n+1} = b_{m+1}$, and if $a_n$ is odd, then $a_{n+2} = b_{m+1}$. Note that $b_{n+1} \equiv \frac{b_n}{2} \pmod{d}$, so $b_n \equiv 2^{-n} \pmod{d}$. Taking $n$ to be the order of 2 modulo $d$ yields $b_n \equiv 1 \pmod{d}$. Furthermore, it is clear by induction that $b_n \leq d$ for all positive $n$, so we have $b_n = 1$.

We show that only odd, positive d work. Obviously if d is even, then the number will remain even forever, no matter how many $a_k$ we calculate. 1) We can prove easily that $a_n \leq 2d$ : We'll prove by induction on n that $a_n \leq d$ when $a_n$ is odd and $a_n \leq 2d$ when $a_n$ is even. For n=1, it's trivial. Suppose it's true for n, now for n+1 : - If $a_{n+1}$ is odd : * If $a_n$ is also odd, then $a_{n+1} = a_n + d = even$, and this is a contradiction. * So $a_n$ is even, and hence : $a_{n+1} = \frac{a_n}{2} \leq d$ - If $a_{n+1}$ is even : We either have : $a_{n+1} = a_n + d$ or $a_{n+1} = \frac{a_n}{2}$ and in both cases it's clear that $a_{n+1} \leq 2d$ 2) Suppose that the set $ \{n\in \mathbb{N}, n>0 / \exists k > n : a_n = a_k \}$ is not empty and define n to be its minimal element. We either have ($a_n = \frac{a_{n-1}}{2}$ and $a_k = \frac{a_{k-1}}{2}$) or ($a_n = a_{n-1}+d$ and $a_k = a_{k-1}+d$) or ($a_n = \frac{a_{n-1}}{2}$ and $a_k = a_{k-1}+d$) or ($a_n = a_{n-1}+d$ and $a_k = \frac{a_{k-1}}{2}$) The first two cases contradict the minimality of n, so let's just consider the third one (the third and the last are symmetric) : We have : $a_n = \frac{a_{n-1}}{2} \leq d$ and $a_k = a_{k-1}+d > d$, contradiction. The sequence $(a_n)_{n>0}$ is bounded by 2d and have different terms, so there will be a k such that $a_k=2$ and that will give $a_{k+1}=1$, which finishes the proof.

It is agreed that $d$ must be odd (otherwise $a_{n+1} = a_n + d$ forever). Now, by simple induction, $a_n \leq 2d$, since if $a_n$ is even then $a_{n+1} = a_n/2 \leq d$, while if $a_n$ is odd, it must be at most $d$, and then $a_{n+1} = a_n + d \leq 2d$ (this is because if $a_n > d$, and if it was obtained through $a_n = a_{n-1} + d$, then it should have been even, while if it was obtained through $a_n = a_{n-1}/2$, then $a_{n-1} > 2d$, in contradiction with the induction hypothesis). Once this established, connect $a_n$ with $a_{n+1}$ by an arrow, in the finite digraph having as vertices the values of the terms of the sequence $(a_n)$. Then the path $a_1a_2\ldots a_k\ldots$ must meet again a first time a vertex from the path, i.e. for some $n > \ell$ we will have $a_{n+1} = a_{\ell}$. Assume $\ell > 1$; since if ${a_\ell} \leq d$ the only way it was obtainable was via $a_{\ell} = a_{\ell - 1}/2$, while if ${a_\ell} > d$ the only way it was obtainable was via $a_{\ell} = a_{\ell - 1} + d$, it means $a_n = a_{\ell-1}$, absurd. Therefore $\ell=1$, and the graph is a cycle.