$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
 A: 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}
$$
A: By successive division by $2$ you get:

*

*$f(2^nx)=f(2^{n-1}x)=\cdots=f(x)$


*$f(2^n(2x+1))=f(2x+1)=f(x)+1$
Also we will need $f(0)$:

*

*$f(1)=f(1+2\times 0)=f(0)+1$ and since $f(1)=1$ then $f(0)=0$
Let's write $n$ in its binary form $n=\sum\limits_{i=1}^M 2^{\alpha_i}$ with $\alpha_i>\alpha_j$ for $i>j$
Said otherwise $n$ has $M$ bits set to $1$.
Then notice that $n=2^{\alpha_1}(1+\sum\limits_{i=2}^M 2^{\alpha_i-\alpha_1})=2^{\alpha_1}(1+2\underbrace{\sum\limits_{i=2}^M 2^{\alpha_i-\alpha_1-1}}_x)$
Since $\alpha_i>\alpha_1\iff \alpha_i\ge \alpha_1+1\iff \beta_i=\alpha_i- \alpha_1-1\ge 0$ then $x=\sum\limits_{i=2}^M 2^{\beta_i}$
And you have your induction on the value of $M$ i.e. $f(n)=f(x)+1$ with $x<n$ having $M-1$ bits set to $1$.
The process terminates when the next number is $0$ aka. $M-M=0$ bits set to $1$, which corresponds to $f(n)=\underbrace{f(0)}_0+\underbrace{1+1+\cdots+1}_\text{M terms}=M=\operatorname{bitcount}(n)$.

Here is an alternative approach we will show that $f$ and bitcount coincide on all integers:
Let define $g(n)=f(n)-\operatorname{bitcount}(n)$
It is not difficult to show that $\operatorname{bitcount}$ obeys the same relations than $f$, indeed a multiplication by $2$ just shift all the bits to the left and add a zero to the right, this doesn't change the bitcount so $\operatorname{bitcount}(2n)=\operatorname{bitcount}(n)$. And for $2n+1$ it is not a zero we add to the right but a one, so the bit count is raised by $1$ and $\operatorname{bitcount}(2n+1)=\operatorname{bitcount}(2n)+1=\operatorname{bitcount}(n)+1$.
We have $g(0)=g(1)=0$ to start our induction and we will assume it is true up to $n$.

*

*$n=2p$ then $g(n+1)=f(2p+1)-\operatorname{bitcount}(2p+1)=(f(p)+1)-(\operatorname{bitcount}(p)+1)=g(p)=0$ by induction since $p<n$.


*$n=2p+1$ then $g(n+1)=f(2p+2)-\operatorname{bitcount}(2p+2)=f(p+1)-\operatorname{bitcount}(p+1)=g(p+1)=0$ by induction since $p+1<n$.
This terminates our induction and we conclude $g(n)=0$ for all $n$.

Finally here is a computational expression of $f$ (& is the bitwise AND operator):
$f(n)=\min\{\ i\mid u_i=0\text{ where } u_0=n,\ u_{i+1}=u_i \mathbin{\&} (u_i-1)\}$
