Uproot this recurrence

Let $f(x) = 4x(1 - x)$ . Observe that

$f^{-1} (0) = {0, 1}, f^{-1} (1) = {1/2}, f^{-1} [0, 1]) = [0, 1],$

and $|\{y : f(y) = x\}| = 2$ for all $x \in [0, 1)$ .

Let $A_n = \{x \in \mathbb{R} : f^n (x) = 0\}$ ; then

$\begin{aligned} A_{n + 1} &= \{x \in \mathbb{R} : f^{n + 1}(x) = 0\}\\ &= \{x \in \mathbb{R} : f^n(f(x)) = 0\} = \{ x \in \mathbb{R} : f(x) \in A_n\}. \end{aligned}$

We claim that for all $n \geq 1$ , $a_n \subset [0, 1]$ , $1 \in A_n$ , and

$|A_n| = 2^{n - 1} + 1.$

For $n = 1$ , we have

$A_1 = \{x \in \mathbb{R} | f(x) = 0\} = {0, 1},$

and the claim holds.

Now suppose $n \geq 1$ and $A_n \subset [0, 1], 1 \in A_n$ , and $|A_n| = 2^{n - 1} + 1$ . Then

$x \in A_{n + 1} \Rightarrow f(x) \in A_n \subset [0, 1] \Rightarrow x \in [0, 1],$

so $A_{n + 1} \subset [0, 1]$ .

Since $f(0) = f(1) = 0$ , we have $f^{n + 1} (1) = 0$ for all $n \geq 1$ , so $1 \in A_{n + 1}$ .

Now we have

\begin{aligned} |A_{n + 1}| &= |\{x : f(x) \in A_n\}|\\ &= \displaystyle \sum_{a \in A_n} |\{x : f(x) = a\}|\\ &= |\{x : f(x) = 1\}| + \displaystyle \sum_{\substack{a \in A_n \\ a \in [0, 1)}} |\{x : f(x) = a\}|\\ &= 1 + \displaystyle \sum_{\substack{a \in A_n \\ a \in [0, 1)}} 2\\ &= 1 + 2(|A_n| - 1)\\ &= 1 + 2(2^{n - 1} + 1 - 1)\\ &= 2^n + 1. \end{aligned}

Thus the claim holds by induction.

Finally, $a_{1998} = 0$ if and only if $f^{1997} (t) = 0$ , so there are $2^{1996} + 1$ such values of $t$ . Evaluating this in $\pmod {1000}$ , you arrive at an answer of $337$ .