Choose a number, say 100000.
- Choose any random number in the range $[0, 100000]$, say $n$.
- Choose a number in the range $[0, n]$ and set $n$ to this.
- Repeat this till $n$ is zero.
A quick Python script tells me that:
$10^4\;$ takes 9.822 iterations (on average).
$10^8 \; $ takes $18.981$.
$10^{12}$ takes $28.201$.
$10^{16}$ takes $37.496$.
$10^{20}$ takes $46.82$.
$10^{200}$ takes $460.922$ iterations to reach zero.
Interestingly, these numbers don't vary much from one run of the script to another.
Could anyone provide me with a mathematical explanation for this?
Let $P_r$ be the mean number of steps from starting number $r$.
Then we have $$P_n=1+\frac 1 n\sum^{n-1}_0P_r$$ or $$nP_n=n+\sum^{n-1}_0P_r$$
Using the expressions for $nP_n$ and $(n-1)P_{n-1}$ we obtain:
$$nP_n -(n-1)P_{n-1}=n-(n-1)+P_{n-1}$$
Which simplifies to $$P_n-P_{n-1}=\frac1 n$$
Since $P_1=1$ we get the harmonic series, whose properties are well known.