Tstst

Let $x$ be written in lowest terms as $p/q$, and write $q = 2^r s$, where $s$ is odd. Let $S$ be the set of residue classes modulo $s$, where arithmetic on elements of $S$ is understood to be done modulo $s$. For any positive integer $N$ and any $t \in S$, say that $t$ is attainable at $N$ if there exists a sequence $x_0, x_1, \dots, x_N$ such that

* $x_0 = x$;
* $x_n = 2x_{n-1}$ or $x_n = 2x_{n-1} + 1/n$ for each $n = 1, \dots, N$;
* $s x_N$ is an integer in the residue class $t$.

Say that a subset $T \subseteq S$ is attainable at $N$ if every element of $T$ is attainable at $N$.

Lemma 1. There exists a nonempty set attainable at some $N$.

Proof. Taking $x_n = 2x_{n-1}$ for all $n$, we get $x_r = 2^r x = p/s$, in lowest terms, hence the residue class of $p$ is attainable at $r$. $\square$

Lemma 2. If the nonempty subset $T \subseteq S$ is attainable at $N$, and $T$ is not all of $S$, then there exist another subset $T'$ and $N' > N$, with $T'$ attainable at $N'$, and $T'$ containing more elements than $T$.

Proof. Choose $k$ such that $2^k s > N$, and put $N' = 2^k s + k$.

For each $t \in T$, the residue class $2^{N'-N} t$ is attainable at $N'$. Indeed, if $x_0, \dots, x_N$ attain $t$ at $N$, then just extend the sequence by defining $x_n = 2x_{n-1}$ for each $n = N+1, \dots, N'$, and we have $x_{N'} = 2^{N'-N} x_N$ from which the assertion follows.

Also, the residue class $2^{N'-N} t + 1$ is attainable at $N'$. Indeed, take the sequence $x_0, \dots, x_N$ attaining $t$ at $N$, then define $x_n = 2x_{n-1}$ for each $n = N+1, \dots, N'$ except for $n = 2^k s$, in which case we put $x_n = 2x_{n-1} + 1/n$. Then we have $x_{N'} = 2^{N'-N} x_N + 2^{N'-2^k s}/2^k s = 2^{N'-N} x_N + 1/s$, from which the assertion follows.

So the two sets of residues
$$T'_1 = \{2^{N'-N} t \mid t \in T\} \quad \text{and} \quad T'_2 = \{2^{N'-N} t + 1 \mid t \in T\}$$
are both attainable at $N'$. Also, $T'_1$ has the same number of elements as $T$, since $2^{N'-N}$ is relatively prime to $s$.

There must be some $t \in T'_1$ such that $t + 1 \notin T'_1$: Otherwise, starting from any element of $T'_1$ and applying induction, we could show that every element of $S$ must be in $T'_1$; but since $T'_1$ has the same number of elements as $T$, which by assumption is a proper subset of $S$, this is impossible. Hence, $T'_2$ contains some element not in $T'_1$. So their union $T' = T'_1 \cup T'_2$, which again is attainable at $N'$, contains strictly more elements than $T'_1$, and so contains more elements than $T$. This completes the proof. $\square$

Now, using Lemma 1 and Lemma 2, we can successively construct nonempty subsets $T_1, T_2, T_3, \dots$ having progressively more elements, each attainable at some $N_1, N_2, N_3, \dots$ respectively. This process cannot continue forever, since each $T_i$ is contained in the finite set $S$. Therefore, it must eventually stop, which happens when some $T_i$ is all of $S$. In particular, the residue class $0 \in T_i$ is attainable at $N_i$. This means that we can construct $x_0, x_1, \dots, x_{N_i}$ with $x_{N_i}$ an integer. Then just take $x_n = 2x_{n-1}$ for each $n \ge N_i + 1$, and we have an infinite sequence satisfying the conditions of the problem.

Suppose that $x_m \in \mathbb{Q} \setminus \mathbb{Z}$ is given, where $m \ge 0$. Let $p$ be the largest prime divisor of the denominator of $x_m$, and write
$$x_m = \frac{a}{b p^k}$$
where $p \nmid a$ and $p \nmid b$. We show that we can reach a value $x_n$, $n > m$, whose denominator has at most $k-1$ factors of $p$ and no larger prime divisors. Using this successively, we can decrease the largest prime divisor of the denominator until no factors are left.

If $p=2$, we may take $n=m+1$ with $x_n = 2x_m$. Therefore, we will now assume that $p \ge 3$.

Our procedure for constructing $x_{m+1}, \dots, x_n$ will be to take $x_{i+1} = 2x_i$ for $m \le i < n-1$ and
$$x_n = 2x_{n-1} + \frac{1}{n} = 2^{n-m} x_m + \frac{1}{n} = \frac{2^{n-m} a}{b p^k} + \frac{1}{n}.$$
We consider $n$ of the form $c p^k (p-1)$, where all prime factors of $c$ are less than $p$. Then
$$x_n = \frac{2^{c p^k (p-1) - m} \cdot a}{b p^k} + \frac{1}{c p^k (p-1)} = \frac{2^{c p^k (p-1)} a c (p-1) + 2^m b}{2^m b c p^k (p-1)}.$$
Since the denominator of this expression has exactly $k$ factors of $p$ and no larger prime divisors, it suffices to show that we can choose $c$ such that the numerator is divisible by $p$. Mod $p$, we have $2^{c p^k (p-1)} \equiv 1 \pmod{p}$ so we want
$$a c \equiv 2^m b \pmod{p}.$$
Since $p \nmid a$, $p \nmid b$, and $p \ne 2$, this condition has a unique solution $c = c_0$, $1 \le c_0 \le p-1$. We may now take $c = 2^{\ell(p-1)} c_0$ where $\ell$ is large enough so that $n = c p^k (p-1) > m$. This value of $c$ clearly has no prime factors greater than or equal to $p$.