Sum of 5 squares

Say two solutions to the equation, for some given n, are associated if one can be obtained from the other by some sign changes and a permutation of the terms. Clearly solutions being associated is an equivalence relation. It is clear we can vary the signs and positions of the numbers independently (e.g. by suffixing letters A, B, C, D and E to the numbers of some canonical solution).

We will show that most equivalence classes have size 0 mod 10. Since each class has nonzero terms, then choosing the signs will have an even number of choices, so it will be 0 mod 2.

Suppose not all of the $a_i$ in a solution are the same (in absolute value). So there is some number which occurs as exactly 1, 2, 3 or 4 of the $a_i$ . There are 5, 10, 10 or 5 (respectively) ways of choosing the slot the numbers of that absolute value fills, which is divisible by 5.

Hence, in this case the equivalence class is 0 mod 10, and we can ignore it.

Otherwise, the $a_i$ are the same, leaving 32 = 2 mod 10 possibilities for the sign.

If this happens, then $n = 5a^2$ , so a can take any value at most $\sqrt{\frac{5675}{5}}$ , which means that $1 \leq a \leq 33$ . All these values work, so there are 2*33 = 66 solutions.

Consider the correspondence $(a_1, a_2, a_3, a_4, a_5) \rightarrow (b_1, b_2, b_3, b_4, b_5)$ for $a_1^2+a_2^2+a_3^2+a_4^2+a_5^2 = n$ where $a_i^2 = b_i$ . Consider some set $(b_1, b_2, b_3, b_4, b_5)$ where for some $i=1, 2, 3, 4, 5$ , $i$ of the $b_k$ are equal to some value $a$ . Then there are $\binom{5}{i}$ ways to choose the $b_k$ that are equal, multiplied by $2^i$ ways to choose the signs of the corresponding $a_k$ (due to $a_k$ being allowed to be either the positive or negative squareroot of $b_k$ ), and then multiplied by the number of ways to write $n-ia$ as a sum of $5-i$ squares (let this be $c$ ). Then the number of such sets is clearly divisible by $10$ , as the number of such sets is $\binom{5}{i}2^ic$ which is both even and a multiple of $5$ for $1 \leq i \leq 4$ . Therefore these kinds of sets make no contribution to the last digit of $|T_n|$ and thus no contribution to $D_n$ .

Thus, it suffices to consider only those sets in which all of the $b_k$ are equal. Then $n$ is of the form $5a^2$ , and each $b_k$ is equal to $a^2$ , which means that the $a_k$ are equal to $\pm a$ . There are $2^5=32$ ways to choose the arrangement of possible signs, which means the number of such sets for this form of $n$ is equal to $32$ . So then $|T_n| = 10k+32$ for some $k$ , which means that $D_n=2$ .

It hence follows that if $n$ is not of the form $5a^2$ , then $D_n=0$ , and otherwise $D_n=2$ . Thus, it suffices to find the number of such $n$ . The number of integers of the form $5a^2$ under $5678$ is equal to $\left\lfloor \sqrt{\frac{5678}{5}}\right\rfloor = 33$ , and so we have $\displaystyle\sum_{k=1}^{5678} D_n = 2 \cdot 33 = \boxed{66}$

Suppose $a^2+b^2+c^2+d^2+e^2=n$ . This means that any permutation of $(\pm a,\pm b,\pm c,\pm d,\pm e)$ is a valid solution and is thus present in $T_n$ . Since at least one of $a,b,c,d,e$ is non-zero, $+a_i\ne-a_i$ for some element and thus the number of permutations is even, implying that $\left|T_n\right|$ is even.

Now, consider only the case when the elements which are $\ge 0$ . How many permutations of $(a,b,c,d,e)$ are distinct? The answer is $\frac{5!}{\prod_k m_k}$ where $m_k$ s are the multiplicities of elements (For example, $(a,a,a,b,b)$ has multiplicities 3 and 2). We note that this number is a multiple of 5 unless all elements are equal. This when compounded with the earlier result that the cardinality is even (flip the sigh of every number and we get another solution), we get that the number of solutions is a multiple of 10 unless the solution is of the type $(\pm a,\pm a,\pm a,\pm a,\pm a)$ .

