If I have $100$ dollars and I spend it all in a series of transactions costing a random whole number of dollars from $1$ dollar to however much I have at that time, what is the expected number of dollar values I will have at any point had that are powers of $2$?
For example, $100 \to 64 \to 23 \to 16 \to 9 \to 8 \to 4 \to 1 \to 0$ contains 5 powers of 2.
What if I have $128$ dollars? Is there a closed form for the expected number of powers of $2$ found in the sequence, given how many dollars I start with?
Let $(X_n)_{n\geq 0}$ denote the sequence you get (just pad it with infinitely many $0$s if you want). Then we have $$P(\exists n \geq 0, X_n = j | X_0 = i) = \begin{cases}\frac{1}{1+j} & i > j\geq0 \\ 1 & i=j \\ 0 & i < j\end{cases}$$
You are asking for the value of the sum $$\sum_{k=0}^\infty P(\exists n\geq 0, X_n = 2^k | X_0=x)$$ If $x$ is a power of two, this has the form: $$1 + \sum_{k=0}^{\log_2(x)-1} \frac{1}{1+2^k}$$ If $x$ isn't a power of two, it has the form: $$\sum_{k=0}^{\lfloor \log_2(x)\rfloor} \frac{1}{1+2^k}$$
Note: Wolfram Alpha gives the closed form of this sum in terms of the "q-digamma" function, which I personally had never even heard of before, so as far as I'm concerned, that sum is the most simplified I can give the answer.