Representing a number as a sum of at most $k$ squares

This is an example of "Waring's problem" - expressing integers as the sum of $k$ $p$th powers of integers. In the case of squares, when $k\ge5$ the asymptotics of the number of representations (as a function of $n$) have been known for some time (I believe Hua proved this in the 1930s). When $k\ge5$, the number of ways to write $n$ as the sum of $k$ squares of positive integers is asymptotic to $$ \frac{\Gamma(3/2)^k}{\Gamma(k/2)}n^{k/2-1} S(n), $$ where $\Gamma$ is the Gamma function that interpolates the values of factorials, and $S(n) = S_k(n)$ is the "singular series" that depends upon $n$ but is bounded above and below.

One can find expositions of Waring's problem and the "circle method" (aimed at many different levels) in various places on the web, such as here and here.

The leading term of the asymptotics will be $r_k(n)/k!$ where $r_k(n)$ is the unconstrained number of representations of $n$ as a sum of squares of $k$ integers. For specific $k$ such as 4 or 8 there are classical formulas as sums of arithmetic functions (proofs use modular forms). For fixed $k>4$ the leading term is on average equal to $An^b$ with $A$ and $b$ calculable from volumes of spheres, but as explained in the answer by Greg Martin, the "constant" $A$ is in fact a quasiperiodic function of $n$, the singular series (the product of p-adic densities of solutions to the equation).

This is not an answer to your question. But here's some things I vaguely know.

The introduction of Ila Varma's master thesis

http://www.math.leidenuniv.nl/scripties/VarmaMaster.pdf

written under the supervision of Bas Edixhoven might have some things relevant to what you need. As she says in the introduction, there are closed formulas for even integers $n\geq 12$. She proves that there aren't any formulas for $n > 12$. (This has to do with cusp forms.)

Anyway, there aren't formulas, but there ARE polynomial algorithms. See this paper by P. Bruin.

http://pmb.univ-fcomte.fr/2011/Bruin.pdf

You might want to look at the end of the introduction to his article right after Remark 1.6.

At the end of his article he shows that it's possible to compute these numbers in polynomial time.