So we just count the number of such solutions. $5\times 33^2 \le 5678 \le 5\times 34^2$ . Hence we have 33 values of $|a|$ . For each value of $|a|$ , there are 32 solutions when we consider the signs of all 5 elements. Hence the unit's digit contribution is 2. So the required answer is $33\times 2=6$ .

Every solution \­( (x,y,z,q,w) \­) of the equation \­( x^2+y^2+z^2+q^2+w^2=n \­) has a root solution \­( (a,b,c,d,e) \­) such that \­( a^2+b^2+c^2+d^2+e^2=n \­) such that \­( |x|=a, |y|=b, |z|=c, |p|=d, |w|=e \­) .

Then, because the order of the letters also matters, the number of solutions \­( (x,y,z,q,w) \­) that have as root solution \­( (a,b,c,d,e) \­) can be counted.

That means that if we define a root solution \­( (a,b,c,d,e) \­) as a vector composed of nonegative integrers such that \­( a \geq b \geq c \geq d \geq e \­), it can be generated new solutions permutating the order of the coordinates and their signs.

The number of permutation of the coordinates depends of how many numbers are equal in the vector \­( (a,b,c,d,e) \­). If all numbers are distinct, the number of permutations is \­( 5! \­).I If \­( a=b\­), \­( c=d=e \­), the number of permutations is \­( \frac {5!}{2! 3!} \­) If \­( a=b \­), \­( c=d \­), its \­( \frac {5!}{2! 2! 1!} \­)

In general the numbers are of the form \­( \frac {5!}{m!n!...} \­) And because \­( m,n,... <5 \­), the result is multiple of \­( 5 \­).

Also, considering that if \­( (a,b,c,d,e) \­) is a solution for \­( n \­) is impossible that \­( a=b=c=d=e=0 \­), at least you can double the number of solutions by changing signs of the original vector. For example \­( (10,7,5,5,2) \­) is equivalent to \­( (-10,7,5,5,2) \­)

As we can see, the number of solutions that have as root solution \­( (a,b,c,d,e) \­) is multiple of \­( 2 \­) and \­( 5 \­) and because of it, \­( 10 \­).

The only way to avoid this is that \­( a=b=c=d=e \­) because the number of permutations of this is \­( 1 \­). Then, if \­( (a,a,a,a,a) \­) is a solution, there are \­( 2^5 \­) different solutions changing signs. If \­( (a,a,a,a,a) \­) is solution to n, then \­( 5a^2=n < 5679 \­) \­( a^2 < 1135.8 < 1156 < 34^2 \­) \­( a < 34 \­)

So, only caring about unit digit, the only numbers that care are the solutions \­( (a,a,a,a,a) \­) for \­( n=5m^2 \­) with \­( m \­) from \­( 1 \­) to \­( 33 \­). \­( 2^5=32 \­) so \­( D_{5m^2}=2 \­) So the total sum is \­( 2*33=66 \­).

Denote $T_n = A_n \cup (T_n \setminus A_n)$ where $A_n^c := T_n \setminus A_n = \{\underline{a} \in T_n | a_1 = a_2 = a_3 = a_4 = a_5\}$ .

Claim: $|A_n|$ is divisible by $10$ for all naturals $n$ .

Proof: Pick any vector $\underline{a}$ in $A_n$ whose co-ordinates are in non-decreasing order. Observe that all 5 cyclic permutations of $\underline{a}$ are distinct, for this case, and they all belong to $A_n$ . Further we can get 5 more solutions by running this argument for $-\underline{a}$ . Thus for every solution $\pm \underline{a}$ in non-decreasing order, we can generate $10$ solutions. Also note that the ten solutions generated for two different non-decreasing vectors (upto a -sign) is different. Further, every solution is some permutation of it's non-decreasing order. Thus we have partitioned $A_n$ into disjoint sets of 10 vectors each. This means that 10 divides $|A_n|$ for every $n$ . Q.E.D.

