P5147 Random Number Generator

HKE recently wrote a function $\text{rand}(l,r)$, where $l,r$ are positive integers and $l \le r$. This function returns, with equal probability, any positive integer in the interval $[l, r]$. Then he wrote another function: ```cpp int work(int x){ if(x==1) return 0; else return work(rand(1,x))+1; } ``` In Pascal, this code is: ```pascal function work(x:integer):integer; begin if x=1 then exit(0); else exit(work(rand(1,x))+1); end; ``` Given a positive integer $n$, what is the expected value of the return value of $\text{work}(n)$? Definition of expectation: Suppose all possible return values of $\text{work}(n)$ are $x_1, x_2, \dots , x_k$ with probabilities $p_1, p_2, \dots, p_k$, then the expectation is: $$\mathbb{E}=\sum_{i=1}^{k}x_i p_i.$$

A positive integer $n$.

A real number representing the expected value of $\text{work}(n)$. Keep $5$ decimal places.

[Sample 1 Explanation] $\text{work}(2)$ returns $1$ with probability $1/2$, returns $2$ with probability $1/4$, returns $3$ with probability $1/8$, and so on. Therefore, the expectation is $1/2+2/4+3/8+\dots=2$. Constraints For $30\%$ of the testdata, $n \le 9$; For $50\%$ of the testdata, $n \le 1000$; For $70\%$ of the testdata, $n \le 1000000$; For $100\%$ of the testdata, $1 \le n < 2^{31}$. Translated by ChatGPT 5