3. Define the function $f$ on the positive integers such that

$$
f(1)=1, \quad f(3)=3
$$

and

$$
\begin{aligned}
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 the number of integers $n$ in the range $1 \leq n \leq 1988$ for which $f(n)=n$ holds.
Let's notice that if we read the binary digits of $n$ in reverse (from right to left), we get $f(n)$! We will prove this statement by complete induction on $n$. Clearly:

$$
f(1)=1, f(2)=1, f(3)=3, f(4)=1 .
$$

Assume the statement is true up to $(n-1)$, and prove it for $n$.

a) If $n=2 k$, let $f(k)=z$.

$$
f(n)=f(2 k)=f(k)=z
$$

b) If $n=4 k+1$, let $2^{t-1} \leqq k<2^{t}$, and $f(k)=z$,

$$
f(n)=2 f(2 k+1)-f(k)=2 \cdot\left(2^{t+1}+z\right)-z=2^{t+2}+z
$$

c) If $n=4 k+3$, let $2^{t-1} \leqq k<2^{t}$, and $f(k)=z$,

$$
f(n)=3 f(2 k+1)-2 f(k)=3 \cdot\left(2^{t+1}+z\right)-2 z=3 \cdot 2^{t+1}+z
$$

The solutions to the problem are thus the numbers between 1 and 1988, which, when written in binary, read the same backwards. These are called palindromic numbers. Let's count them.

In binary, a palindromic number with $2 n$ digits has $2^{n-1}$ possibilities, because the first digit is 1, and from the second to the $n$-th place, 0 or 1 can stand, which gives $2^{n-1}$ possibilities, and the last $n$ digits are uniquely determined.

Similarly, a palindromic number with $2 n+1$ digits has $2^{n}$ possibilities.

1988 in binary is: 11111000100 (11 digits). All palindromic numbers with up to 10 digits are smaller. Their number is 62. 1988 falls between the 11-digit palindromic numbers $1967=11110101111$ and $2015=11111011111$, so the number of 11-digit palindromic numbers smaller than 1988 is 30.

Therefore, the problem has a total of $92$ solutions.