Need help with even number problem

Question

Problem:
A random non-zero positive even integer, $E$ is picked.
We can call the bracketed section in the statement $E = {Acdot2^n}$ the factored form of this number (because it is even, $n$ is at least $1$). $n$ is to be as large as possible ensuring $A$ is odd.
E.g.: $E= 80$ so $A=5$ and $n=4$ because $5cdot2^4$ is the factored form of $80$.
Every time we get a random even number $E$, we will divide by $2$ until we find $A$. The question is, on average how much lower is $A$ than $E$, or what is the average $n$ you should expect to find in the factored form?

My approach:
$1/2$ of all numbers or every other number is even or in other words a factor of $2^1$
half of the factors of $2^1$ are factors of $2^2$
half of the factors of $2^2$ are factors of $2^3$
and so on.
I believe, adding from $n=1$ to infinity for $1/(2^n)cdot1/(2^n)$ may represent the change from $E$ to $A$. I added a picture with actual sigma notation at the bottom.
I got 1/(2^n) because:
1/2+1/4+1/8...= 1
1/2 of all even numbers have n=1 as the largest n in the factored form
therefore 1/2 of all even numbers can only be divided once by 2 until they become odd
1/4 of all even numbers have n=2 as the largest n in the factored form.
therefore 1/4 of all even numbers can be divided once by 4 until they become odd
1/8 of all even numbers have n=3 as the largest n in the factored form.
therefore 1/8 of all even numbers can be divided once by 8 until they become odd
1/16
etc...
generally 1/2^n of all even numbers can be multiplied by 1/2^n until odd
therefore addition from 1 to infinity of (1/(2^n))^2 will represent the difference from E to A out of a whole
According to my sigma calculator, squaring each term before adding them suggesting $A=frac{1}{3}E$. I'm convinced I messed up somewhere in trying to calculate the average difference between $E$ and $A$.

Haran · Answer

To find the expected value of $n$, we use the following method. Assume we want to find the probability that $n=n_0$ for a fixed $n_0$. We need $2^{n_0} mid E$ and $2^{n_0+1} nmid E$. This is equivalent to saying $E equiv 2^{n_0} pmod{2^{n_0+1}}$. Thus, we have one choice for $E$ in every $2^{n_0+1}$ numbers, giving us the fact that the probability that $n=n_0$ is $frac{1}{2^{n_0+1}}$. Now, consider summing this over all of $n$:
Thus, the expected value of $n$ is:
$$n_{text{avg}}=sum_{n=1}^infty frac{n}{2^{n+1}}=sum_{n=1}^infty frac{1}{2^{n+1}}+sum_{n=1}^infty frac{n-1}{2^{n+1}}=frac{1}{2}+frac{1}{2}sum_{n=1}^infty frac{n-1}{2^{n}}$$
$$n_{text{avg}}=frac{1}{2}+frac{1}{2}sum_{n=1}^infty frac{n-1}{2^n}=frac{1}{2}+frac{1}{2}sum_{n=2}^infty frac{n-1}{2^n}=frac{1}{2}+frac{1}{2}sum_{n=1}^infty frac{n}{2^{n+1}}=frac{n_{text{avg}}+1}{2}$$
This would give $n_text{avg}=1$.

JMP · Answer

Expectation is defined as:
$$sum_x xP(X=x)$$
so your sum should be:
$$sum_limits{n=1}^infty nfrac1{2^n}=2$$
wa
To sum $sum_limits{n=1}^infty dfrac n{2^n}$, observe that it equals:
$$sum_limits{n=1}^infty frac1{2^n}+sum_limits{n=2}^infty frac1{2^n}+sum_limits{n=3}^infty frac1{2^n}+dots$$
$$=1+frac12+frac14+dots=2$$

Need help with even number problem

2 Answers

Add your own answers!

Ask a Question