求可得到的最大正整数

王守恩

`A`、`B`是两个有限数集，定义`A+B`为遍历`A`、`B`所得二元和之集。

构造含有`k`个不同正整数的集`S=\{0, s_1, s_2, …，s_k\}`，使得`S+S+S`可覆盖尽可能长的自然数前段`\{1, 2, 3, …，n\}`。

当`k=10`时，求最大的的正整数`n`.

.·.·.

如果k=3，按3位2进数最大能覆盖到7。
如果k=4，可以写程序（用的python，请自行脑补缩进）

1. 
   
2. for i1 in range(15):
   
3.   for i2 in range(i1,15):
   
4.    for i3 in range(i2,15):
   
5.     for i4 in range(i3,15):
   
6.      if set([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])<set([i1,i2,i3,i4,i1+i2,i1+i3,i1+i4,i2+i3,i2+i4,i3+i4,i1+i2+i3,i1+i2+i4,i1+i3+i4,i2+i3+i4]):
   
7.       print([i1,i2,i3,i4])

复制代码

没结果，而[1,2,4,8]可以覆盖到14
于是可以构造出[1,2,4,8,15,23,30,37,44,51]，这一列数能覆盖到57
当然57应该是可以改进的

暴力搜索可以得到：
[1,2,4,7,14]可以覆盖到23
[1, 2, 3, 6, 10, 20]
[1, 2, 4, 7, 14, 24]这两组都可以覆盖到33

然后，用后面那个解法我们可以拿[1,2,4,7,14,24,34,44,54,64]覆盖到73
不确定73是否可以改进，大概率可以
比如用[1, 2, 3, 6, 10, 20,34,...]

或许[1,2,3,6,10,16,26,40,54,74]可以覆盖到87
[1, 2, 3, 6, 10, 20,34,48,62,76]可以覆盖到89
[1,2,3,6,10,14,28,46,64,82]可以覆盖到99
python:

1. res=[0]
   
2. a=[1,2,3,6,10,14,28,46,64,82]
   
3. for i in a:
   
4.   for j in a:
   
5.    for k in a:
   
6.     if i<j<k:
   
7.      res+=[i,j,k,i+j,i+k,j+k,i+j+k]
   
8. 
   
9. for k in range(1+len(set(res))):
   
10.   if not (set(range(k+1))<=set(res)):
    
11.    print(k)
    
12.    break
    

复制代码

用贪心算法凑出来的都不是最好的，反而是在前面稍微减一点之后，在后面会得到一个更大的结果

无论如何，坑已挖好，就等大神了：）

hujunhua

M10验证

1. Plus @@@ Subsets[{1, 2, 3, 6, 10, 14, 28, 46, 64, 82}, {1, 3}] // Union
   
2. LengthWhile[%, %[[#]] == # &]

复制代码

输出：
Out[1]={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87,88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 102, 106, 110, 111, 112, 113, 116, 120, 124, 128, 129, 130, 131, 134, 138, 142, 146, 147, 148, 149, 152, 156, 160, 174, 192}
Out[2]=99

mathe

http://oeis.org/A001213