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

Question

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.

Answer 1

\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.

Answer 2

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