Xrfgtjtk

You have a positive integer $n$ written on a blackboard, and you perform $k$ iterations of the following procedure: say the current number is $v$. Pick one of the divisors of $v$ (possibly 1 and $v$ itself) and replace $v$ with this divisor. Each divisor is equally likely to be chosen.

What is the expected value of the number on the blackboard after $k$ iterations?

[This questions is taken from Hello2019D Codeforces]

EDIT (since this was flagged): I am posting this to see if there is any elegant mathematical solution without brute forcing/DP.

Write $v_n=p_1^{alpha_1(n)}cdots p_{r}^{alpha_r(n)}$, and $d_{k}$ the divisor chosen at at step $k$. Since divisors are picked uniformly at random, it's equivalent at any given time to sample $d$ by sampling $a_{I}(k+1)$ from ${0,1,cdots,alpha_i(k)}$, so that $d_{n+1}=p_1^{a_1(k+1)}cdots p_r^{a_r(k+1)}$ and $alpha_{I}(k+1)=alpha_i(k)-a_i(k+1).$ By symmetry, it's equivalent to instead pick the form of $v_{k+1}$, e.g. $alpha_{I}(k+1)=a_i(k+1)$.

By stars and bars, for $v_k$ the probably that $v_k=p_1^{b_1}cdots p_r^{b_r}$ is equal to $prod_{i=1}^rbinom{a_i-b_i+k+1}{k}/binom{a_i+k+1}{k}$. There's probably no explicit form for this expectation, but you can now numerically compute the answer for any $v$ once you find it's prime factorization, by summing over all possibilities and their probabilities.