Therefore $|D_n| = |A_n| + |A_n^c| = |A_n^c| \mod 10$

Any vector in $A_n^c$ is of the form $(k,k,k,k,k)$ and therefore $5k^2 = n$ . There are two cases:

1) If $n$ is not of the form $5k^2$ , $A_n^c$ is empty and therefore $|D_n| = 0 \mod 10$ .

2) If $n = 5k^2$ , then there are two vectors, viz. $(k,k,k,k,k)$ and $-(k,k,k,k,k)$ in $A_n^c$ and therefore $D_n = 2 \mod 10$ .

Now $1 \leq 5k^2 \leq 5 \cdot 33^2 < 5678$ and thus $D_n$ contributes $33$ twos to the sum $\sum_{i=1}^{5678} D_i$ and therefore the answer is 66.

For a particular 'n' let $(a_1,a_2,a_3,a_4,a_5)$ be an ordered pair satisfying $a_1^2+a_2^2+a_3^2+a_4^2+a_5^2=n$

We know that all permutations of $(a_1,a_2,a_3,a_4,a_5)$ will also satisfy $a_1^2+a_2^2+a_3^2+a_4^2+a_5^2=n$

Case -1(If all $a_i$ s are distinct)

From the given ordered pair $(a_1,a_2,a_3,a_4,a_5)$ we can obtain $5!$ ordered pairs (including the one used) by permuting $a_1,a_2,a_3,a_4,a_5$ in 5 places.

Case -2(If 2 $a_i$ s are identical, rest are distinct)

From the given ordered pair we can get ${5 \choose 2}\times 3!$ ordered pairs (including the one used) by permuting $a_1,a_2,a_3,a_4,a_5$ in 5 places.

Case-3(If there exist 2 pairs of $a_i$ which are not identical, both contain the same numbers and the other number is not equal to the numbers in any of the pairs)

From the given ordered pair we can create ${5 \choose 2}\times {5 \choose2}$ ordered pairs (including the original one) by permuting $a_1,a_2,a_3,a_4,a_5$ in 5 places.

Case-4(If 3 $a_i$ s are identical and other 2 are distinct)

Using the given ordered pair we can obtain ${5 \choose 2}\times 2!$ ordered pairs(including the original one).

Case-5(If there exists a triplet and a pair of $a_i$ s each containing equal numbers and the numbers in the triplet not being equal to the numbers in the pair)

Using the given ordered pair we can obtain ${5 \choose 2}$ ordered pairs(including the original one).

Case-6(If 4 $a_i$ s are identical and the fifth one is distinct from the rest 4)

Similarly here, we can construct ${5\choose4}$ ordered pairs from the given one.

Case-7(If all $a_i$ s are identical)

Here we can construct only 1 ordered pair(i.e the original one).

Now note that in cases 1-5 the number of ordered pairs obtained by permutation is a multiple of 5.

Let us look at cases 6 and 7 more closely.

Case-6(revisited)

If $(a_1,a_2,a_3,a_4,a_5)$ is a solution then we can obtain more ordered pairs by reversing the sign of some or all the $a_i$ s.

Considering the cases:-

(i)All the $a_i$ s are non 0.

(ii)4 of the $a_i$ s are 0, the other is non zero

(iii)1 $a_i$ is 0, others are non-zero

In each of the above sub cases we have to multiply a multiple of 2 to get more ordered pairs.

Case-7(revisited)

All $a_i$ s must be non-zero according to the question.

Here we can get $2^5$ ordered pairs(including the original one).

Now, it is clear that for all n that cannot be expressed as $5 \times k^2$ (where k is a positive integer) the number of ordered pairs is a multiple of 10. $D_n=0$ for all such n.

There are 33 numbers less than 5678 which can be expressed as $5 \times k^2$

So, our answer will be $33\times2$ which is 66.

