# Is there a $k\geq 1$ such that $a_k=2018$?

The following question is from a contest in my city in the year 2018 (sorry if the wording is bad, I translated this from my language):

The numbers $$a_0,a_1,\dots$$ are formed such that $$a_0$$ is a positive integer and $$a_{n+1}$$ is either equal to $$2a_n+1$$ or equal to $$\frac{a_n}{a_n+2}$$ for any $$n\geq 0$$. Decide if there exists a number $$k\geq1$$ such that $$a_k=2018$$.

I tried working backwards. If $$a_n=x$$, then $$a_{n-1}$$ is either $$\frac{x-1}{2}$$ or $$\frac{2x}{1-x}$$. By this I can say if $$a_k=2018$$, then $$a_{k-1}$$ is either $$\frac{2017}{2}$$ or $$-\frac{4036}{2017}$$. But we can't get negative values. So we can ignore the second value and continue working backwards and take only the first value. But we cannot get a positive integer at the last. So such $$k$$ cannot exist.

Is this a right solution?

• Notice that when $x<1$, you will get $\frac{2x}{1-x}$ as a positive number. By working backwards, you will eventually reach such an $x$. So you can't just ignore the second value in all cases. Oct 12, 2021 at 13:08
• Oct 12, 2021 at 13:53

For a given odd integer $$N > 1$$, we let $$S_N$$ denote the set $$\{\frac x y: x, y \in \Bbb Z_{> 0}, \gcd(x, y) = 1, x + y = N\}$$.

We define two functions $$f, g$$ on $$S_N$$ as follows.

If $$\frac x y \in S_N$$ with $$x > y$$, then $$f(\frac xy) = \frac{x - y}{2y}$$; if $$\frac xy \in S_N$$ with $$x < y$$, then $$f(\frac xy) = \frac{2x}{y - x}$$.

If $$\frac xy \in S_N$$ with $$y$$ even, then $$g(\frac xy) = \frac{x + \frac y2}{\frac y2}$$; if $$\frac xy \in S_N$$ with $$x$$ even, then $$g(\frac xy) = \frac{\frac x2}{\frac x2 + y}$$.

It is easy to check that $$f$$ and $$g$$ are both maps from $$S_N$$ to $$S_N$$, and they are inverses of each other.

Note also that for any $$a \in S_N$$, $$g(a)$$ is either $$2a + 1$$ or $$\frac a{a + 2}$$.

Since $$S_N$$ is a finite set, we know that $$g$$ is just a permutation of that set. This means that for any element $$a \in S_N$$, there exists $$k \in \Bbb Z_{> 0}$$ such that $$g^{(k)}(a) = a$$, where $$g^{(k)}$$ denotes the $$k$$-th iteration of $$g$$.

Now take $$N = 2019$$ and $$a = \frac {2018}1$$. We have seen that there exists $$k \in \Bbb Z_{> 0}$$ such that $$g^{(k)}(2018) = 2018$$.

We then simply define $$a_i = g^{(i)}(2018)$$ for $$i = 0, \dots, k$$.

This leads to the following sequence:

$$2018, 1009/1010, 1514/505, 757/1262, 1388/631, 694/1325, 347/1672, 1183/836, 1601/418, 1810/209, 905/1114, 1462/557, 731/1288, 1375/644, 1697/322, 1858/161, 929/1090, 1474/545, 737/1282, 1378/641, 689/1330, 1354/665, 677/1342, 1348/671, 674/1345, 337/1682, 1178/841, 589/1430, 1304/715, 652/1367, 326/1693, 163/1856, 1091/928, 1555/464, 1787/232, 1903/116, 1961/58, 1990/29, 995/1024, 1507/512, 1763/256, 1891/128, 1955/64, 1987/32, 2003/16, 2011/8, 2015/4, 2017/2, 2018$$

• +1 interesting argument and it does work. Oct 12, 2021 at 14:47