, 2017

Solution:
By plugging in $x=0$, we get that $f(0)$ can be either $-1,2$. As $f(0)$ is unrelated to all other values, we need to remember to multiply our answer by $2$ at the end. Similarly, $f(1)=-1$ or $2$.

Consider the graph $x \rightarrow x^{2}$. It is a binary tree rooted at $-1$, and there is an edge $-1 \rightarrow 1$, and a loop $1 \rightarrow 1$. Our first case is $f(1)=-1$. Note that if $x, y$ satisfy $x^{2}=y$, then $f(y) \neq 1$. Otherwise, we would have $f(x)^{2}=3 \pmod{17}$, a contradiction as $3$ is a nonresidue. So only the $8$ leaves can take the value $1$. This contributes $2^{8}$.

For $f(1)=2$, we can once again propagate down the tree. While it looks like we have $2$ choices at each node (for the square roots), this is wrong, as if $f(x)=-2$ and $y^{2}=x$, then $f(y)=0$ is forced.

Given this intuition, let $a_{n}$ denote the answer for a binary tree of height $n$ where the top is either $-2$ or $2$. Therefore, $a_{1}=2$, $a_{2}=5$. You can show the recurrence $a_{n}=a_{n-1}^{2}+2^{2^{n}-4}$. This is because if the top is $2$, then we get a contribution of $a_{n-1}^{2}$. If the top is $-2$, then both entries below it must be $0$. After that, you can show that each of the remaining $2^{n}-4$ vertices can be either of $2$ possible square roots. Therefore, we get the recurrence as claimed. One can compute that $a_{4}=5777$, so we get the final answer $2(256+5777)=12066$.