100内,寻找一个集合A,元素全是自然数,得两两相加能表示2以上100以内所有的数？

xiugakei

100内,寻找一个集合A,元素全是自然数,得两两相加能表示2以上100以内所有的数？
比如1,2,4,5,....
2=1+1
3=1+2
4=2+2
5=1+4......
求A的数量上最小的集合。

最好推广到1000,10000

litaoye

是不是费伯纳妾的问题?

无心人

A = [1..50]可以么？

gxqcn

改成相减就是最少刻度尺问题。
感觉楼主这个问题也蛮有实际意义的。

northwolves

原帖由 litaoye 于 2008-12-25 12:30 发表
是不是费伯纳妾的问题?

又见老朋友，还欧拉娶妻呢

northwolves

手工推算了一个，不知是否最少的那个：
1, 2, 4, 5, 8, 10, 16, 17, 20, 21, 32, 34, 40, 42, 64, 65, 68, 69, 80, 81, 84, 85

northwolves

应该与二进制或四进制有关：
1  0000001
2  0000010
4  0000100
5  0000101
8  0001000
10  0001010
16  0010000
17  0010001
20  0010100
21  0010101
32  0100000
34  0100010
40  0101000
42  0101010
64  1000000
65  1000001
68  1000100
69  1000101
80  1010000
81  1010001
84  1010100
85  1010101

northwolves

竟然搜到了这个序列：
A126684

xiugakei

高手!这道题我心里还没底,我算了50的,100的还在推。我还想推广到无穷。
1, 2, 4, 5, 8, 10, 16, 17, 20, 21, 32, 34, 40, 42, 64, 65, 68, 69, 80, 81, 84, 85肯定大了,最大的数不需要超过70（估算的）

xiugakei

我的估算是100内,只需要20个（10*2）左右
推广之后是
n只需要1.5*√n~2*√n个。