Consider a sequence $\{u_i\}_{i=0}^k$, in which let $u_1 = n$ and $u_i \vert u_{i-1}\ (i > 0)$. Apparently there are a lot of sequences like that. For each $i > 0$, $u_i$ is selected randomly with equal possibilities among the divisors of $u_{i-1}$. Let’s denote $F(n)$ the expected value of $u_k$. What is $F(n)$? Read the problem statement.

For example, we have $u_0 = 6$ and need to calculate $E(u_3)$. All possible sequences of $\{u_i\}$ are:

Can we simply calculate the average value of $u_2$?, in this case:

No we can’t, because the possibilities for the sequences to happen are not all the same. For example, the possibility of $(6, 6, 6)$ is $\frac{1}{4}\times\frac{1}{4}=\frac{1}{16}$, while that of $(6, 3, 1)$ is only $\frac{1}{4}\times\frac{1}{2}=\frac{1}{8}$.

## Observation

Consider $u_i = p_1^{t_1}p_2^{t_2}\dots p_m^{t_m}$ (prime factorization). The process of choosing $u_{i+1}$ (which is a divisor of $u_i$) can be interpreted as $m$ independent steps (events). In step $j$, we choose $w_j$ as a random number from 0 to $t_j$. After all $m$ steps, we have $u_{i+1} = p_1^{w_1}p_2^{w_2}\dots p_m^{w_m}$.

This means, instead of dealing with the problem above with any number $n$, we can break it down into $m$ (the number of prime factors of $n$) smaller problems. Each small problem requires finding the expected value of $u_k$ given $u_1 = p^t$, in other word, finding $F(p^t)$. Suppose that $n = p_1^{t_1}p_2^{t_2}\dots p_m^{t_m}$, then:

## The smaller problem

How do we calculate $F(p^t)$? This should be done easily with dynamic programming or recursion. We consider the probability for the $i$-th term of the sequence to equal $p^j$:

Then the rest is straightforward:

## Complexity analysis

Factorizing $n$ takes $O(\sqrt{n})$. Calculating $F(p^t)$ takes $O(kt)$. Since $t \leq \log(n)$, the overall complexity is $O(\sqrt{n} + k\log(n))$.

See my solution written in C++.