Let $\displaystyle S$ be the set of all positive integers $\displaystyle n$ not exceeding $\displaystyle 1 000 000$ such that $\displaystyle n \equiv 4 \pmod{8}$, that is, $\displaystyle S = \{4,12,20,28,\ldots,999996\}$.

How many of the elements of $\displaystyle S$ can be written as the sum of the three integer squares?

A theorem says that $\displaystyle n$ can be written as sum of three integer squares iff $\displaystyle n \ne 4^k (8m + 7)$ for non-negative integers $\displaystyle k,m$.

So $\displaystyle n = 8x - 4$ can be written as sum of three integer squares iff $\displaystyle n = 8x - 4 \ne 4^k (8m + 7)$, or in another word when $\displaystyle 8x - 4 = 4^k (8m + 7)$ with variable $\displaystyle x$ has no integer solution.

$\displaystyle x = 4^km + \frac{4^k \timex 7}{8} - \frac{1}{2}$ is not an integer when $\displaystyle k > 1$, and is an integer when $\displaystyle k = 0,1$.

Work out how many $\displaystyle n$ CANNOT be written as sum of three integer squares.

When $\displaystyle k = 0$, $\displaystyle n = 8m + 7 \equiv 7 \pmod{8}$ are not in $\displaystyle S$.

When $\displaystyle k = 1$, $\displaystyle n = 4(8m + 7) = 32m + 28 \equiv 4 \pmod{8}$ are in $\displaystyle S$.

We require $\displaystyle n = 4(8m + 7) \leq 1000000$ or $\displaystyle m \leq 31249$, hence there are $\displaystyle 31250$ elements in$\displaystyle S$ that cannot be written as sum of three integer squares.

There are $\displaystyle 124999$ elements in $\displaystyle S$, hence $\displaystyle 124999-31250 = 93749$ elements can be written as sum of three integer squares.