1
$\begingroup$

Consider all even natural numbers. Every 4th number has a power of 4 (or $2^2$)

Every 8th number has a power of 8 (or $2^3$)

Every 16th number has a power of 16 (or $2^4$)

What is the average number of power of 2 in any random even number?

Since every 2nd number has a power of 2,and every 4th number is a power of 4 and so on

$\left(2 \times \dfrac{1}{2}\right) + \left(4 \times \dfrac{1}{4}\right) + \left(8 \times \dfrac{1}{8}\right) + \ldots$

This goes all the way to Infinity and hence the answer is $\infty$. Is this correct?

$\endgroup$
2
$\begingroup$

A multiple of $4$ only has two powers of $2$ in its factorization and a multiple of $8$ only has three. Your sum should therefore be $$\left(1 \times \dfrac{1}{2}\right) + \left(2 \times \dfrac{1}{4}\right) + \left(3 \times \dfrac{1}{8}\right) + \ldots=2$$ because half the evens have exactly one factor of two, one quarter have exactly two factors of two and so on. Although it you can't pick a random natural number, this makes sense as the limit of the average number of factors of two in the even numbers up to $n$ as $n \to \infty$.

$\endgroup$
2
  • $\begingroup$ thanks a lot.I wonder how is the sum 2?the 1st 2 add upto to 1....not sure how to add rest,unable to use GP formula directly $\endgroup$ – Rahul Shah Dec 13 '18 at 17:42
  • 1
    $\begingroup$ It is an arithmetico-geometric series. This particular one is solved on this site. Here and here. You can search for arithmetico-geometric $\endgroup$ – Ross Millikan Dec 13 '18 at 17:56
0
$\begingroup$

I think you are double counting the multiples of $4$ since half of them have been counted as multiples of $2$. That multiple counting continues.

I think the sum (corrected as I suggest) for the power of $2$ dividing a "random integer", is $$ \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots $$ which sums to $1$. That makes sense for the average power of $2$.

The result for a random even integer would be $2$.

I put "random integer" in quotes since defining a "random integer" is a little subtle.

$\endgroup$
3
  • $\begingroup$ A "little subtle" ... like trisecting the angle. :) $\endgroup$ – John Hughes Dec 9 '18 at 21:50
  • $\begingroup$ @JohnHughes Not quite. I think you can make sense of that expected value as a limit. I didn't want to spend the time. $\endgroup$ – Ethan Bolker Dec 9 '18 at 21:54
  • $\begingroup$ Indeed... I meant that picking a uniform distribution on the integers might be a little problematic. $\endgroup$ – John Hughes Dec 9 '18 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.