Find the cardinality of the following set $S_n=\{(x,y)|x^2+y^2=n, \text{where }x,y,n \in \mathbb Z\text{ and }n\geq0 \}$ We are given with  $$S_n=\{(x,y)|x^2+y^2=n, \text{where }x,y,n \in \mathbb Z\text{ and }n\geq0  \}$$
Now observe that $-\sqrt n\leq x\leq\sqrt n $ and similarily, $-\sqrt n\leq y\leq\sqrt n $. This means that $-\left \lfloor{\sqrt n}\right \rfloor\leq x\leq \left \lfloor{\sqrt n}\right \rfloor$ and  $-\left \lfloor{\sqrt n}\right \rfloor\leq y\leq \left \lfloor{\sqrt n}\right \rfloor$. Through this result one can easily write code and figure out the cardinality of set $S_i$ but I was wondering whether an expression can be found that would allow one to directly compute $|S_i|$. 
 A: Let us denote the size $|S_n|$ as $r_2(n)$, as is done in this answer and on this Wolfram page. It can be computed as
$$
r_2(n) = 4 \sum_{\text{odd } d \mid n} (-1)^{\frac{d-1}{2}}.
$$
However, this formula is a bit cryptic. More usefully, $\frac{r_2(n)}{4}$ is multiplicative, that is for $a$ and $b$ relatively prime, $\frac{r_2(ab)}{4} = \frac{r_2(a)}{4} \cdot \frac{r_2(b)}{4}$. And, for a prime $p$:
$$
r_2(p^k) =
4 \cdot \begin{cases}
  1 & \text{if } p = 2 \\
  0 & \text{if } p \equiv 3 \pmod{4} \text{ and } k \text{ is odd} \\
  1 & \text{if } p \equiv 3 \pmod{4} \text{ and } k \text{ is even} \\
  (k+1) & \text{if } p \equiv 1 \pmod{4}.
\end{cases}
$$
So this gives another way to write $r_2(n)$: if every odd prime congruent to $3$ mod $4$ divides into $n$ an even number of times, then we have
$$
r_2(n) = 4 \prod_{\substack{p \equiv 1 \pmod{4} \\ p^k \mid n}}
(k+1),
$$
where $p^k$ is the highest prime power dividing $n$.
Otherwise, $r_2(n) = 0$.
This sequence can be found on OEIS here.

Some special cases:


*

*The sum of two squares theorem: 
in your context, this says that $|S_n| = 0$ if $n$ contains an odd number of copies of some prime divisor $p \equiv 3 \pmod{4}$, and $|S_n| > 0$ otherwise.

*For $p, q$ distinct primes $\equiv 1 \pmod{4}$, $|S_p| = |S_q| = 8$ and $|S_{pq}| = 16$.
(Because we allow for $x, y < 0$, a factor of $4$ arises for the sign of $x$ and $y$, and a factor of $2$ is for switching $x$ and $y$.)
This is discussed in some related questions.

*The most trivial case, $|S_1| = 4$. We could also define $|S_0| = 1$, but most of the formulas in this answer don't apply for $|S_0|$.

Generating function:
$$
\sum_{n=1}^\infty r_2(n) x^n = 4\sum_{k=\color{red}{0}}^\infty \frac{(-1)^{k} x^{2k+1}}{1 - x^{2k+1}} = 4 \sum_{k=\color{red}{1}}^\infty \frac{x^{k}}{1 + x^{2k}},
$$
which can also be written as an infinite product involving Pochhamer symbols if we like.
This is derived from the formula at the top of this post.

Cumulative sums: Gauss's circle problem
Finally, others have mentioned Gauss's circle problem. $\sum_{n=0}^{N} |S_n|$ is the number of integer coordinates inside a circle of radius $\sqrt{N}$ about the origin. Therefore it approximates the area of that circle, and we have
$$
\sum_{n=0}^{N} r_2(n) \approx N \pi.
$$

Notes on how to prove the formulas
I do not provide a proof here of the formulas for $r_2(n)$. The basic idea is that they come from Gaussian integer factorization (unique factorization property in the ring $\mathbb{Z}[i]$). In particular, every $(a,b)$ such that $n = a^2 + b^2$ corresponds to a factorization
$$
n = (a + bi)(a - bi),
$$
so to count the number of such factorizations we can count the number of ways to write $n = z \overline{z}$ where $z \in \mathbb{Z}[i]$. Then we factorize $n$ in the Gaussian integers, where the primes equivalent to $3$ mod $4$ do not decompose, but the primes equivalent to $1$ mod $4$ split into pairs. Using this, we can derive the desired formulas.
