15
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.