Let $S_n(R)$ denote the number of lattice points in an $n$-dimensional "sphere" with radius $R$. For clarification, I am interested in lattice points found both strictly inside the sphere, and on its surface. I want to count exactly how many such points there are. This count corresponds to the amount of sets of integers that are solutions to the equation $$a_1^2+a_2^2+a_3^2+...+a_{n-1}^2+a_n^2= R^2$$ where the $a_i$'s are required to be integers, not necessarily positive, and sets that differ just by the order of the summands are also considered distinct, i.e for the case $n=3, R=5$, the following are both counted: $3^2+(-4)^2+0^2$ and $(-4)^2+0^2+3^2$. This can also be interpreted as the sum of squares function - $r_d(k)$ denotes in how many such ways I can write $k$ as the sum of $d$ squares. This means that $$S_n(R) = \sum_{k=1}^{R^2}r_n(k)$$
I am asking this question as a general one, but I am mostly concerned about the cases of $n=2, n=3,n=4$.
In order not to be too lengthy and remain focused, I won't explain why but summing this way requires to factor each $k$ first. This is very time consuming, so I searched for better ways.
For the case of $n=2$, which is essentially just the count of lattice points in a circle of radius $R$, I have managed to find that $$S_2(R)= 1+\sum_{i=1}^\infty\biggl(\biggl \lfloor\frac{R^2}{4i+1}\biggl \rfloor-\biggl \lfloor\frac{R^2}{4i+3}\biggl \rfloor\biggl )$$For the case of $n=4$, I found: $$S_4(R)= 1+8\sum_{k=1}^{R^2}\sum_{d|k \atop {4\nmid d}}d$$ Unfortunately, for the case of a sphere ($n=3$), I have found no formula, neither for the count of lattice points inside nor on the surface of the sphere.
Although these formulas do indeed provide the exact count of lattice points, they are very slow in computational terms, as their running time complexity is $O(R^2)$. I was wondering if a more efficient way exists to count the number of such lattice points, perhaps $O(R)$ or $O(R^{1/2+\epsilon})$, so that I can work with radii as big as $10^9$ or even more. I suspect there is a way, but I can't find it. Not necessarily a different approach to the problem, but rather just a more clever way to reduce the order of the sum. Also, any insight about $S_3(R)$ will be appreciated.
