The story begins with a coding problem:

Given a positive integer $$n$$, find the least number of perfect square numbers (for example, $$1, 4, 9, 16$$, …) which sum to $$n$$.

## A DP Algorithm

The above problem can be solved with a simple DP algorithm:

int solve(int n)
{
vector<int> v(n + 1, INT_MAX);
v[0] = 0;
for (int i = 1;i <= n;i++)
for (int j = 1;j * j <= i;j++)
v[i] = min(v[i], v[i - j * j] + 1);
return v[n];
}


Not much surprise. But what if you run it through $$[1, 100]$$, or even more? The result is always between 1 and 4.

## Theorems

In fact there is a Lagrange’s four-square theorem which states:

Every natural number can be represented as the sum of four integer squares.

In fact there is also a Legendre’s three-square theorem which states:

A natural number can be represented as the sum of three squares of integers if and only if $$n$$ is not of the form $$n = 4^a(8b + 7)$$ for integers $$a$$ and $$b$$.

## A Faster Algorithm

With these two theorems we have a faster solution to the above problem:

int solve(int n)
{
while (n % 4 == 0)
n /= 4;
if (n % 8 == 7)
return 4;

if (int(sqrt(n)) * int(sqrt(n)) == n)
return 1;

for(int i = 1;i * i < n;i++) {
int j = n - i * i;
if (int(sqrt(j)) * int(sqrt(j)) == j)
return 2;
}

return 3;
}


We now give an analysis of this algorithm. If not otherwise noted, all integers we consider in the analysis below are positive integers.

### Analysis

1. Lagrange’s four-square theorem shows that the answer to any number $$n$$ is no more than 4. Legendre’s three-square theorem shows that the answer is greater than 3 when $$n$$ is not of the form $$n = 4^a(8b + 7)$$. So the answer must be exactly 4 when $$n$$ is of the form $$n = 4^a(8b + 7)$$.

2. In all other cases the answers can only be 1, 2 or 3. We first determine whether the answer is 1 by checking whether $$n$$ is a perfect square. However, the code is actually not checking $$n$$ but $$m = 8b + 7$$. We need to prove $$n$$ is a perfect square if and only if $$m$$ is a perfect square.

• If part. If $$m = x^2$$ is a perfect square, then $$n = 4^am = (2^ax)^2$$ is also a perfect square.

• Only-If part. If $$n = 4^am = y^2$$ is a perfect square, then $$(2^a / y)^2 = m$$. So $$2^a / y = \sqrt{m}$$. Since $$m$$ is a positive integer, if $$m$$ is not a perfect square then $$\sqrt{m}$$ is irrational. But $$2^a / y$$ is rational. This is a contradiction.

3. If $$n$$ is not a perfect square then we further check whether it is a sum of two perfect squares. We can still check $$m$$ instead of $$n$$ since we can prove $$n$$ is a sum of two perfect squares if and only if $$m$$ is a sum of two perfect squares.

• If part. If $$m = x^2 + y^2$$ is a sum of two perfect squares, then $$n = 4^am = (2^ax)^2 + (2^ay)^2$$ is also a sum of two perfect squares.

• Only-If part. We first prove the following lemma:

If an even number $$4w$$ is a sum of two perfect squares, then $$w$$ is also a sum of two perfect squares.

Proof. Let $$4w = u^2 + v^2$$. Then $$w = (u / 2)^2 + (v / 2)^2$$. Since $$4w \equiv 0 \bmod 4$$, it must be that $$u$$ and $$v$$ are both even:

• Since $$4w$$ is even, it must be that $$u$$ and $$v$$ are both odd or both even.

• If $$u = 2s - 1$$ and $$v = 2t - 1$$ are both odd, then $$(u^2 + v^2) \equiv (4s^2 - 4s + 1 + 4t^2 - 4t + 1) \equiv 2 \bmod 4$$. This is a contradiction.

Therefore $$u$$ and $$v$$ are both even and $$u / 2$$ and $$v / 2$$ are both integers. So $$w$$ is a sum of two perfect squares.

Repeated use of the lemma on $$n = 4^am$$ will finish the proof.

4. If $$n$$ is neither a perfect square nor a sum of two perfect squares, then the answer is 3.