Let $y_n = \frac{x_n}{2^n}$. Then $y_n = y_{n-1}$ or $y_n = y_{n-1} + \frac{1}{n\cdot 2^n}$. Let $x = \frac{a}{b}\cdot 2^l$, where $b$ is odd, $a$ is odd, $\gcd(a,b) = 1$, and $l$ is an integer. By the Pigeonhole Principle, there exists a nonzero residue $r$ such that $(2^{2^kb}\cdot 2^k)^{-1} \equiv r \pmod{b}$ for infinitely many $k$. Let $d \equiv -a2^l r^{-1} \pmod{b}$, and consider $d$ of the infinitely many $k$ with $(2^{2^kb}\cdot 2^k)^{-1} \equiv r \pmod{b}$, which we call $k_1, k_2, \cdots k_d$. For all $k_i$, let $y_{bk_i} = y_{bk_i-1}+\frac{1}{bk_i 2^{bk_i}}$, and for all other numbers, let $y_m = y_{m-1}$. If we take $N > bk_d$, then $y_N = x+\sum_{i=1}^d \frac{1}{bk_i 2^{bk_i}}$. Since $(2^{2^{k_i}b}\cdot 2^{k_i})^{-1} \equiv r \pmod{b}$ and $d \equiv -a2^l r^{-1} \pmod{b}$, the numerator (when put over the denominator of $2^{2^{k_i}b}\cdot 2^{k_i}b$) of this fraction is divisible by $b$. Thus the denominator of $y_N$ divides $2^{2^{k_i}b}\cdot 2^{k_i}$, a power of $2$, so for some sufficiently large $K$, $x_K = 2^Ky_K=2^Ky_N$ will be an integer.

Note that $x_n=2^nx+\frac{2^{n-1}c_1}1+\frac{2^{n-2}c_2}2+\ldots+\frac{2c_{n-1}}{n-1}+\frac{c_n}n$, where $c_i\in\{0,1\}$ for all $i$, and all choices of $c_i$ are achievable. Let the $x=\frac j{2^ab}$, where $a$ and $b$ are nonnegative integers with odd, and take $n=a+2^mb-m$, where $m$ is a large integer. Now, set $c_i=0$ unless $i$ is $b$ multiplied by a power of 2. Then, we have that $x_n=\frac{2^{n-a}j+2^{n-b}c_1+2^{n-2b-1}c_2+\ldots+2^{n-2^{m-1}b-(m-1)}c_{2^{m-1}}+2^ac_{2^m}}b$. We want to find some subset of $\{2^{n-b},2^{n-2b-1},\ldots,2^a\}$ that sum to $-2^{n-1}j$ mod $b$. This is always achievable for sufficiently large $m$ as all numbers in the set are relatively prime to $b$, so we are done.

