# An IMO inspired problem

This problem from IMO 1988 is said to be one of the most elegant ones in functional equations.

Problem : The function $f$ is defined on the set of all positive integers as follows: \begin{align} f(1) = 1, f(3) &= 3, f(2n) = f(n), \\ f(4n+1) &= 2f(2n+1) - f(n), \\ f(4n+3) &= 3 f(2n+1) - 2f(n) \end{align} Find the number of $n$ with $f(n) = n, 1 \leq n \leq 1988$.

The main idea towards the solution is realizing that these conditions stand for the fact that $f(n)$ just reverses the digits in the binary representation of the number $n$. So, essentially the solution is finding the number of binary pallindromes $\leq 1988_{10}$.

My question is the following: How to reformulate the problem so that $f(n)$ reverses the digits of $n$ in its ternary representation. Or even better, can we reformulate it for a general base $k$?

Thanks.

In general for base $k$:
\eqalign{f(kn ) &= f(n)\cr f(k^2 n + a k + b) &= k f(kn+b) + a f(kn+1) - (k - a -1) f(n)\cr} for $a = 0, \ldots, k-1$, $b = 1, \ldots, k-1$.