Sum of five squares
Time limit5.555sMemory limit555 MB
Given n up to 10^10, count the signed integer 4-tuples and 5-tuples whose squares sum to n.
- Level
Hard8 of 10
- Topics
- Math, Number theory
- Solved
- No attempts yet
Problem
Sanggeun was playing with squares when he noticed that the number of ways to write a nonnegative integer as a sum of five squares is far larger than the number of ways to write it as a sum of four squares.
For example, when , the ways to write it as a sum of four squares are
1 &= 1^2 + 0^2 + 0^2 + 0^2 \\ 1 &= {(-1)}^2 + 0^2 + 0^2 + 0^2 \\ 1 &= 0^2 + 1^2 + 0^2 + 0^2 \\ 1 &= 0^2 + {(-1)}^2 + 0^2 + 0^2 \\ 1 &= 0^2 + 0^2 + 1^2 + 0^2 \\ 1 &= 0^2 + 0^2 + {(-1)}^2 + 0^2 \\ 1 &= 0^2 + 0^2 + 0^2 + 1^2 \\ 1 &= 0^2 + 0^2 + 0^2 + {(-1)}^2 \end{align\*} $$ for a total of $8$. The ways to write it as a sum of five squares are $$ \begin{align\*} 1 &= 1^2 + 0^2 + 0^2 + 0^2 + 0^2 \\ 1 &= {(-1)}^2 + 0^2 + 0^2 + 0^2 + 0^2 \\ 1 &= 0^2 + 1^2 + 0^2 + 0^2 + 0^2 \\ 1 &= 0^2 + {(-1)}^2 + 0^2 + 0^2 + 0^2 \\ 1 &= 0^2 + 0^2 + 1^2 + 0^2 + 0^2 \\ 1 &= 0^2 + 0^2 + {(-1)}^2 + 0^2 + 0^2 \\ 1 &= 0^2 + 0^2 + 0^2 + 1^2 + 0^2 \\ 1 &= 0^2 + 0^2 + 0^2 + {(-1)}^2 + 0^2 \\ 1 &= 0^2 + 0^2 + 0^2 + 0^2 + 1^2 \\ 1 &= 0^2 + 0^2 + 0^2 + 0^2 + {(-1)}^2 \end{align\*} $$ for a total of $10$. Strictly speaking, the number of ways to write a nonnegative integer $n$ as a sum of four squares and as a sum of five squares are $$ r_{4}(n) = \left\vert \{ (a_1, a_2, a_3, a_4) \in \mathbb{Z}^4 : n = a_1^2 + a_2^2 + a_3^2 + a_4^2 \} \right\vert $$ $$ r_{5}(n) = \left\vert \{ (a_1, a_2, a_3, a_4, a_5) \in \mathbb{Z}^5 : n = a_1^2 + a_2^2 + a_3^2 + a_4^2 + a_5^2 \} \right\vert $$ Sanggeun counted these for small values of $n$ and put the results in a table. | $n$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | $r_{4}(n)$ | $1$ | $8$ | $24$ | $32$ | $24$ | $48$ | $96$ | $64$ | $24$ | $104$ | $144$ | | $r_{5}(n)$ | $1$ | $10$ | $40$ | $80$ | $90$ | $112$ | $240$ | $320$ | $200$ | $250$ | $560$ | Tired of counting by hand, Sanggeun wants a program that, given $n$, computes the number of ways to write $n$ as a sum of four squares and the number of ways to write it as a sum of five squares.Input
The first line contains an integer ().
Output
On the first line, print the number of ways to write as a sum of four squares. On the second line, print the number of ways to write as a sum of five squares.