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$
-
0@Kedar Your question now seems slightly ambiguous. See my answer and Eri$c$'s answers for 2 different interpretations. Can you $c$larify 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