Description

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:

int work(int x){
    if(x==1) return 0;
    else return work(rand(1,x))+1;
}

In Pascal, this code is:

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:

Input Format

A positive integer $n$.

Output Format

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

2

2.00000

3

2.50000

100000

13.09014

Hint

[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