Sum of squares of distinct integers

Question

Could you please suggest any algorithm ideas for solving the following problem:

Given positive integers S, K ≤ N. Find distinct positive integers x₁, x₂, ..., x_K such that

x₁² + x₂² + ... + x_K² = S

x_i ≤ N and x_i < x_i+1 for all i = 1...K.

So far I know that I should start searching for the largest x below the square root of S.

Every positive number can be written as a sum of at most 4 squares. See for instance the answer I have given [here](https://stackoverflow.com/a/41556521/5459839) which gives an implementation for finding *x1, x2, x3 and x4* (or fewer). — trincot, Nov 18 '18 at 22:41
@trincot thanks for this, my case is a bit different, because integers should be distinct, which is not case for 4-square theorem, but thanks for direction to think — torayeff, Nov 18 '18 at 22:48
Possible duplicate of [Represent natural number as sum of distinct squares](https://stackoverflow.com/questions/26222693/represent-natural-number-as-sum-of-distinct-squares) — גלעד ברקן, Nov 19 '18 at 15:30
I don't understand the role of N in the question. Any xᵢ will be ≤ S, so that xᵢ ≤ N will always be true. So why mention an N at all? Couldn't the problem simply be stated as “Given positive integers S and K, find [...]” omitting the “xᵢ ≤ N and” part? — Walter Tross, Nov 19 '18 at 18:12
@WalterTross sure N matters. For example, there are 3 ways to sum to 178 from 5 positive integers. But there are only two if we restrict the largest integer to 10. — גלעד ברקן, Nov 19 '18 at 19:10
I assumed S, K ≤ N means S ≤ N and K ≤ N, but it seems I was wrong. I would rephrase the problem as "given positive integers S, K and N, with K ≤ N [...]", then. — Walter Tross, Nov 19 '18 at 19:49

score 1 · Answer 1 · answered Nov 19 '18 at 19:19

Here's a slightly optimised brute force. As I linked to in the comments (and close vote), it seems to me we could modify the standard subset sum problem to work with squares.

JavaScript code (ellipsis at the end of an output means add the rest of the numbers down to 1):

function f(S, K, N){
  function g(s, k, n, c){
    const minS = k*(k+1)*(2*k+1)/6;
    const maxN = Math.min(
      n,
      ~~Math.sqrt(s - (k-1)*k*(2*k-1)/6)
    );

    if (s < minS || maxN < 1)
      return [];
    else if (s == minS)
      return [c.concat([k, '...'])];
    if (k == 0)
      return [];
    
    return g(s - maxN*maxN, k - 1, maxN - 1, c.slice().concat(maxN))
      .concat(
        g(s, k, maxN - 1, c)
      );
  }
  
  return g(S, K, N, []);
}

for (let j=1; j<6; j++)
  console.log(JSON.stringify([178, j, f(178, j, 100)]));

console.log(JSON.stringify([178, 5, f(178, 5, 10)]));

score 1 · Answer 2 · answered Nov 20 '18 at 12:47

Since you ask for an algorithm idea, and not a precise answer, so here is my 2 cents.

You can transform your problem to get rid of the squares by finding all perfect squares ( e.g. 1, 4, 9, 16, 25...) from 1 to S and put them into a set called PerfectSquareSetLessThanS.

Then, if you can solve the following (more general) problem, you can easily solve your original problem.

General problem:

Given an arbitary set V, find a subset W of V that has exactly K numbers such that they sum to S.

While I don't yet have a precise solution, your general problem looks a lot like a well known problem called the 3SUM problem.

The 3SUM problem asks if given a set of n numbers, are there a set of 3 numbers whose sum is 0. The wikipedia page outlines an algorithm to search for such tupple.

Note that the 3SUM problems have different variants, 1 of which is the k-SUM (substitute 3 by k in the above paragraph) , and another one is the non-zero sum variant. Maybe you could find a combination of these two variants to build your generalized solution.

Sum of squares of distinct integers

2 Answers2