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

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.

Re: How many elements of S can be written as the sum of three integer squares?

Your solution seems correct. However, $\displaystyle S$ contains 125,000 elements, not 124,999 (you have to add 1 b/c you have an inclusive set). So the answer should be 93,750.

Re: How many elements of S can be written as the sum of three integer squares?

Thank you. You are right. $\displaystyle S$ does contain 125000 elements.

Re: How many elements of S can be written as the sum of three integer squares?

it appears that i agree with your answer, although i do not know how you can conclude that x is an integer when k = 0. for then:

x = m + 7/8 - 1/2 = m + 3/8, which is *not* an integer.

Re: How many elements of S can be written as the sum of three integer squares?

$\displaystyle k$ cannot be zero (because every integer in $\displaystyle S$ is congruent to 4 mod 8).

Re: How many elements of S can be written as the sum of three integer squares?

i am saying that when k = 0, x is not even an integer.

look, when k = 0, 8x - 4 = 8m + 7

8(x - m) = 11 ---> x - m is not an integer ---> x is not an integer.

Re: How many elements of S can be written as the sum of three integer squares?

You guys are right. I have got the details wrong about $\displaystyle k = 0$. Thank you guys for pointing it out and explaining.