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 = \{A\cdot2^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 $5\cdot2^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$.

Answer 1

Expectation is defined as:

$$\sum_x xP(X=x)$$

so your sum should be:

$$\sum_\limits{n=1}^\infty n\frac1{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$$

Answer 2

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$.