Suppose that $a$ is an integer. A sequence $x_{1}, x_{2}, x_{3}, x_{4}, \ldots$ is constructed with

- $x_{1}=a$,
- $x_{2 k}=2 x_{2 k-1}$ for every integer $k \geq 1$, and
- $x_{2 k+1}=x_{2 k}-1$ for every integer $k \geq 1$.

For example, if $a=2$, then

$$
x_{1}=2 \quad x_{2}=2 x_{1}=4 \quad x_{3}=x_{2}-1=3 \quad x_{4}=2 x_{3}=6 \quad x_{5}=x_{4}-1=5
$$

and so on. The integer $N=578$ can appear in this sequence after the 10th term (for example, $x_{12}=578$ when $a=10$ ), but the integer 579 does not appear in the sequence after the 10th term for any value of $a$. What is the smallest integer $N>1395$ that could appear in the sequence after the 10th term for some value of $a$ ?
Suppose that $x_{1}=a$.

Then

$$
\begin{aligned}
x_{2} & =2 x_{1}=2 a \\
x_{3} & =x_{2}-1=2 a-1 \\
x_{4} & =2 x_{3}=4 a-2 \\
x_{5} & =x_{4}-1=4 a-3 \\
x_{6} & =2 x_{5}=8 a-6 \\
x_{7} & =x_{6}-1=8 a-7 \\
x_{8} & =2 x_{7}=16 a-14 \\
x_{9} & =x_{8}-1=16 a-15 \\
x_{10} & =2 x_{9}=32 a-30 \\
x_{11} & =x_{10}-1=32 a-31
\end{aligned}
$$

The pattern above suggests that, for each integer $k \geq 1$, we have

$$
x_{2 k}=2^{k} a-\left(2^{k}-2\right) \quad \text { and } \quad x_{2 k+1}=2^{k} a-\left(2^{k}-1\right)
$$

We note that this is true for $k=1,2,3,4,5$.

Also, if this is true for some value of $k \geq 1$, then

$$
x_{2 k+2}=2 x_{2 k+1}=2\left(2^{k} a-\left(2^{k}-1\right)\right)=2^{k+1} a-2\left(2^{k}-1\right)=2^{k+1} a-\left(2^{k+1}-2\right)
$$

and

$$
x_{2 k+3}=x_{2 k+2}-1=2^{k+1} a-\left(2^{k+1}-1\right)
$$

which means that it is true for $k+1$.

This inductive reasoning shows that that this form is correct for all $k \geq 1$.

Consider the terms $x_{m}$ when $m \geq 11$. We want to determine the smallest value larger than 1395 that such a term can equal.

Suppose that $m$ is even, say $m=2 k$ for some integer $k \geq 6$.

Note that

$$
x_{m}=x_{2 k}=2^{k} a-\left(2^{k}-2\right)=2^{k}(a-1)+2=2^{6} \cdot 2^{k-6}(a-1)+2=64\left(2^{k-6}(a-1)\right)+2
$$

In other words, for every $k \geq 6$, the term $x_{2 k}$ is 2 more than a multiple of 64 . (Note that $2^{k-6}$ is an integer since $k \geq 6$.)

Suppose that $m$ is odd, say $m=2 k+1$ for some integer $k \geq 5$.

Note that

$$
x_{m}=x_{2 k+1}=2^{k} a-\left(2^{k}-1\right)=2^{k}(a-1)+1=2^{5} \cdot 2^{k-5}(a-1)+1=32\left(2^{k-5}(a-1)\right)+1
$$

In other words, for every $k \geq 5$, the term $x_{2 k+1}$ is 1 more than a multiple of 32 (Note that $2^{k-5}$ is an integer since $k \geq 5$.).

Now $43 \cdot 32=1376$ and $44 \cdot 32=1408$. Also, $21 \cdot 64=1344$ and $22 \cdot 64=1408$.

The smallest integer larger than 1395 that is 1 more than a multiple of 32 is 1409 .

The smallest integer larger than 1395 that is 2 more than a multiple of 64 is 1410 .

This means that 1409 is the smallest candidate for $N$, but we must confirm that there is a sequence with 1409 in it.

When $a=45$, the 11 th term is $32 a-31=1409$.

This means that 1409 is in such a sequence as a term past the 10 th term when $a=45$.

In particular, this sequence is $45,90,89,178,177,354,353,706,705,1410,1409$.

ANSWER: 1409