v_Enhance wrote: A rational number $x$ is given. Prove that there exists a sequence $x_0, x_1, x_2, \ldots$ of rational numbers with the following properties: (a) $x_0=x$; (b) for every $n\ge1$, either $x_n = 2x_{n-1}$ or $x_n = 2x_{n-1} + \textstyle\frac{1}{n}$; (c) $x_n$ is an integer for some $n$. Note that $$x_n=2^nx_0+\sum^n_{i=1} \left(\frac{2^{n-i}}{i}\right)\varepsilon_i$$where $\varepsilon_i \in \{0,1\}$ is upto us. Let $x_0=\tfrac{p}{2^mq}$ with $q$ an odd positive integer. Note that it suffices to remove $q$ from the denominator since $x_{n+m}=2^mx_n$ will then do our job. Let $s \equiv \tfrac{1}{2^m}p \pmod{q}$. Now we see $2^{n-m}p- 2^ns \equiv 0 \pmod{q}$. Also we'll only pick an index $r$ if $\left(\frac{2^{n-r}}{r}-\frac{1}{q}\right)$ is an integer. Also let $r=2^jq$. Then we wish $q \mid 2^{n-2^jq-q} -1$ for all such $j$. Let $v$ be large enough, and $2^{j} \equiv 2^v \pmod{\phi(q)}$. Let $g$ be the largest odd divisor of $\phi(q)$ then let $j \equiv v \equiv 0 \pmod{\phi(g)}$ and $j \equiv 0 \pmod{\phi(q)}$. It is clear that we can pick any number upto $q$ of such $j$'s. Now put them to be the $v_2$'s for $r$, and $n \equiv 2^vq \pmod{\phi(q)}$ be sufficiently large. Accordingly, we see that $$x_n \in \mathbb{Z} \iff \frac{2^ns}{q}+\underbrace{\frac{1}{q}+\frac{1}{q}+\dots+\frac{1}{q}}_{k} \in \mathbb{Z}$$so pick $1 \le k \le q$ wisely, as per the residue of $2^ns \pmod{q}$. P.S. I realize how awful the wording is here. The main idea is to pretty much surmised in the last line: we want all those fractions to actually be $\tfrac{1}{q}$ less than an integer. Adding up a good number of them will neutralise the residue of the initial term. Multiplying by $2^m$ will deal with any $v_2$'s in the denominators.

Let $x = a/b$, where we may assume $\gcd(a,b) = 1$. It suffices to show we can find some $a_1 < a_2 < \cdots <a_n$ such that $$x + \frac{1}{a_1 2^{a_1}} + \frac{1}{a_2 2^{a_2}} + \cdots + \frac{1}{a_n 2^{a_n}}$$is a dyadic rational (i.e. its denominator is a power of two). We will induct on the largest prime $p$ dividing $b$. Suppose $p^{\ell} \vert \vert b$ and write $b = p^{\ell} b'$. We want to find $k$ such that $$y := \frac{a}{b} + \frac{1}{2^k k} = \frac{2^k k a + b}{2^k k b}$$has only primes less than $p$ dividing its denominator. Let $k = p^{\ell} m$. Then we have $$y = \frac{2^k p^{\ell} m a + p^{\ell} b'}{2^k k b} = \frac{2^k m a + b'}{2^k p^{\ell} m b'}$$Now $b'$ has only primes less than $p$ as divisors, so we should choose $m$ such that 1. all prime divisors of $m$ are less than $p$. 2. $p^{\ell}$ divides the numerator of $y$. If we do so, we ensure $y$ has only primes less than $p$ dividing its denominator, so we are done by induction. We want $$2^{p^\ell m} m \equiv -b'/a \pmod{p^{\ell}}$$so by Euler's theorem, it suffices to ensure $m \equiv 0 \pmod{p-1}$ and $m \equiv -b'/a \pmod{p^{\ell}}$. Writing $m = (p-1)m'$ and $-b'/a \equiv c \pmod{p^{\ell}}$, we want to find $m'$ such that $m' \equiv c/(p-1) \pmod{p^{\ell}}$. But we can do this by taking $m'$ to be a power of a primitive root mod $p^{\ell}$ (this ensures the prime factors of $m'$ are less than $p$ and we can make $m'$ as large as desired).

