Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
1  
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
1  
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

2 Answers 2

up vote 4 down vote accepted

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$.

share|improve this answer

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)

share|improve this answer
1  
Hmm, that's a good catch! :) –  Srivatsan Sep 15 '11 at 16:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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