<s>[INST] $f(n) = f(2n)$, and $f(2n + 1) = f(n) + 1$, find expression of such $f$ The question is
a. $f(n) = f(2n)$
b. $f(2n + 1) = f(n) + 1$,
with $f(1)=1$, find expression of such $f$ that defined on positive integers
Got an initial idea about the pattern but find the difficulty to find the exact form. It's related to exponent of 2 (obviously). the number of times it can be expressed as addition of 2 exponents
for example, for $13 = 2^3+2^2+2^0, f(13) = 3$
and $16=2^4, f(16)=1; 15 = 2^3+2^2+2^1+2^0, f(15)=4$
in other words, it's the sum of all digits in its binary form, right? if so what's the formula of it.
during such time as I wrote my thoughts down, it seems I come up with a formula
$$a-\sum_{i=1}^\infty  \lfloor a/2^i\rfloor.$$
which seems to be the answer to the question
 [/INST] Expanding on my comment, let the binary representation of $a$ be $\,\overline{a_na_{n-1}\dots a_1a_0}\,$ with $\,a_k \in \{0,1\}\,$, then $\,a = \sum_{k \ge 0} 2^k a_k\,$ and $\,a_k = \left\lfloor \frac{a}{2^k}\right\rfloor \bmod 2\,$, so the sum of binary digits can be written as $\,\sum_{k \ge 0} \left(\left\lfloor \frac{a}{2^k}\right\rfloor \bmod 2\right)\,$.
Using the identity $\,n \bmod 2 = n - 2 \left\lfloor \frac{n}{2} \right\rfloor\,$ leads to the form in OP's question:
$$
\require{cancel}
\begin{align}
\sum_{k \ge 0} \left(\left\lfloor \frac{a}{2^k}\right\rfloor \bmod 2\right) &= \sum_{k \ge 0} \left( \left\lfloor \frac{a}{2^k}\right\rfloor - 2 \left\lfloor \frac{a}{2^{k+1}}\right\rfloor \right)
\\ &= \sum_{k \ge 0} \left( \left\lfloor \frac{a}{2^k}\right\rfloor - \left\lfloor \frac{a}{2^{k+1}}\right\rfloor \right) - \sum_{k \ge 0} \left\lfloor \frac{a}{2^{k+1}}\right\rfloor
\\ &= \left(\left\lfloor \frac{a}{2^0}\right\rfloor - \cancel{\left\lfloor \frac{a}{2^1}\right\rfloor} + \cancel{\left\lfloor \frac{a}{2^1}\right\rfloor} - \bcancel{\left\lfloor \frac{a}{2^2}\right\rfloor}  + \bcancel{\left\lfloor \frac{a}{2^2}\right\rfloor} - \dots\right) - \sum_{k \ge 1} \left\lfloor \frac{a}{2^{k}}\right\rfloor
\\ &= a - \sum_{k \ge 1} \left\lfloor \frac{a}{2^{k}}\right\rfloor
\end{align}
$$
</s>