Expected Path Length Iii :
Difficulty Level : Medium
Submissions : 209
Asked In :
Marks :15
: 6 | : 0
You choose a natural number from 1 to $$$n$$$ (each number being equally likely) and do the following procedure:
- Initialize a variable $$$step = 0$$$.
- Let $$$X$$$ be the current number you have.
- Randomly choose any divisor of $$$X$$$ (each divisor being equally likely). Let it be $$$Y$$$, now replace $$$X$$$ by $$$X/Y$$$. Also, increment step by $$$1$$$.
- If $$$X$$$ is not equal to $$$1$$$, repeat from $$$2^{nd}$$$ step.
Let expected value of step be represented in the form of a irreducible fraction $$$x/y$$$. Return $$$xy^{-1}$$$ mod $$$(10^9+7)$$$, where $$$y^{-1}$$$ is the modulo multiplicative inverse of $$$y$$$ modulo $$$(10^9 + 7)$$$.
The first and only line of input contains an integer $$$n$$$ $$$(1 \le n \le 10^5)$$$.
Print a single integer — the expected value of step modulo $$$10^9 + 7$$$.
1
0
2
1
In sample testcase $$$1$$$, The only possible $$$X$$$ we can choose is $$$1$$$.
For $$$X=1, step=0$$$. Therefore,expected path length = 0.
In sample testcase $$$2$$$, Different possible sequences of steps are:
$$$\{[1], [2, 1],[2,2,1],[2,2,2,1],... \}$$$
with their corresponding value of step as: $$$0,1,2,3,.....$$$ It is found that the expected value is $$$1$$$.
