Note: this is not a duplicate of this post.
Consider the function $f:\mathbb{Z^+}\to\mathbb{Z^+}$, where $\mathbb{Z^+}$ denotes the positive integers, defined by:
$$ f(n)=3^n+3n, $$
and the function $g$, also $\mathbb{Z^+}\to\mathbb{Z^+}$, that counts the amount of $1$s in the binary expansion of a given positive integer.
Then what is:
$$ g(f(n))? $$
In general, if one defines the function:
$$ f_{k}(n)=k^n+kn, $$
how may one find:
$$ g(f_k(n))? $$
EDIT: I understand this is a hard problem. Consider then instead the function $g'$ defined as follows:
$$ g'(n) = \begin{cases} 1 & \rm {if }\ \ g(n)\equiv0\mod2, \\ 0 & \rm {otherwise }, \end{cases} $$
i.e., $g'$ is equal to $1$ if the amount of $1$s in the binary expansion of $n$ is even, and $0$ otherwise. Is finding $g'$ easier than finding $g$?
I doubt there is a simple exact formula. You can get an approximation by noting that $3^n$ has $\lceil \log_2 3^n \rceil$ bits and guessing that half will be $1$s. This gives $n\frac {\log_2 3}2$ one bits. The $+3n$ will affect only the bottom few bits, so is not important when $n$ is large. The extension to $k$ is $n \frac {\log_2 k}2$