如何找到整数列表（多集，大小 n），其中集合的均方根是整数？

Question

我已经找到了this one

暴力破解当然可以，但是还有其他办法吗？有没有办法找到所有的多重集？有没有办法找出在一定限制下存在多少种组合？

也许这个问题对SO来说太数学了，如果是这样我会移动它。

我通过生成数字列表的所有可能组合，然后检查整数 RMS，在 javascript 中创建了 my own version。这些是集合，而不是多重集合。

Answer 1

编辑：我用 N 表示求和值，用 K 表示方块数。

multi-sets的数量增长很快，所以N应该有一个合理的值。所以这个问题等同于用标称1,4,9,25...的K个硬币改变总和N（并且变体的数量可以使用动态规划来计算）。

最简单的实现是递归的——我们只生成所有可能的加数。在我的 Delphi 实现中，为了简单起见，我在字符串（而不是列表）中收集加数。

请注意，这样的实现可能会一次又一次地生成相同的序列 - 请注意我示例中的 {5,7} 结束序列。为了提高性能（对于相当大的 N 和 K 值很重要），将生成的序列存储在 table 或映射（使用 {N;K;Min} 键）中是值得的。在那种情况下，从大加数到小加数的生成会更好，因为小加数会产生很多重复模式。

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

如何找到整数列表（多集，大小 n），其中集合的均方根是整数？

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

math

rms