HMMT February

Solution:
Answer: $1.813759629294 \cdot 10^{12}$

Rewrite the sum as
$$\sum_{x^{2}+x y+y^{2} \leq 10^{6}}\left(x^{2}+x y+y^{2}\right),$$
where the sum is over all pairs $(x, y)$ of integers with $x^{2}+x y+y^{2} \leq 10^{6}$. We can find a crude upper bound for this sum by noting that
$$x^{2}+x y+y^{2}=\frac{3}{4} x^{2}+\left(\frac{x}{2}+y\right)^{2} \geq \frac{3}{4} x^{2}$$
so each term of this sum has $|x| \leq \frac{2}{\sqrt{3}} 10^{3}$. Similarly, $|y| \leq \frac{2}{\sqrt{3}} 10^{3}$. Therefore, the number of terms in the sum is at most
$$\left(\frac{4}{\sqrt{3}} 10^{3}+1\right)^{2} \approx 10^{6}$$
(We are throwing away "small" factors like $\frac{16}{3}$ in the approximation.) Furthermore, each term in the sum is at most $10^{6}$, so the total sum is less than about $10^{12}$. The answer $1 \cdot 10^{12}$ would unfortunately still get a score of 0.

For a better answer, we can approximate the sum by an integral:
$$\sum_{x^{2}+x y+y^{2} \leq 10^{6}}\left(x^{2}+x y+y^{2}\right) \approx \iint_{x^{2}+x y+y^{2} \leq 10^{6}}\left(x^{2}+x y+y^{2}\right) d y d x$$
Performing the change of variables $(u, v)=\left(\frac{\sqrt{3}}{2} x, \frac{1}{2} x+y\right)$ and then switching to polar coordinates $(r, \theta)=\left(\sqrt{u^{2}+v^{2}}, \tan ^{-1}(v / u)\right)$ yields
$$\begin{aligned} \iint_{x^{2}+x y+y^{2} \leq 10^{6}}\left(x^{2}+x y+y^{2}\right) d y d x & =\frac{2}{\sqrt{3}} \iint_{u^{2}+v^{2} \leq 10^{6}}\left(u^{2}+v^{2}\right) d v d u \\ & =\frac{2}{\sqrt{3}} \int_{0}^{2 \pi} \int_{0}^{10^{3}} r^{3} d r d \theta \\ & =\frac{4 \pi}{\sqrt{3}} \int_{0}^{10^{3}} r^{3} d r \\ & =\frac{\pi}{\sqrt{3}} \cdot 10^{12} \end{aligned}$$
This is approximately $1.8138 \cdot 10^{12}$, which is much closer to the actual answer. (An answer of $1.8 \cdot 10^{12}$ is good enough for full credit.)

The answer can also be computed exactly by the Common Lisp code:
```
(defconstant +MAX+ 1e6)
(defvar +lower+ -2000)
(defvar +upper+ 2000)
(princ
(loop for x from +lower+ to +upper+ sum
(loop for y from +lower+ to +upper+
sum
(let ((S (+ ( x x) ( x y) (* y y))))
(if (and (<= S +MAX+) (> S 0)) S 0))))
```