选数字

northwolves

在$1-10^8$范围内选出$N$个数字,使其两两之和互不相等. $N$最大值是多少? 7069

数学星空

由于每两个数的和均不相同,则N个数可构成$N*(N-1)/2$个不同的数, 因其最大值为$10^8+10^8-1$,最小值为3,则有 $N*(N-1)/2<=2*10^8-3$得:$N<=20000$

KeyTo9_Fans

楼上给的上界太大了吧？ 我列了最小的几个数： 1,2,3,5,8,13,21,30 然后搜了一下，果然有这个数列！ https://oeis.org/search?q=2%2C3% ... e=english&go=Search 与楼主的说法完全相同。

litaoye

可以用斐波那契求个下界。记得以前好像讨论过100以内的。

KeyTo9_Fans

楼上给的下界太小了吧？ 不是斐波那契数列，虽然前几项看起来很像。 这里已经给出了N=2024的解： http://www.research.att.com/~njas/sequences/b011185.txt 这里虽然条件更严格 http://www.research.att.com/~njas/sequences/A005282 但得到的解反而比前面的大： N=2025 http://www.research.att.com/~njas/sequences/b005282.txt

gxqcn

主题帖里暗藏有秘密，不过现在不能告诉你。

mathe

上面给出的这些结果都不够好. 任意选择一个素数p使得$(p-1)p<10^8$

对于$[0,(p-1)p]$的整数根据其关于模p-1和p的余数可以看成二维空间$(x,y)$中的整数点,其中$0<=x

northwolves

楼上给的下界太小了吧？ 不是斐波那契数列，虽然前几项看起来很像。 这里已经给出了N=2024的解： http://www.research.att.com/~njas/sequences/b011185.txt 这里虽然条件更严格 http://www.research ... KeyTo9_Fans 发表于 2010-1-23 22:28

这个连接与我的题目相似但不完全相同

mathe

7#中方法选择p=9973就可以得到一个有9972个数的方案 而题目中如果允许两两之和中的"两两"为同一个数,那么就正好是Optimal Golomb Ruler (http://www.research.att.com/~njas/sequences/A003022) http://topic.csdn.net/t/20020811/00/931488.html

northwolves

先降低难度: 如果在1-10000间取数,N最大多少?取哪些数字?