IMO 2J, Independent Study 2

Let $g(n) = k$. Then $f(n) = 2^k - 1$, and so we just need to determine all $k$ such that $(2^k - 1)^k$ has $k$ 1's in its binary representation. To do this, we can simply expand
$$(2^k - 1)^k = \sum_{i=0}^{k} (-1)^i \binom{k}{i} 2^{k^2 - ki} = \sum_{i=0}^{\lfloor \frac{k-1}{2} \rfloor} \binom{k}{2i} 2^{k^2 - 2ki} - \binom{k}{2i+1} 2^{k^2 - 2ki - k} + ((k+1) \bmod 2).$$
Here $(k+1) \bmod 2$ is 1 if $k$ is even and 0 if $k$ is odd. Write $s(k, i)$ for
$$\binom{k}{2i} 2^{k^2 - 2ki} - \binom{k}{2i+1} 2^{k^2 - 2ki - k}$$
Then we know that
$$s(k, i) < 2^k 2^{k^2 - 2ki} = 2^{k^2 - (2i-1)k},$$
and we also know that $2^{k^2 - (2i+1)k}$ divides $s(k, i)$. Therefore
$$f((2^k - 1)^k) = \sum_{i=0}^{\lfloor \frac{k-1}{2} \rfloor} f(s(k, i)) + ((k + 1) \bmod 2).$$
Since $s(k,i)/2^{k^2-(2i+1)k} \equiv -\binom{k}{2i+1} \bmod 2^k$, we know that $f(s(k,i)) = f(s(k,i)/2^{k^2-(2i+1)k})$ is at least
$$k - \left\lfloor \log_2 \binom{k}{2i+1} \right\rfloor.$$
Now we can proceed in two ways.

Approach 1. If $k \ge 3$, then we get
$$s(k, 0) + s(k, 1) \ge 2k - \lfloor \log_2 k \rfloor - \left\lfloor \log_2 \binom{k}{3} \right\rfloor > 2k - 4 \log_2 k$$
Therefore $4 \log_2 k > k$ and so $k < 16$. Now, plugging in
$$k \ge 2k - \lfloor \log_2 k \rfloor - \left\lfloor \log_2 \binom{k}{3} \right\rfloor$$
for $k < 16$, we get $k = 4, 5, 6, 7, 8, 9$ and the equality holds in all cases.

However, when $k \ge 5$ we have
$$f((2^k - 1)^k) > f(s(k, 0)) + f(s(k, 1)) + f(s(k, 2)) \ge k + 1,$$
which is a contradiction. When $k = 4$, we have $f(15^4) \ge s(4, 0) + s(4, 1) + 1 > 5$. Therefore, we reach a contradiction from $k \ge 3$, showing that $k < 3$ must hold. It is clear that $k = 1, 2$ both work and we get $n = 1, 9$. $\square$

Approach 2. It is clear that $k = 1, 2$ both work, so we will assume that $k \ge 3$ from now on. If $k$ is odd, then we have $s(k, (k-1)/2) = k \cdot 2^k - 1$, showing that $f(s(k, (k-1)/2)) \ge k$. We also have $f(s, 0) \ge 1$, so we already get a contradiction. Therefore, $k$ must be even, and we have $f(s(k, 0)), f(s(k, k/2-1)) \ge k - \lfloor \log_2 k \rfloor$. Thus, $2 \lfloor \log_2 k \rfloor \ge k$, and we get $k = 4$. However, it is easy to compute that $f(15^4) \ne 4$, showing that $k \ge 3$ does not work at all. $\square$