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!

Solution 1:

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$

Solution 2:

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.

Solution 3:

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)".