7
$\begingroup$

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.

$\endgroup$
10
  • 3
    $\begingroup$ 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? $\endgroup$
    – saulspatz
    Jun 15 '21 at 19:37
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Subset_sum_problem $\endgroup$
    – saulspatz
    Jun 15 '21 at 19:38
  • 3
    $\begingroup$ It should be $\sum_{i \in S} i^2=N^2$ $\endgroup$
    – M A Pelto
    Jun 15 '21 at 19:38
  • 4
    $\begingroup$ 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? $\endgroup$
    – davidlowryduda
    Jun 15 '21 at 19:39
  • 2
    $\begingroup$ 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. $\endgroup$
    – Juan Amado
    Jun 22 '21 at 16:06
2
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.