Expected Value Iteratively picking divisors of number [closed]
$begingroup$
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.
probability elementary-number-theory recurrence-relations expected-value dynamic-programming
asked Jan 8 at 13:39
Sameer LalSameer Lal
215
$endgroup$
closed as off-topic by Saad, Cesareo, Namaste, Alexander Gruber♦ Jan 8 at 22:06
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Cesareo, Namaste, Alexander Gruber
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
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.
probability elementary-number-theory recurrence-relations expected-value dynamic-programming
asked Jan 8 at 13:39
Sameer LalSameer Lal
215
$endgroup$
closed as off-topic by Saad, Cesareo, Namaste, Alexander Gruber♦ Jan 8 at 22:06
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Cesareo, Namaste, Alexander Gruber
If this question can be reworded to fit the rules in the help center, please edit the question.
1
$begingroup$
Neat question. What have you tried?
$endgroup$
– Alex R.
Jan 8 at 19:38
$begingroup$
Codeforces lists this as a past contest, if any Reader is concerned.
$endgroup$
– hardmath
Jan 8 at 21:26
$begingroup$
Solution is posted on codeforces. I did a brute force implementation which didn't pass test cases due to time complexity. Looking to see if there's an elegant mathematical solution.
$endgroup$
– Sameer Lal
Jan 9 at 22:10
add a comment |
$begingroup$
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.
probability elementary-number-theory recurrence-relations expected-value dynamic-programming
asked Jan 8 at 13:39
Sameer LalSameer Lal
215
$endgroup$
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.
probability elementary-number-theory recurrence-relations expected-value dynamic-programming
probability elementary-number-theory recurrence-relations expected-value dynamic-programming
asked Jan 8 at 13:39
Sameer LalSameer Lal
215
asked Jan 8 at 13:39
Sameer LalSameer Lal
215
edited Jan 12 at 21:14
Sameer Lal
asked Jan 8 at 13:39
Sameer LalSameer Lal
215
asked Jan 8 at 13:39
Sameer LalSameer Lal
215
asked Jan 8 at 13:39
Sameer LalSameer Lal
215
215
closed as off-topic by Saad, Cesareo, Namaste, Alexander Gruber♦ Jan 8 at 22:06
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Cesareo, Namaste, Alexander Gruber
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Saad, Cesareo, Namaste, Alexander Gruber♦ Jan 8 at 22:06
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Cesareo, Namaste, Alexander Gruber
If this question can be reworded to fit the rules in the help center, please edit the question.
1
$begingroup$
Neat question. What have you tried?
$endgroup$
– Alex R.
Jan 8 at 19:38
$begingroup$
Codeforces lists this as a past contest, if any Reader is concerned.
$endgroup$
– hardmath
Jan 8 at 21:26
$begingroup$
Solution is posted on codeforces. I did a brute force implementation which didn't pass test cases due to time complexity. Looking to see if there's an elegant mathematical solution.
$endgroup$
– Sameer Lal
Jan 9 at 22:10
add a comment |
1
$begingroup$
Neat question. What have you tried?
$endgroup$
– Alex R.
Jan 8 at 19:38
$begingroup$
Codeforces lists this as a past contest, if any Reader is concerned.
$endgroup$
– hardmath
Jan 8 at 21:26
$begingroup$
Solution is posted on codeforces. I did a brute force implementation which didn't pass test cases due to time complexity. Looking to see if there's an elegant mathematical solution.
$endgroup$
– Sameer Lal
Jan 9 at 22:10
1
1
$begingroup$
Neat question. What have you tried?
$endgroup$
– Alex R.
Jan 8 at 19:38
$begingroup$
Neat question. What have you tried?
$endgroup$
– Alex R.
Jan 8 at 19:38
$begingroup$
Codeforces lists this as a past contest, if any Reader is concerned.
$endgroup$
– hardmath
Jan 8 at 21:26
$begingroup$
Codeforces lists this as a past contest, if any Reader is concerned.
$endgroup$
– hardmath
Jan 8 at 21:26
$begingroup$
Solution is posted on codeforces. I did a brute force implementation which didn't pass test cases due to time complexity. Looking to see if there's an elegant mathematical solution.
$endgroup$
– Sameer Lal
Jan 9 at 22:10
$begingroup$
Solution is posted on codeforces. I did a brute force implementation which didn't pass test cases due to time complexity. Looking to see if there's an elegant mathematical solution.
$endgroup$
– Sameer Lal
Jan 9 at 22:10
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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.
answered Jan 9 at 1:24
Alex R.Alex R.
25.1k12452
$endgroup$
$begingroup$
I think it is enough to find the expectation for a prime power $p^n$. If it is denoted by $mu(p,n)$ and $v=p_1^{n_1}cdots p_k^{n_k}$ then the expectation will be $mu(p_1,n_1)timescdotstimesmu(p_k,n_k)$ by independence. Unfortunately it seems hard to find $mu(p,n)$. I gave up.
$endgroup$
– drhab
Jan 9 at 9:57
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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.
answered Jan 9 at 1:24
Alex R.Alex R.
25.1k12452
$endgroup$
$begingroup$
I think it is enough to find the expectation for a prime power $p^n$. If it is denoted by $mu(p,n)$ and $v=p_1^{n_1}cdots p_k^{n_k}$ then the expectation will be $mu(p_1,n_1)timescdotstimesmu(p_k,n_k)$ by independence. Unfortunately it seems hard to find $mu(p,n)$. I gave up.
$endgroup$
– drhab
Jan 9 at 9:57
add a comment |
$begingroup$
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.
answered Jan 9 at 1:24
Alex R.Alex R.
25.1k12452
$endgroup$
$begingroup$
I think it is enough to find the expectation for a prime power $p^n$. If it is denoted by $mu(p,n)$ and $v=p_1^{n_1}cdots p_k^{n_k}$ then the expectation will be $mu(p_1,n_1)timescdotstimesmu(p_k,n_k)$ by independence. Unfortunately it seems hard to find $mu(p,n)$. I gave up.
$endgroup$
– drhab
Jan 9 at 9:57
add a comment |
$begingroup$
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.
answered Jan 9 at 1:24
Alex R.Alex R.
25.1k12452
$endgroup$
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.
answered Jan 9 at 1:24
Alex R.Alex R.
25.1k12452
edited Jan 9 at 18:50
answered Jan 9 at 1:24
Alex R.Alex R.
25.1k12452
answered Jan 9 at 1:24
Alex R.Alex R.
25.1k12452
answered Jan 9 at 1:24
Alex R.Alex R.
25.1k12452
25.1k12452
$begingroup$
I think it is enough to find the expectation for a prime power $p^n$. If it is denoted by $mu(p,n)$ and $v=p_1^{n_1}cdots p_k^{n_k}$ then the expectation will be $mu(p_1,n_1)timescdotstimesmu(p_k,n_k)$ by independence. Unfortunately it seems hard to find $mu(p,n)$. I gave up.
$endgroup$
– drhab
Jan 9 at 9:57
add a comment |
$begingroup$
I think it is enough to find the expectation for a prime power $p^n$. If it is denoted by $mu(p,n)$ and $v=p_1^{n_1}cdots p_k^{n_k}$ then the expectation will be $mu(p_1,n_1)timescdotstimesmu(p_k,n_k)$ by independence. Unfortunately it seems hard to find $mu(p,n)$. I gave up.
$endgroup$
– drhab
Jan 9 at 9:57
$begingroup$
I think it is enough to find the expectation for a prime power $p^n$. If it is denoted by $mu(p,n)$ and $v=p_1^{n_1}cdots p_k^{n_k}$ then the expectation will be $mu(p_1,n_1)timescdotstimesmu(p_k,n_k)$ by independence. Unfortunately it seems hard to find $mu(p,n)$. I gave up.
$endgroup$
– drhab
Jan 9 at 9:57
$begingroup$
I think it is enough to find the expectation for a prime power $p^n$. If it is denoted by $mu(p,n)$ and $v=p_1^{n_1}cdots p_k^{n_k}$ then the expectation will be $mu(p_1,n_1)timescdotstimesmu(p_k,n_k)$ by independence. Unfortunately it seems hard to find $mu(p,n)$. I gave up.
$endgroup$
– drhab
Jan 9 at 9:57
add a comment |
1
$begingroup$
Neat question. What have you tried?
$endgroup$
– Alex R.
Jan 8 at 19:38
$begingroup$
Codeforces lists this as a past contest, if any Reader is concerned.
$endgroup$
– hardmath
Jan 8 at 21:26
$begingroup$
Solution is posted on codeforces. I did a brute force implementation which didn't pass test cases due to time complexity. Looking to see if there's an elegant mathematical solution.
$endgroup$
– Sameer Lal
Jan 9 at 22:10