How to find the sum of squares of $1\ldots N-1$ that add to a squared number $N^2$?

So here's a question my friend recently gave me and ever since I've been trying to solve it without much success:

There's a number $$N$$, and out of the set $$U = \{1,2,3,\ldots,(N-1)\}$$ we have to find a subset $$S$$ such that the sum

$$\sum_{i\in S} i^2 =$$ $$\color{red}{N^2} ~: ~$$(corrected what was assumed to be a typo : user2661923)

For instance if $$N = 11$$, $$U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$$ has the solutions $$S_1 = \{1,2,4,10\}$$ and $$S_2 = \{2,6,9\}$$ because both $$S_1$$ and $$S_2$$ have square sums of $$11$$. Yet there's a caveat that the solution having the largest square and the most number of elements is preferable. In this case, $$S_1$$ is preferable because the largest element in $$S_1$$ is $$10$$ compared to that of $$S_2$$ which is $$9$$. Also $$S_1$$ has more elements than $$S_2$$ which satisfies our criteria.

I'm struggling to find a general deterministic algorithm that can find such subsets, for example what if $$N$$ is something like $$50$$? In that case there are many possible ways to build but subsets of squares that add to $$50$$ yet also to check these two criteria in conjunction proves to be somewhat of a challenge. I'm not sure if there is even such an algorithm, although I'll be happy to be proved otherwise.

What I've tried is that starting from $$N-1$$ in the set $$U = \{1,2,\ldots,N-1\}$$ I can count backward, but how do I choose if some number $$i$$ should be included in the solution set or not? For it may happen with extremely large sets that the way I would get a perfect sum of squares is dependent upon the specific numbers I choose rather than just make a decision based of the number I am currently standing on.

• Don't you mean the that sum of the squares is $N^2$? When $N=50$ we have to find as set $S\subset\{1,2,\dots,49\}$ such that $\sum_{i\in S}i^2=2500$, correct? Jun 15 '21 at 19:37
• en.wikipedia.org/wiki/Subset_sum_problem Jun 15 '21 at 19:38
• It should be $\sum_{i \in S} i^2=N^2$ Jun 15 '21 at 19:38
• What's more important: having a larger term or having lots of small terms? Are we to interpret number of terms as a tie-breaker? Jun 15 '21 at 19:39
• saulspatz link shows this problem is at worst NP-complete, but this problem as stated could be a special case in which a polynomial time algorithm exists. Jun 22 '21 at 16:06

Before we start, let me point out that the set of numbers that cannot be represented as a sum of distinct squares are finite ( OEIS A001422) and the largest element in this list is $$128$$. We are going to construct an algorithm based on this.

For any $$n,m \in \mathbb{Z}$$, let $$[n,m] = \{ k \in \mathbb{Z} : n \le k \le m \}$$.

For any $$S \subset \mathbb{Z}_{+}$$, let $$f(S) = \sum\limits_{i\in S}i^2$$.

By brute force, one can verify:

For any $$n \in [129,272]$$, there is a $$S \subset [1,11]$$ such that $$n = f(S)$$.

For any $$r \ge 273$$, let $$s = \left\lfloor \sqrt{r - 129}\right\rfloor$$. It is clear $$s \ge \sqrt{273-129} = 12$$. Furthermore,

$$s \le \sqrt{r - 129} < s + 1 \quad\implies\quad 129 \le r - s^2 \le 2s+ 129$$

Notice $$s^2 - (2s+129) = (s-1)^2 - 130 > 0$$. If $$r - s^2 = f(S)$$ for some $$S \subset \mathbb{Z}_{+}$$, the largest element in $$S$$ will be smaller than $$s$$. This will lead to $$r = f(S \cup \{s\})$$.

If $$r - s^2 \in [129,272]$$, we can express $$r$$ as a sum of distinct squares. If not, apply this procedure repeatedly to $$r - s^2$$ until we get one which falls between $$[129,272]$$. This will allow us to represent $$r$$ as a sum of distinct squares.

More precisely, construct a finite sequences of pairs $$r_k, s_k$$ by following rules:

1. Start from any $$r \ge 129$$. If $$r < 273$$, let $$m = 0, r_0 = r, s_0 = 0$$ and stop.
2. Otherwise, set $$k = 1$$ and let $$r_1 = r$$, $$s_1 = \left\lfloor \sqrt{r_1 - 129} \right\rfloor$$.
3. If $$r_k - s_k^2 \in [129,272]$$, set $$m = k$$ and stop.
4. Otherwise, let $$r_{k+1} = r_k - s_k^2$$, $$s_{k+1} = \left\lfloor \sqrt{r_{k+1} - 129} \right\rfloor$$. Set $$k = k+1$$ and repeat step 3.

At the end, we will have a bunch of distinct $$s_1, s_2, \ldots, s_m$$ (when $$m > 0$$) and $$r_m, s_m$$ such that the $$r_m - s_m^2 \in [129,272]$$. Lookup the $$S \subset [1,11]$$ with $$r_m - s_m^2 = f(S)$$, we will have

$$r = \begin{cases} f(S), & m = 0\\ f(S \cup \{ s_1, s_2, \ldots, s_n \}), & m > 0\end{cases}$$

This means every $$r \ge 129$$ can be represented as a sum of $$\ell \ge 1$$ distinct squares: $$r = \sum_{i=1}^\ell x_i^2 \quad\text{ with }\quad x_1 > x_2 > \cdots > x_\ell > 0$$ Notice $$x_1 \le \begin{cases}\sqrt{r - 129}, & r \ge 273\\ 11, & r \in [129,272]\end{cases} \implies \sum_{i=2}^\ell x_i^2 > 0$$

This implies $$\ell > 1$$ and we can strengthen above claim to:

Every $$r \ge 129$$ can be represented as a sum of $$\ell \ge 2$$ distinct squares.

As a corollary,

For $$N \ge 12$$, above algorithm produces a $$S \subset [1,N-1]$$ with $$f(S) = N^2$$.

For smaller $$N$$, not all $$N^2$$ can be expressed as a $$f(S)$$ for $$S \in [1,N-1]$$. By brute force again, one find the possible ones are $$N = 5,7$$ and all $$N \ge 9$$.

\begin{align*} \bigg(\sum_{x=1}^{n}x^2\bigg) &=\dfrac{n\big(n+1\big)\big(2n+1\big)}{6} \\ \text{The (n-1) sum minus n^2 should be zero}\\ \\ \bigg(\sum_{x=1}^{n-1}x^2\bigg)-(x)^2 &=\dfrac{(n-1)\big(n\big)\big(2n-1\big)}{6} -(n)^2 =0\\ \end{align*}

\begin{align*} (n-1)\big(n\big)\big(2n-1\big) - 6(n)^2 =0\\ n (2 n^2 - 9 n + 1)=0\\ \end{align*}

\begin{align*} n\in\bigg\{0, \dfrac{9 \pm\sqrt{73}}{4} \bigg\}\\ \\ \end{align*}

It appears that $$S=U=\{0\}.\space$$ There areno other integer solutions.

• So you've shown that $S=U$ doesn't work, but what about when $S$ is a strict subset of $U$? Sep 28 '21 at 7:01