Let $R(n)$ returns an integer in the range $0,1,...,n−1$ with uniform probability. Note that this is not a true function in the mathematical sense, as inputting the same number a second time will not necessarily yield the same result. The random number generator only works for $n > 1$. Starting from a googol, $x_0 = 10^{100}$, consider the sequence $x_i = R(x_{i−1})$. Eventually the sequence terminates when $x_s = 0$ for some $s$ and no further generation is possible. What is $E[s]$?
Intuition: $R(x_i)$ generates a midpoint on average and imagine a number line cut in half. Hence, $E[s]$ is equivalent to the number of cuts until we're left with nothing but $0$ (in some sense).
So, $E[R(n)] = \frac{n-1}{2}$ for $n \geq 1$.
$E[R(10^{100})] = \frac{10^{100}-1}{2} = \frac{1}{2}\cdot10^{100}-\frac{1}{2}$
$E[R(\frac{10^{100}-1}{2})] = \frac{1}{2^2}\cdot10^{100} - \frac{1}{2^2}$
In general, we want to find $k$ such that
$\frac{1}{2^k}10^{100} - \frac{1}{2^k} = 1$. Solving for $k$ , I get $k = \log_2{(10^{100}-1)} = E[s]$. Is this the right approach?