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)?

Question

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)..?

Answer 1

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$

Answer 2

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.

Answer 3

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)$.