Let $\sigma(a,b,c,d,e) = (-e,-a,-b,-c,-d).$ Note that $\sigma^{10}$ is the identity and that $\sigma$ preserves distance from the origin. The group $G$ generated by $\sigma$ acts on $T_n$ , so it partitions $T_n$ into orbits of size $10/m$ where $m$ is the size of the stabilizer of an element in the orbit.

If $m = 1$ then the orbit has size $10$ .

If $m = 2$ then $\sigma^5 {\bf x} = {\bf x}$ for all ${\bf x}$ in the orbit, but $\sigma^5 {\bf x} = -{\bf x}$ so $\bf x$ is the all-zeroes vector, which is impossible for $n > 0$ , so there are no orbits of size $5$ .

If $m = 5$ then $\sigma^2 (a,b,c,d,e) = (a,b,c,d,e)$ for all $(a,b,c,d,e)$ in the orbit, so $(d,e,a,b,c) = (a,b,c,d,e)$ , so $a=b=c=d=e$ . This is possible only if $n = 5a^2$ , in which case there is exactly one orbit of size $2$ , consisting of $(a,a,a,a,a)$ and $(-a,-a,-a,-a,-a)$ .

If $m = 10$ then $\sigma {\bf x} = {\bf x}$ for all $\bf x$ in the orbit, but then $\sigma^5 {\bf x} = {\bf x}$ , which we have seen above is impossible for $n > 0$ . So there are no orbits of size $1$ .

Putting it all together, we see that $D_n = 2$ if $n = 5a^2$ for some integer $a$ and $D_n = 0$ otherwise. There are $33$ positive values of $n \le 5678$ that satisfy $n = 5a^2$ (since $5(33)^2 \le 5678 \le 5(34)^2$ ), so the sum is $2 \cdot 33 = 66.$

If $a_1^2+a_2^2+a_3^2+a_4^2+a_5^2 = n$ then $a_2^2+a_3^2+a_4^2+a_5^2 + a_1^2 = n$ and $(-a_1)^2+(-a_2)^2+(-a_3)^2+(-a_4)^2+(-a_5)^2 = n$ . These generate a group of order 10. If a solution has no symmetries, then the orbit under the group has size 10, and together these have no effect on the units digit of $D_n$ .

For a solution to have an orbit of size less than 10, it must be of the form $a_1=a_2=a_3=a_4=a_5$ . For each n of the form 5k^2 with $k\gt 0$ , there are two of these, $a_1=k$ and $a_1=-k$ , so $D_{5k^2} = 2$ . Since $\lfloor \sqrt{5678/5} \rfloor = 33, \sum_{i=1}^{5678} D_i = 2*33 = 66.$

We claim that $D_n = 2$ when $n = 5 k^2$ and $D_n = 0$ otherwise. For each element $(a_1,a_2,a_3,a_4,a_5)$ of $T_n,$ we consider the unordered multi-set $\{|a_1|, |a_2|, |a_3|, |a_4|, |a_5|\}.$

If the $a_i$ values are not all the same, then the number of ways of ordering the elements $|a_1|, |a_2|, |a_3|, |a_4|, |a_5|$ to form a $5$ -tuple will be a multiple of 5, since it is of the form $\frac{5!}{v!w!x!y!z!}$ where $0 \leq v,w,x,y,z \leq 4$ and $v + w + x +y + z = 5.$ If there are $h$ non-zero entries, then for each permutation of the numbers, there will be $2^h$ ways of making a $5$ -tuple from that permutation by choosing a sign for each non-zero entry. Since $h > 0,$ the number of these will be a multiple of 10.

If the $a_i$ values are all the same, then there are 32 different $5$ -tuples that have the same multi-set of elements. We will only ever have all the $a_i$ values being the same when $n = 5 a_1^2,$ or, that is to say when $n$ is 5 times a perfect square.

The number of numbers less than $5678$ that have this property is $\left\lfloor \sqrt{\frac{k}{5}} \right\rfloor$ , hence the sum of $D_i$ is $2 \times \left\lfloor \sqrt{\frac{k}{5}} \right\rfloor = 66.$