Is there a simple way to get the numbers of squares that can fit into an integer N in descending order starting with sqrt(N)? To make things clear, consider the example of $$N=143= 11^2 + 4^2 + 2^2 + 1^2 + 1^2$$
Is there a way to predict how many squares will add up to N=143 in descending order without finding the squares if the only operation used is taking the sqrt(N), then sqrt(N-a^2), then sqrt(N-a^2-b^2)..? 
 A: As I understand the question, you want to know the maximum run-time of your algorithm for expressing a number $N$ as a sum of decreasing squares. You are not looking to minimise the number of squares (which is where the four-square theorem discussed in another answer might come in handy).
My first approach will be to consider the "worst case scenario." It is rather a naive way, but does give us an upper bound to the run-time.
In the "worst-case scenario" $N=k^2+(k-1)^2+...+2^2+1^2=\frac{k(k+1)(2k+1)}{6}\approx \frac {k^3}3$
This would give a run-time of $k\approx (3N)^{\frac 13}$
The problem is that this approach overestimates the run-time significantly!
My second approach is a recursive one.
Let $T(n)$ be the run-time for your algorithm starting with the number $n$.
It can be shown quite easily that:
$T(1)=1$
$T(2)=2$
$T(3)=3$
Linear? Of course not!
$T(4)=1$
$T(5)=2$
Once again let's look at a worst case scenario - where you have the largest possible residue after subtracting the first square. This is when $n$ is just one less than a slightly larger square.
If $n=(k+1)^2-1$, then we subtract $k^2$.
The result is $(k+1)^2-1-k^2=k^2+2k+1-1-k^2=2k$
So $T((k+1)^2-1)\le 1+T(2k)$
Since $n=(k+1)^2-1$, we have $n+1=(k+1)^2 \Rightarrow k=\sqrt{n+1}-1$
$T(n)\le 1+T(\sqrt n)$
This is still quite tricky...
...but it is true to say that $\sqrt n \le \frac n2$ for all $n > 4$
So our sequence is $T(n)\le 1+T(\frac n2)\le 1+1+T(\frac {n}4) \le ...$
Again an upper bound can be found by asking how many times must we halve until we get to $T(3)$
$n(\frac 12)^k=3 \Rightarrow \frac{n}3=2^k \Rightarrow \log_2(\frac{n}3)=k  \Rightarrow T(n) \le \log_2(\frac{n}3)+3 \le \log_2(n)+2$
That gives what is still an upper bound $T(n)\le \log_2(n)+2$
A: If $N = \lfloor \sqrt{N} \rfloor^2 + R$, then $R \leq N/2$ for $N > 3$.  Therefore the number of iterations is $O(\log N)$.
A: There is this theorem "Lagrange's four-square theorem"(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem)
that predicts that every natural number can be expressed as the sum of four squares.
