2
$\begingroup$

I am aware of Lagrange's Four-Square Theorem, which states that every positive integer can be written as the sum of at most four squares. Clearly some integers require fewer squares. Does there exist a polynomial-time algorithm to compute the minimum number of squares needed to sum to a given integer $n$?

It is easy to come up with a dynamic program for this problem; denote the number of squares needed to represent $i$ by $T[i]$, then

\begin{align*} T[i] = \min_{1 \le s \le \sqrt{i}} T[i - s^2] + 1 \end{align*}

Thus, we can solve this problem in $\Theta(n\sqrt{n})$, but this is not polynomial in $\log(n)$.

  • 0
    So the difficult part is differentiating between numbers that require two squares and numbers that require three. Thanks for the feedback!2012-01-27

0 Answers 0