How do I find a list (multiset, size n) of integers where the root-mean-square of the set is an integer?

Question

I already found this one

Brute force is possible of course, but are there any other ways? Is there a way to find all multisets? Is there a way to find out how many combinations exist under a certain limit?

Perhaps this question is too mathy for SO, if that is the case I'll move it.

I created my own version in javascript by generating all possible combinations of a list of numbers, then checking for integer RMS. These are sets though, not multisets.

Answer 1

Edit: I used N for sum value and K for the number of squares.

Number of multi-sets grows fast, so N should have reasonable value. So this problem is equivalent to changing sum N by K coins with nominals 1,4,9,25... (and the number of variants might be calculated using dynamic programming).

The simplest implementation is recursive - we just generate all possible addends. In my Delphi implementation I collect summands in string (instead of list) for simplicity.

Note that such implementation might generate the same sequences again and again - note {5,7} end-sequence in my example. To improve performance (important for rather large values of N and K), it is worth to store generated sequences in table or map (with {N;K;Min} key). In that case generation from large summands to smaller ones would be better, because small summands give a lot of repeating patterns.

procedure FSP(N, K, Minn: Integer; Reslt: string);
var
  i: Integer;
begin
  if (K = 0) then begin
    if (N = 0) then
      Memo1.Lines.Add(Reslt); //yield result
    Exit;
  end;

  i := Minn;
  while (i * i <= N) do begin
    FSP(N - i * i, K - 1, i, Reslt + Format('%d ', [i]));
    i := i + 1;
  end;
end;

procedure FindSquarePartitions(N, K: integer);
begin
  FSP(N, K, 1, '');
end;

 FindSquarePartitions(101, 5);

1 1 1 7 7 
1 1 3 3 9 
1 1 5 5 7 
1 2 4 4 8 
1 5 5 5 5 
2 2 2 5 8 
2 3 4 6 6 
2 4 4 4 7 
3 3 3 5 7