Represent an integer as a sum of n non-consecutive squares Is it possible to decompose an integer into a sum of n unique squares ,even though they are not necessarily consecutive.
For instance, How would I obtain the sequence 1*1 + 7*7 + 14*14 + 37*37 given the integer 1615
or 11*11 + 15*15 + 29*29 + 43*43 + 69*69 given the integer 7797.
 A: OEIS A001422 gives the full list of
natural numbers not expressible as the sum of distinct squares:
$$
\begin{array}{c}
2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 
\\
43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128.
\end{array}
$$
The reference is

R. Sprague, Über Zerlegungen in ungleiche Quadratzahlen, 
  Math. Z. 51 (1948), 289$-$290.

(This two-page paper
is several decades before Halter-Koch 1982, which concerns
decompositions into exactly $5$ distinct squares.)
Added later: The Sprague paper is elementary and constructive,
thus also answering the OP's question "How would I obtain
[a sum-of-distinct-squares representation] given the integer".
Basically, starting from $n$, subtract the first square larger than $n/2$,
and repeat until you first reach a number less than $300$.
That number will still exceed $128$, so to finish consult
a table with a distinct-square representation of each of the 
integers in $(128,300)$.  Such a table was routine to compute
even in 1948, and is basically trivial with the computer.
For example, applying this technique to the OP's $1615$ yields
$1615 = 29^2 + 20^2 + 14^2 + 178$, and then for instance $178 = 13^2 + 3^2$
or $178 = 12^2 + 5^2 + 3^2$.
If we read "even though they are not consecutive" in the strict sense 
that no pair of consecutive squares is allowed in the sum, then
much the same technique must still work, though with thresholds
somewhat larger than $128$ and $300$, and subtracting from $n$ 
the smallest $k$ such that $n-k^2 < (k-1)^2$ (not just less than $k^2$).
A: Yes, by Lagrange's four-square theorem. More generally, for any $k$ there is an $s$ such that any natural number is the sum of $s$ $k$-th powers, see Waring's problem.
Added 1. Halter-Koch proved in 1982 that any integer greater than 245 is the sum of 5 distinct squares, see Satz 4 here. He also determined which numbers are not the sum of 4 distinct squares (there infinitely many exceptions, but only finitely many exceptions that are not divisible by 4), see Satz 3 here.
Added 2. For representability as a sum of more distinct squares, see the paper by Bateman, Hildebrand, Purdy here. For example, Table I in this paper tells us that any integer greater than 343296 is the sum of 100 distinct squares.
Added 3. It is straightforward to show that for any $d>0$, every sufficiently large $n$ is the sum of squares of 5 natural numbers whose minimal distance is at least $d$. This is because, by the circle method, the number of representations $n=n_1^2+\dots +n_5^2$ is $\gg n^{3/2}$, while the number of representations with $|n_i-n_j|<d$ for some $1\leq i<j\leq 5$ is $\ll_{d,\epsilon} n^{1+\epsilon}$ for any $\epsilon>0$.
A: John Thompson and I proved in a paper about character theory of the Alternating group that for $m > 1922$, it is possible to express $m$ as a sum of at most $11$ distinct odd squares.
A: I do not know the answer, but I suspect for every n greater than 3, all but finitely many
positive integers will have a representation as a sum of n distinct and
nonconsecutive squares, and of those, only finitely many will have only one such
representation.
Here is a method to search for a representation.  Given integers n and s, you know
that if there is a representation, the largest summand is greater than s/n.  Now
for each square q from s/n to some limit less than s, consider the subproblem
(s-q, n-1, q), which is to represent s-q as the sum of n-1 distinct and nonconsecutive
squares, all less than the largest square less than q.  A program which searches for such
representations and values of n less than 10 should be able to find one or more
representations when they exist for s less than a billion quite quickly.  You may find
a good upper bound for non representable numbers fairly quickly, and from that
conjecture a general bound depending only on n greater than 3.
