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.

Assume $k$ and $n$ are non-negative integers and define $f(k,n)$ to be the index of the $k$th least significant set bit and define $f(k,n) = 0$ if $n$ has fewer than $k$ set bits. For example, if $k=2$ and $n=88 = 1011000 \text{ (base } 2)$, then $f(k,n)= 4$. How can you compute the asymptotics of

$$S_{n,k} = \sum_{i=0}^n 2^{f(k,i)} \, ?$$

For $k=1$ and $n = 0\dots10$, we get $1, 2, 4, 5, 9, 10, 12, 13, 21, 22, 24$.

For $k=2$ and $n = 0\dots10$, we get $1, 2, 3, 5, 6, 10, 14, 16, 17, 25, 33$

share|improve this question
add comment

1 Answer

If in the $N$-bit number the $k$'th lest significant bit sits int the position $m$, there are exactly $k-1$ bits in the positions $0 \to m-1$, therefore, there are exactly $2^{N-m-1}* (^{m-1}_{k-1})$ such numbers, each contributing $2^{N-1}* (^{m-1}_{k-1})$ to the total.

Can you take it from here?

share|improve this answer
    
This isn't obvious to me. For fixed $k$ do you get something like $n\log^{k}{n}$? However we know it can't be more than $\sum_{i=0}^n (i+1)$ so that can't be the full solution. –  marshall Feb 14 at 11:21
add comment

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.