如何用任何连续数的唯一和构造一个正整数序列？

Question

例如:1,2,4,5有以下总和:

1,2,4,5

3,6,9

7,11

12

每一笔钱都是独一无二的.

现在,1,2,3有以下总和:

1,2,3

3,5

6

并且显然不是每一笔钱都是独一无二的.

是否有任何有效的方法来生成与第一个示例类似的序列,目标是尽可能小地选择每个数字(不仅仅是1,2,4,8,16 ......)？我知道我可以编写一个程序来强制执行这个程序,但我只是好奇它能以更好的方式完成.

Answer 1

我想你在这里寻找的是Golomb统治者.如果你将上面描述的数字作为标记之间的距离,你就已经描述了一个Golomb标尺.当标尺上的标记集没有重复时,正如您所描述的那样,这就是使它成为Golomb标尺的原因.

似乎描述Golomb标尺的标准方法是通过表示每个标记的位置,而不是它们之间的距离.因此,您的1,2,4,5将被描述为Golomb Ruler 0-1-3-7-12.

引用维基百科:

目前,找到任意阶数n的OGR(其中n以一元给出)的复杂性是未知的.在过去,有人猜测这是一个NP难问题.与Golomb统治者的构造相关的问题可证明是NP难的,其中还注意到没有已知的NP完全问题具有与找到Golomb统治者类似的风味.