In general, the formula for $x_n$ is \[ x_n = 2^nx + \frac{2^{n-1}\varepsilon_1}{1} + \frac{2^{n-2}\varepsilon_2}{2}+\frac{2^{n-3}\varepsilon_3}{3}+\cdots+\frac{2^0\varepsilon_n}{n},\]where $\varepsilon_i \in \{0,1\}$ for all $1\le i \le n$. Let $x=\tfrac{a}{b}$; note that $b$ is fixed. WLOG $b$ is odd by initially multiplying by 2 enough times. If we can find an $n$ such that there are least $b$ numbers $r<n$ with $\tfrac{2^{n-r}}{r}-\tfrac{1}{b} \in \mathbb{Z}$, then we could make only a subset of these $\varepsilon_r$'s equal to 1, and get an integer $x_n$. To do this, we strategically only consider $r$ of the form $r=2^kb$ as we vary $k$. Then \[ \frac{2^{n-2^kb}}{2^kb} - \frac{1}{b} \in \mathbb{Z} \iff 2^kb \mid 2^{n-2^kb}-2^k \iff b\mid 2^{n-k-2^kb}-1. \]This new condition is satisfied if $n-k-2^kb \equiv 0\mod{\phi(b)}$. We want an $n$ such that: we can find at least $b$ values $k$ for which \[ 2^kb + k \equiv n \mod \phi(b).\]Let $f(k)=2^kb+k \mod \phi(b)$. If we plug in sufficiently many values of $k$ into $f(k)$, we will get some residue $\mod \phi(b)$ that occurs $100b>b$ times. Letting $n \mod \phi(b)$ be this residue, we can easily find a sufficiently large $n$ which works.

Absurd problem. Consider a sequence $x_0,x_1,\dots,x_m$ satisfying the described properties. Call a nonnegative integer $i$ $\textit{interesting}$ if $x_{i+1}=2x_i+\frac{1}{i+1}.$ Let $\{n_1,n_2,\dots,n_k\}$ be the set of interesting integers. We can compute that $$x_m=2^{m}x_{0}+\frac{2^{m-n_1}}{n_1}+\frac{2^{m-n_2}}{n_2}+\dots+\frac{2^{m-n_k}}{n_k}$$$$= 2^{m}\left(x_0+\frac{1}{n_{1}2^{n_{1}}}+\frac{1}{n_{2}2^{n_{2}}}+\dots+\frac{1}{n_{k}2^{n_{k}}}\right).$$It suffices to show that for any rational number $x_0=\frac{p}{q},$ we can choose $m,n_1,n_2,\dots,n_k$ such that the above expression is an integer. Note that we may assume $q$ is odd. Additionally, for convenience, let $f(x)=x\cdot 2^x.$ Choose some large $N,$ and consider the numbers $$\frac{f(2^{N}q)}{f(q)},\frac{f(2^{N}q)}{f(2q)},\dots,\frac{f(2^{N}q)}{f(2^{N}q)}.$$Since each of these numbers is a power of two, all of them are relatively prime to $q.$ Therefore, if we pick $N$ large enough, then some of these numbers must have a sum congruent to $r$ modulo $q$ for any $r$ relatively prime to $q.$ Choose $r=-p\cdot (f(2^{N}q)/q)$ and $m=f(2^{N}q)/q.$ It is easy to see this works, so we are done.

Let $x=\frac{p}{q}$ with $(p,q)=1$. Suppose $q$ is odd. Write $x_n=2x_{n-2}+\frac{c_n}{n}$, where $c_n\in \{0,1\}$. It is not hard to get to the relation $$x_n=2^n\frac{p}{q}+\sum_{k=0}^{n-1}\frac{2^kc_{n-k}}{n-k}\Leftrightarrow qx_n=2^np+\sum_{k=0}^{n-1}\frac{2^kc_{n-k}q}{n-k}$$Take $x_i=0$ for every $i\neq 2^kq$ for some $k$. Then, if $n=2^yq+\alpha$ with $\alpha<2^yq$ we have : $$x_n=2^n\cdot \frac{p+2^{-q}c_q+2^{-2q}c_{2q}+2^{-4q}c_{4q}+2^{-8q}c_{8q}+\dots +2^{-2^yq}c_{2^yq}}{q}$$$$=2^{\alpha}\cdot \frac{p\cdot 2^{2^yq}+2^{(2^y-1)q}c_q+2^{(2^y-2)q}c_{2q}+2^{(2^y-4)q}c_{4q}+2^{(2^y-8)q}c_{8q}+\dots+c_{2^yq}}{q}$$Now let $p\cdot 2^{2^yq}\equiv c(\text{mod } q)$. Keep enlarging $y$ by $\varphi(\varphi(q))\cdot K$ for some huge $K$ so that there are at least $q-c$ distinct numbers $i$ with $k-i=\varphi(\varphi(q))\cdot C$ for some $C$. This way, the product $p\cdot 2^{2^yq}$ is constant mod $q$, and $2^{(2^k-2^i)q}\equiv 1(\text{mod } q)$. Make exactly $q-c$ of their $c_i$'s $1$ and the rest $0$. Then, finally: $$p\cdot 2^{2^yq}+2^{(2^y-1)q}c_q+2^{(2^y-2)q}c_{2q}+2^{(2^y-4)q}c_{4q}+2^{(2^y-8)q}c_{8q}+\dots+c_{2^yq}\equiv c+q-c\equiv 0(\text{mod }q)$$hence $x_n\in \mathbb{Z}.$ If $q=2^st$, then keep multiplying by 2 until you get to $x_s=\frac{p}{q}$, and repeat the same process as above for $x_s$.

