A function $f$ from $\mathbb{Z}$ to $\{1, \ldots, 1000\}$ is said to be interesting if for all integers $x$ and $y$, we have

$$
\operatorname{gcd}(f(x), f(y))=\operatorname{gcd}(f(x), x-y)
$$

How many interesting functions exist?
Let $f$ be a potentially interesting function, and let $n$ be the LCM of the integers $f(x)$, and

$$
n=\prod_{i=1}^{r} p_{i}^{\alpha_{i}}
$$

be a factorization of $n$ into prime factors. For any integer $i \leqslant r$, we are given an integer $x_{i}$ such that $p^{\alpha_{i}}$ divides $f\left(x_{i}\right)$. The Chinese Remainder Theorem indicates that there exists a residue $n$ modulo $n$ such that $m \equiv x_{i}\left(\bmod p_{i}^{\alpha_{i}}\right)$ for all $i$. We then verify that $p_{i}^{\alpha_{i}}$ divides $\operatorname{GCD}\left(f\left(x_{i}\right), x_{i}-\right.$ $m)=\operatorname{GCD}\left(f\left(x_{i}\right), f(m)\right)$, so that $f(m)$ is divisible by each of the factors $p_{i}^{\alpha_{i}}$, and thus by $n$ itself.

Consequently, for any integer $x$, and since $f(x)$ divides $n=f(m)$, we know that

$$
f(x)=\operatorname{GCD}(f(m), f(x))=\operatorname{GCD}(f(m), m-x)=\operatorname{GCD}(n, x-m) .
$$

Conversely, if we denote $f_{m, n}$ as the function defined by $f_{m, n}: x \mapsto \operatorname{GCD}(n, x-m)$, we observe that

$\operatorname{GCD}\left(f_{m, n}(x), f_{m, n}(y)\right)=\operatorname{GCD}(n, x-m, y-m)=\operatorname{GCD}(n, x-m, x-y)=\operatorname{GCD}(f(x), x-y)$.

Thus, each function $f_{m, n}$ is interesting.

Finally, if two functions $f_{m, n}$ and $f_{m^{\prime}, n^{\prime}}$ coincide, we know that $n$ and $n^{\prime}$ are both equal to the LCM of the integers $f m, n(x)=f_{m^{\prime}, n^{\prime}}(x)$ obtained when $x \in \mathbb{Z}$, so that $n=n^{\prime}$. But then $n=f_{m, n}(n)=f_{m^{\prime}, n}(n)=\operatorname{GCD}\left(n, m-m^{\prime}\right)$, so $n$ divides $m-m^{\prime}$; conversely, if $n$ divides $m-m^{\prime}$, the functions $f_{m, n}$ and $f_{m^{\prime}, n}$ coincide.

Therefore, we have as many distinct interesting functions as there are pairs $(n, m)$ with $n \in$ $\{1, \ldots, 1000\}$ and $m \in\{1, \ldots, n\}$, which gives us a total of

$$
\sum_{n=1}^{1000} n=\frac{1000 \times 1001}{2}=500500
$$

interesting functions.

Alternative solution:

We will first prove that, for all integers $u$ and $v$, there exists an integer $w$ such that $\operatorname{lcm}(f(u), f(v))$ divides $f(w)$. Indeed, let $d=\operatorname{gcd}(f(u), f(v))$, then $x=f(u) / d$ and $y=f(v) / d$. Since $d=\operatorname{gcd}(f(u), v-u)=\operatorname{gcd}(f(v), v-u)$, there exists an integer $z$, coprime with $x$ and $y$, such that $v-u=d z$.

The Chinese Remainder Theorem indicates that there exists an integer $s$ such that $s \equiv 0(\bmod x)$ and $s \equiv z(\bmod y)$. If we set $w=u+d s$, we then observe that

$$
\left\{\begin{array}{l}
\operatorname{gcd}(f(u), f(w))=\operatorname{gcd}(d x, w-u)=\operatorname{gcd}(d x, d s)=d x \text { and } \\
\operatorname{gcd}(f(v), f(w))=\operatorname{gcd}(d y, w-v)=\operatorname{gcd}(d y, d(s-z))=d y .
\end{array}\right.
$$

Thus, $f(w)$ is divisible by $d x$ and by $d y$, i.e., by $\operatorname{lcm}(f(u), f(v))$.

Now, let $a$ be an integer for which $f(a)$ is maximal. For any integer $b$, the image of $f$ contains a multiple of $\operatorname{lcm}(f(a), f(b))$, and this multiple is both divisible and bounded by $f(a)$, so it is equal to $f(a)$. Thus, $f(b)$ divides $f(a)$, and the image of $\mathbb{Z}$ by $f$ contains only divisors of $f(a)$. In particular, for any integer $x$,

$$
f(x)=\operatorname{gcd}(f(a), f(x))=\operatorname{gcd}(f(a), x-a),
$$

and the integers $x$ for which $f(x)=f(a)$ are those such that $x \equiv a(\bmod f(a))$. Thus, $f(a)$ has a unique preimage by $f$ in $\{1,2, \ldots, f(a)\}$, and $f$ is characterized by the choice of $f(a)$ and this preimage.

Conversely, any function of this form works, because

$$
\begin{aligned}
\operatorname{gcd}(f(x), f(y)) & =\operatorname{gcd}(\operatorname{gcd}(f(a), f(x)), \operatorname{gcd}(f(a), f(y))) \\
& =\operatorname{gcd}(\operatorname{gcd}(f(a), x-a), \operatorname{gcd}(f(a), y-a)) \\
& =\operatorname{gcd}(f(a), x-a, y-a) \\
& =\operatorname{gcd}(f(a), x-a, x-y) \\
& =\operatorname{gcd}(\operatorname{gcd}(f(a), x-a), x-y) \\
& =\operatorname{gcd}(\operatorname{gcd}(f(a), f(x)), x-y) \\
& =\operatorname{gcd}(f(x), x-y) .
\end{aligned}
$$

In conclusion, when we want to construct an interesting function, we have 1000 choices for $f(a)$, and then $f(a)$ choices for the smallest integer $a \geqslant 1$ possible, which gives us a total of

$$
\sum_{k=1}^{1000} k=1000 \times 1001 / 2=500500
$$

interesting functions.