How many factors of $2^{95}$ are greater than $10^6$

Question

The title says it all.

My problem: I can solve this using logarithms but the problem is meant to be solved by combinatorics methods which I can't see how to apply them in this kind of problem.

Answer 1

Hint:-Use the fact that all factors of $2^{95}$ is of the form $2^n$.To solve your problem find all $2^n$ greater than $10^6$.

Answer 2

We want to find how many integers $1 \le m \le 95$ are there such that

$$2^{m} > 10^6 = 2^6\cdot5^6$$ $$2^{m - 6} > 5^6$$

which simplifies the problem a little, since it is easier to compute the least power of $2$ that is greater than $5^6$ as compared to that of $10^6$.

Since $2^{14} = 16384 > 15625 = 5^6$, every $15 \le m - 6 \le 95 - 6$ satisfies the condition.

Answer 3

Recall that $10^3=1000 < 1024 =2^{10}$.

So, $2^{20} > 10^6$.

Now, since $10^3$ is so close to $2^{10}$, most probably $2^{19} < 10^6$. (Indeed, $2^{19}=524288$. Or argue that $2^{20} < 2\cdot 10^6$ by squaring $1024=1000+24$.)

So, $2^m > 10^6$ iff $m \ge 20$.

Adding the restriction $m\le 95$ gives $95-20+1=76$ possible factors.