<s>[INST] Sum of digits of $2^n - k$ in binary Denote the sum of digits of $n$ in binary as $s_2(n)$.
Trying to figure the relation $f(n,k) = s_2(2^n - k)$ for positive integers $n,k$ such that $2^n > k$. I see no pattern here and was thinking there should be at least a good lower bound as a function of $n,k,s_2(k)$.
It is clear from binary addition that $s_2(2^n + k) = s_2(k) + 1$.
Can we get some formula for $f(n,k)$ or at least lower bounds if not known?
E.g for $n=3$ we have:
If $k=1$ then $s_2(2^3-1)=s_2(7) = 3$
If $k=2$ then $s_2(2^3-2)=s_2(6) = 2 $
If $k=3$ then $s_2(2^3-3)=s_2(5) = 2$
If $k=4$ then $s_2(2^3-4)=s_2(4) = 1$
If $k=5$ then $s_2(2^3-5)=s_2(3) = 2$
If $k=6$ then $s_2(2^3-6)=s_2(2) = 1$
If $k=7$ then $s_2(2^3-7)=s_2(1) = 1$
 [/INST] Note that
$$
s_2((2^n-1)-k)=n - s_2(k),
$$
since subtracting from $11\cdots 1$ has the effect of complementing every bit of $k$. Therefore,
$$
s_2(2^n-k)=s_2((2^n-1)-(k-1))=\boxed{n-s_2(k-1).}
$$
</s>