Collatz-ish Olympiad Problem The following is an Olympiad Competition question, so I expect it to have a pretty solution:

For a positive integer $d$, define the sequence:
  \begin{align}
a_0 &= 1\\
a_n &= 
  \begin{cases}
    \frac{a_{n-1}}{2}&\quad\text{if }a_{n-1}\text{ is even}, \\
    a_{n-1}+d        &\quad\text{if }a_{n-1}\text{ is odd.}
  \end{cases}
\end{align}
  Find all values of $d$ such that $a_n=1$ for some $n>0$.

It is obvious that $d$ must be odd, or else the sequence is monotone increasing. Also, I have numerically observed that all odd values of $d$ seem to work. Can anyone provide a hint as to how to even begin to prove this? Thank you!
 A: Here is an outline of an argument. Our guess was that the sequence goes back to $1$ for any $d = 2m-1$.
First, it seems preferable to work with the sequence
$$b_0 = 1, \quad b_n = \begin{cases} \dfrac{b_{n-1}}2 & (b_{n-1}\text{ even}) \\ \frac{b_{n-1}+d}2 & (b_{n-1} \text{ odd})\end{cases}$$
instead of $a_n$ (the statement to be proven remains the same).
Hint: Show that it is enough to show $b_n\equiv 1 \pmod d$ for some $n$. What does the sequence $b_n$ look like mod $d$?

I have included a more detailed outline below (but I fear it is giving away way too much!)

 Claim 1: We have $0<b_n<d$ for all $n$.

-

 This allows us to work mod $d$ from now on, i.e. we have $b_n = 1$ if and only if $b_n\equiv 1 \pmod d$.

-

 Claim 2: $\frac12 \equiv m \pmod d$, where $d=2m-1$ as above.

-

 Now notice that the sequence is really simple when considered $\pmod d$! Use this to show

-

 Claim 3: $b_n \equiv m^n \pmod d$

-

 Claim 3 implies that $b_k \equiv 1 \pmod d$ for some $k$ (why?), so by Claim 1 it follows that $b_k=1$ for this $k$. $\square$

A: It is true that you return to $1$ for all odd $d$, and the power of $2$ that you get to for the return is the next power of $2$ above $d$.  
All odd numbers in the series are less than $d$, which means it must cycle.  If $a_n$ is odd and less than $d$, $a_{n+1}$ is less than $2d$ and even, so the next odd is again less than $d$.
To have a cycle that does not include $1$ you must have a number that can be reached from two different numbers-one to enter the cycle and one to continue it.  But this is impossible-odd numbers have to be reached by division by $2$, even numbers greater than $d$ have to be reached by addition, and even numbers less than $d$ have to be reached by division.
A: The question has already an "accepted" answer - but the following scheme may be useful for some later reader anyway.
The iterative dividing and adding can be expressed as a whole operation.
We formulate one transformation as $$ a_{k+1}={a_k+d \over 2^A }$$ and work on odd $a_k$ only. The value for A is determined by the requirement, that it is the highest A such that the result of the transformation is an odd integer.
The second transformation is then $$ a_{k+2}={{a_k+d \over 2^A }+d \over 2^B} = {a_k \over 2^{A+B} } + d \cdot ({1 \over 2^{A+B} } + {1 \over 2^B} )$$ and so on.     
Let the h subsequent exponents of such transformations $a_0 \to a_h = 1$ be denoted as $A,B,C,\ldots,G,H$ and their sum as $S$. Then the full transformation can be written as
$$ 1 (=a_h) = {a_0 \over 2^S} + d \cdot {(1+2^A + 2^{A+B} + \ldots + 2^{A+B+\ldots + G})\over 2^S} $$    and we must have an integer solution for
$$ 2^S = a_0 + d \cdot (1+2^A + 2^{A+B} + \ldots + 2^{A+B+\ldots +G})= a_0 + d \cdot x $$
where S is to be found (if there is a solution in $A,B,C,\ldots,H$ at all!).        
Thus we solve for S such that 
$ 2^S = a_0 \pmod d$ which must in general be done by searching (see "discrete-logarithm-problem").
Now here seems to be the critical problem of the original question: we need to know such combinations of $d$ and $a_0$ that this equation has a solution at all. Possibly this is also meant to be the core problem in your homework-assignment, so I won't proceed here ( #1  see below) 
If in fact there is a solution for some S then we compute
$$ x = { 2^S - a_0 \over d} $$.   Then the bits in the binary representation of x correspond to the "division by 2's" of the original formulation of the problem.      
For instance, with $a_0 = 605, d=13$ I found $2^S = a_0 + d \cdot x $ with $ S=11, x=111$ and $2048 = 605 + 13 \cdot 111 $ 
(#1): Referring to another answer we might reformulate this as $ 2 = a_0^{1 \over S} \pmod d$ which hints to the concept of "primitive roots (mod p)". 
A: This question is close since a long time, but I would like to add my solution, that could interest readers.
First, we can assume d is odd.
Let's define the following sequence:
\begin{align}
a_0 &= 1\\
a_{n+1} &= 2^{b_n}a_n-d\\ &\quad\text{Where } {b_n} \text{ is the only integer } b_n \ge 1\text{ such that } 2^{b_n-1}a_n\leq d \lt 2^{b_n}a_n.
\end{align}
We show by induction that $a_n$ is well defined, odd and that $1 \leq a_n \leq d$.
Since $a_n$ exist and $1\leq a_n \leq d$, $a_{n+1}$ exist.
Since $1 \leq b_n$ and d odd, $a_{n+1}$ is odd.
Clearly we have $1 \leq a_{n+1}$. Since $2^{b_n-1}\leq \frac{d}{a_n} \lt 2^{b_n}$ we have $2^{b_n}-\frac{d}{a_n} \leq 2^{b_n-1}$ and so $a_{n+1}\leq d$.
We deduce that the sequence $(a_n)$ is periodic from a certain rank, at least two terms between $a_0,a_1,..,a_{\frac{d+1}{2}}$ must be equal ($a_n$ is odd so we have $\frac{d+1}{2}$ possibilities for $a_n$).
We can rewrite the sequence of the problem, eluding even terms and with a different initial condition, as:
\begin{align}
u_0 &\in 2\mathbb{N}+1\\
u_{n+1} &= \frac{u_n+d}{2^{v_2(u_n+d)}}\\ &\quad\text{Where } {v_2(n)} \text{ is the 2-adic valuation of n.}
\end{align}
Taking $u_0=a_n$, we have $u_k=a_{n-k} $ and so $u_n=a_0=1$.
Now, if $a_n$ do not take the value 1 for any $0 \lt n \leq \frac{d+1}{2}$, then it's period don't contain 1, and so taking $u_0=a_\frac{d+1}{2}$ we can't have $u_\frac{d+1}{2}=1$.
Then there exist $0 \lt n \leq \frac{d+1}{2}$ such that $a_n=1$.
Then taking $u_0=a_n=1$ we have $u_n=1$.
So, with $u_0=1$, there exist $0 \lt n \leq \frac{d+1}{2}$ such that $u_n=1$.
