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!

• Did you intend "... if $a_n$ is even, .... if $n$ is odd." Should $n$, or $a_n$ be used in both predicates? Aug 16, 2012 at 16:05
• Thanks for pointing that out. I edited the question Aug 16, 2012 at 16:25
• Yes I have tried induction, but I see no way of relating previous values of $d$ with bigger values of $d$ (i.e. the induction step) Aug 16, 2012 at 16:40
• @RajRaina There still seems be to a typo. Did you mean to say $a_{n+1} = \frac{a_n}{2}$ if $a_n$ is even, and $a_{n+1} = a_n + d$ if $a_n$ is odd? Aug 16, 2012 at 16:41
• AHH sorry for not proofreading more carefully! I edited :) Aug 16, 2012 at 16:43

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 nice argument. You actually show what the return time is, not just that it does return as I do. Aug 16, 2012 at 18:09
• @RossMillikan: Thank you. Yes, at least for the $b_n$, the return time is given by $\mathrm{ord}(m)$, where $m\in \mathbb Z_{2m-1}^\times$ and $d = 2m-1$. But it doesn't seem easy to get a return time for the $a_n$ from this (although it does give an upper bound of $2\varphi(d)$).
– Sam
Aug 16, 2012 at 18:20
• Thank you Sam L. If I am understanding correctly, we can now say that $b_{n}\equiv 2^{−n}\pmod d$ (Claim 3), and so we need $2^n \equiv 1 \pmod d$, which has the trivial solution $n = \phi (d)-1$ since $2$ and $d$ are relatively prime, and so we will always have $b_{\phi(d)-1} =1$. What a simple solution! But what was Claim 2 necessary for? Aug 16, 2012 at 23:12
• @RajRaina: Yes. You are right, claim 2 is actually unnecessary. It is just "scaffolding" from when I was trying to figure out a way to solve the problem.
– Sam
Aug 17, 2012 at 5:15

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.

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

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$$.