positive integer values) is given by
$$
\begin{aligned}
f(1) & =1, \quad f(3)=3, \\
f(2 n) & =f(n), \\
f(4 n+1) & =2 f(2 n+1)-f(n), \\
f(4 n+3) & =3 f(2 n+1)-2 f(n),
\end{aligned}
$$
for all positive integers $n$. Determine with proof the number of positive integers less than or equal to 1988 for which $f(n)=n$.
26. The overline in this problem will exclusively denote binary representation. We will show by induction that if $n=\overline{c_{k} c_{k-1} \cdots c_{0}}=\sum_{i=0}^{k} c_{1} 2^{i}$ is the binary representation of $n\left(c_{i} \in\{0,1\}\right)$, then $f(n)=\overline{c_{0} c 1 \cdots c_{k}}=$ $\sum_{i=0}^{k} c_{i} 2^{k-i}$ is the number whose binary representation is the palindrome of the binary representation of $n$. This evidently holds for $n \in\{1,2,3\}$.

Let us assume that the claim holds for all numbers up to $n-1$ and show it holds for $n=\overline{c_{k} c_{k}-1 \cdots c_{0}}$. We observe three cases:
(i) $c_{0}=0 \Rightarrow n=2 m \Rightarrow f(n)=f(m)=\overline{0 c_{1} \ldots c_{k}}=\overline{c_{0} c_{1} \ldots c_{k}}$
(ii) $c_{0}=1, c_{1}=0 \Rightarrow n=4 m+1 \Rightarrow f(n)=2 f(2 m+1)-f(m)=$ $2 \cdot \overline{1 c_{2} \cdots c_{k}}-\overline{c_{2} \cdots c_{k}}=2^{k}+2 \cdot \overline{c_{2} \cdots c_{k}}-\overline{c_{2} \cdots c_{k}}=\overline{10 c_{2} \cdots c_{k}}=$ $\overline{a_{0} c_{1} \cdots c_{k}}$.
(iii) $c_{0}=1, c_{1}=1 \Rightarrow n=4 m+3 \Rightarrow f(n)=3 f(2 m+1)-2 f(m)=$ $3 \cdot \overline{1 c_{2} \ldots c_{k}}-2 \cdot \overline{c_{2} \cdots c_{k}}=2^{k}+2^{k-1}+3 \cdot \overline{c_{2} \cdots c_{k}}-2 \cdot \overline{c_{2} \cdots c_{k}}=$ $\overline{11 c_{2} \cdots c_{k}}=\overline{c_{0} c_{1} \cdots c_{k}}$.

We thus have to find the number of palindromes in binary representation smaller than $1998=\overline{11111000100}$. We note that for all $m \in \mathbb{N}$ the numbers of $2 m$ - and $(2 m-1)$-digit binary palindromes are both equal to $2^{m-1}$. We also note that $\overline{1111011111}$ and $\overline{11111111111}$ are the only 11-digit palindromes larger than 1998. Hence we count all palindromes of up to 11 digits and exclude the largest two. The number of $n \leq 1998$ such that $f(n)=n$ is thus equal to $1+1+2+2+4+4+8+8+16+16+32-2=92$.