Different solution? Think of the sequence as an ongoing process, where we advance one term every second. All fractions, unless otherwise specified, are reduced. Further, refer to the transition $2x_{n-1} \to x_n$ as move one/first move and $2x_{n-1}+\tfrac{1}{n} \to x_n$ as move two/second move. The key claim is as follows: Claim: At any given time, we can (after finitely many advances) eliminate a factor of $p$ in the denominator while only adding prime factors less than $p$, where $p>2$ is the largest prime dividing the denominator. Proof: Suppose we start with $p^e$ in the denominator for $p$ maximal. Do first moves until we reach a term of the form $(p-1)^{2k}p^e$ for $k$ positive (that is, first moves up to $2x_{(p-1)^{2k}p^e-1} \to x_{(p-1)^{2k}p^e}$). Suppose that our fraction for term $(p-1)^{2k}p^e$ is $\frac{x}{Ap^e}$ for some $p \nmid A$. Then continue with first moves until $(p-1)^{2k+2}p^e-1$ and do a second move to get to $(p-1)^{2k+2}p^e$. Our fraction then is $$\frac{x2^{p^e((p-1)^{2k+2}-(p-1)^{2k})}}{Ap^e}+\frac{1}{(p-1)^{2k+2}p^e}=\frac{(p-1)^{2k+2}x2^{p^e((p-1)^{2k+2}-(p-1)^{2k})}+A}{Ap^e(p-1)^{2k+2}}.$$Since $p-1$ divides the exponent of $2$, the numerator is simply congruent to $x+A \pmod{p}$. Further, the value of $\text{denominator}/p^e$ is also still $A \pmod{p}$. Hence we may repeat this procedure as many times as we wish, going from $(p-1)^{2a}p^e$ to $(p-1)^{2a+2}p^e$ every time, each time changing the value of the numerator $\pmod{p}$ by $+A$. Since $p \nmid A$, doing this an appropriate number of times eventually yields a numerator divisible by $p$, successfully eliminating (at least) one factor of $p$ in the (reduced) denominator. Further, since we only ever multiply the denominator by powers of $p-1$, we never add any primes greater than $p$ to the denominator, as desired. To finish, note that by repeatedly employing the above claim, we eventually will end up with a denominator that's a power of $2$, whence we simply do first moves enough times to get an integer. $\blacksquare$

funny problem

