Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sum of 2^k less than r

  1. May 14, 2013 #1
    Assume [itex]n\in\mathbb{N}[/itex] and [itex]r\in\mathbb{R}[/itex] are some fixed constants and [itex]r>0[/itex]. I want to find some nice lower bound for the amount of elements [itex](k_1,k_2,\ldots,k_n)\in\mathbb{N}^n[/itex] such that [itex]2^{k_1}+\cdots + 2^{k_n}\leq r[/itex].

    In other words, if we define a function

    f:\mathbb{N}^n\to\mathbb{R},\quad f(k_1,\ldots, k_n)=2^{k_1}+\cdots + 2^{k_n}

    I want to find some nice formula for a some reasonably large quantity [itex]\varphi(r,n)[/itex] such that

    \varphi(r,n)\leq \# f^{-1}([1,r])

    where # means the number of elements in the set.

    I tried to approximate some sums as integrals, but didn't get anywhere.

    The special case [itex]n=1[/itex] easy. The number of elements [itex]2^0,2^1,2^2,\ldots[/itex] which are less than [itex]r[/itex] is


    where [itex]x\mapsto [x][/itex] is the floor function defined by [itex][x]=j\in\mathbb{Z}[/itex] and [itex]j\leq x < j+1[/itex].

    So if we want [itex]\varphi(r,1)[/itex] "nice", it could be made differentiable by setting

    \varphi(r,1) = \frac{\log(r)}{\log(2)}.
    Last edited: May 14, 2013
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted