(a) $2k$ and $k$ have the same number of digits $1$ in their binary expansions, so from our point of view, passing from $k$ to $k+1$ is just like adding $2k+1$ to our list of numbers. This means that $f$ is a nondecreasing function which increases with at most $1$ at each step. Since $f(4)=1$, it means that $f$ does indeed take all positive integer values. (b) $|f^{-1}(m)|=1$ is equivalent to both $2k-1$ and $2k+1$ having three $1$'s in their binary expansion. This, in turn, is equivalent to $k=2+2^a,\ a\ge 2$, as can easily be shown. This means that $\{k+1,\ldots,2k\}=\{1+2+2^a,\ldots,4+2^{a+1}\}$, and it's clear from here that $m=f(k)=f(2^a)+1$. All numbers between $2^a+1$ and $2^{a+1}-1$ have a $1$ on the first position, so they have three $1$'s iff they have two $1$'s on the other $a$ positions. There are $\frac{a(a-1)}2$ ways in which this can happen, so $m=f()=f(2^a)+1=\frac{a(a-1)}2+1$, so the answer to (b) is: the numbers $m=\frac{a(a-1)}2+1,\ a\ge 2$.

for a), a little bit more is needed: you have to prove $f$ never becomes constant. the opposite can be disproved by showing that if $n$ is odd and has three $1$ digits in its binary representation then so does $2n-1$ (this is easy). But clearly $2n$ does as well. So from going to $f(n-1)$ to $f(n)$, you lose $n$ from your count but you also gain both $2n$ and $2n-1$. So $f(n)=f(n-1)+1$ meaning $f$ never becomes constant since there for all $k$, there exists $n>k$ such that $n$ is odd and has three 1 digits in its representation (put two $1$ digits at the start, then a sufficiently long enough string of $0$ digits afterwards, then have the final digit $1$).

Sketch: Define the indicator function $I(k) = 1$ if $k$ has $3$ bits and otherwise $I(k) = 0$. One can then derive that $f(k) = \sum_{i=1}^{k}I(2i-1)$. Since $I(k)$ increases by at most $1$ at each step, and $I(k)$ is unbounded (i.e there are infinitely many odd integers with $3$ bits), part $a$ is proved. For part $b$, we can start by listing out all the odd numbers that have $3$ bits and look for ones that differ by $2$ to capture $f(k)$ at these points. We find that $m=\binom{n}{2} + 1$ for $n \geq 2$ is the necessary condition.