Una de la OMI inspirado problema

Question

Este problema de la OMI 1988 es uno de los más elegantes en las ecuaciones funcionales.

Problema : La función de $f$ se define en el conjunto de todos los enteros positivos de la siguiente manera: \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} Encontrar el número de $n$$f(n) = n, 1 \leq n \leq 1988$.

La idea principal hacia la solución es darse cuenta de que estas condiciones de soporte para el hecho de que $f(n)$ sólo invierte los dígitos en la representación binaria del número de $n$. Así que, esencialmente, la solución es encontrar el número de binario pallindromes $\leq 1988_{10}$.

Mi pregunta es la siguiente: ¿Cómo reformular el problema, por lo que el $f(n)$ invierte los dígitos de $n$ en su ternario de la representación. O mejor aún, podemos reformular para una base general $k$?

Gracias.

Answer 1

En general, en base a $k$:

$$ \eqalign{f(kn ) &= f(n)\cr f(k^2 n + k + b) y= k f(kn+b) + a f(kn+1) - (k -1) f(n)\cr}$$ para $a = 0, \ldots, k-1$, $b = 1, \ldots, k-1$.