# Powers of $2$ or $3$ from $m$ to $n$

Is there a formula for finding how many powers of $2$ or $3$ exist in a given range of numbers say $m$ through $n$ or $0$ through $n$?

-
That's the same as the number of integers in $[\log_2 m, \log_2 n]$ (and similarly for $3$). – Srivatsan Sep 15 '11 at 16:26
In short: $\lfloor\log_b n\rfloor-\lceil\log_b m\rceil+1$. – J. M. Sep 15 '11 at 16:32
@Sri: So that's $\lfloor \log_2(n) \rfloor - \lceil \log_2(m) \rceil + 1$ if I'm not mistaken. And Kedar: If $m = 0$ then you will find infinitely many solutions, as $0 < 2^{-n} < 1$ for all $n = 1, 2, \ldots$. – TMM Sep 15 '11 at 16:33
@Kedar Your question now seems slightly ambiguous. See my answer and Eric's answers for 2 different interpretations. Can you clarify what you had in mind? – Srivatsan Sep 15 '11 at 16:48

ADDED: I am taking the phrase "powers of $2$" to mean nonnegative integral powers $\{1,2,4, \ldots\}$.

Assume that $n \geq m \geq 1$. (If $m =0$, then you can safely redefine it to be $1$.) Notice that $2^k \in [m,n] \iff k \in [\log_2 m, \log_2 n]$. Further, if $k$ is an integer, then1: $$2^k \in [m,n] \iff k \in [\ \lceil \log_2 m \rceil, \lfloor \log_2 n\rfloor \ ].$$ Be careful with the floors and ceilings. Therefore the number of powers of two in the given range is: $$\lfloor \log_2 n\rfloor - \lceil \log_2 m \rceil + 1.$$

Proceed similarly for $3$.

1This is because of the following facts. If $k$ is an integer and $x$ real, then $k \leq x$ is equivalent to saying $k \leq \lfloor x \rfloor$. Similarly, $k \geq x \iff k \geq \lceil x \rceil$.

-

If you are looking for numbers composed only from the primes $2$ and $3$ (For $n\leq 10$ this would be $2,3,4,6,8,9$) then see this Math Stack Exchange thread. It turns out there are approximately $$\frac{1}{2} \left(\frac{\log N}{\log 2} + 1\right)\left(\dfrac{\log N}{\log 3} + 1\right).$$

(Counting lattice points in the triangle)

-
Hmm, that's a good catch! :) – Srivatsan Sep 15 '11 at 16:47