We will describe a way to reduce the exponent of the largest prime factor of the denominator without introducing any new prime factors other than adding extra copies of $2$ as long as the denominator is not already a power of 2 (if it is we are essentially already done). Suppose $p$ is the largest prime dividing the denominator, $d$, and that $k$ is the largest positive integer for which $p^k\mid d$. Consider the progression of $(p^k)x_n\pmod{p}.$ The goal is to get this to 0 to decrease the exponent of $p$. At each step, we double it, and optionally add $\frac{p^k}{n}$ (which only matters mod $p$ if $p^k\mid n$). Consider indices of the form $p^k\cdot 2^m$. We "scout" such an index sufficiently far away ($m$ sufficiently large) such that $2^{-m}\equiv c\pmod{p}.$ The key now is to consider indices $p^k\cdot 2^s$ for $s<m$ that are reached along the way that can be used to "adjust" our current residue. Of course, as long as $m$ is big enough, there exist sufficiently many such $s$ for which $2^{-s}\equiv 1\pmod{p}$, so that our residue increases by 1 if we decide to add it on $p^k\cdot 2^s.$ Furthermore, sufficiently many of these indices are multiple of $p-1$ away from our "target" index ($2^s\equiv 2^m\pmod{p-1}$). Thus, the final effect of adding 1 at that point is also increasing the final residue by 1 due to FLT (since it doubles some multiple of $p-1$ times). Thus, as long as we have sufficiently many of these (at least $p$), we can "control" our ending to any residue, thus allowing us to guarantee to reach 0 after the final $c$ is added. This process does not increase the exponent of any primes other than $2$, since all denominators of things we added only have the prime factors $2$ and $p$, and it decreases the exponent of the largest prime dividing $d$. Consider the ordinal $$v_2(d)+v_3(d)\omega +v_5(d)\omega^2+v_7(d)\omega^3\dots.$$This ordinal strictly decreases after each application of the process until $d$ is a power of 2, so the process will terminate in a finite number of moves. At that point, we just keep doubling to finish.

Let $x = a/b$. We perform induction on the largest prime factor $p$ of $b$; in particular, it suffices to show that with $x_0 = x$, there exists an index $n$ with $x_n = a_n/b_n$ in lowest terms and $b_n$ not divisible by $p$. Suppose that $\nu_p(b) = \ell$. Further simplifying, we just need to find an algorithm that spits out an $x_n$ with $\nu_p(b_n) < \ell$ and $b_n$ having no larger prime factors than $p$. To see this, let $b = \frac r{p^\ell}$ where $r$ is some rational number. For a $p \nmid k$ to be determined, we may use the first recursion up until $k \cdot p^\ell$ to get $$x_k = \frac{2^{p^\ell k} \cdot r}{p^\ell} + \frac 1{kp^\ell} = \frac{2^{p^\ell k} r + \frac 1k}{p^\ell}.$$In particular, we just need to guarantee that $$1+k \cdot 2^k \cdot r \equiv 0 \pmod p \iff k \cdot 2^k \equiv -\frac 1r \pmod p.$$We can do this by setting $k = (p-1)s$ where $s$ is the integer less than $p$ such that $s \equiv \frac 1r \pmod p$; then $$k \cdot 2^k = (p-1)s \cdot 2^{(p-1)s} \equiv -\frac 1r \cdot 1 = -\frac 1r \pmod p.$$On the other hand, the denominator $b_k$ of $x_k$ is a divisor of $p^{\ell - 1} \gcd((p-1)s, r)$, which has no prime factors greater than $p$. This concludes the induction.

We eliminate the denominator one odd prime at a time. Suppose we are currently on $x_k=K$, which has at least one odd prime factor of $p$ in the denominator: Consider only adding certain fractions of the form $\frac 1q = \frac{1}{2^ap}$. Notice that all subsequent terms are of the form \[a_n = 2^{n-k} \cdot K + \frac 1p \cdot \sum_{k \leq q \leq n} \left\{\frac{1}{2^a} \cdot 2^{n-q}, 0\right\}.\] If we make $n$ sufficiently large, the possible values for the summation spans every residue modulo $p$ through Pigeonhole. Consequently, we are able to choose our possibilities for $q$ such that we eliminate a factor of $p$. We finish by repeating this process for all odd primes, then simply double until we reach an integer. $\blacksquare$