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$?
Powers of $2$ or $3$ from $m$ to $n$
-
1That's the same as the number of integers in $[\log_2 m, \log_2 n]$ (and similarly for $3$). – 2011-09-15
-
1In short: $\lfloor\log_b n\rfloor-\lceil\log_b m\rceil+1$. – 2011-09-15
-
0@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$. – 2011-09-15
-
0@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? – 2011-09-15
2 Answers
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)
-
1Hmm, that's a good catch! :) – 2011-09-15