7#中方法选择p=9973就可以得到一个有9972个数的方案
而题目中如果允许两两之和中的"两两"为同一个数,那么就正好是Optimal Golomb Ruler (http://www.research.att.com/~njas/sequences/A003022)
http://topic.csdn ...
mathe 发表于 2010-1-24 14:51 http://bbs.emath.ac.cn/images/common/back.gif
我个人觉得N取不到那么大.
$N<sqrt(\frac{10^8}{2})$,能验证但无法证明
再降低难度: 如果在1-1600间取数,N最大多少?取哪些数字?
本帖最后由 KeyTo9_Fans 于 2010-1-24 16:25 编辑
5#给出的是满足楼主要求的可行解。我没有说那是最优解。因为我是用贪心的方法做了一下，发现和那个数列对上了。
还是mathe的方法好。可是mathe总是喜欢给式子，不喜欢举例子，让人很难吃得透。
另外，楼主的题目与9楼说的尺子没关系吧？
楼主并不要求把所有的和都加出来，可以留空位的。
11#把2的位置放错了吧？貌似应该放在根号外面，得到20000。（好像就是2#的结果）
所以mathe的9972还是可信的。
楼主不如把范围也一般化了吧？我们看看对于小范围的解是否有规律，然后再大致估算大范围的解。
#####
对不起，我理解错了。9楼说的是对的。
按http://www.research.att.com/~njas/sequences/b011185.txt ,1-10000间最多可取67个数.
事实上,如果取以下70个数:
143, 288, 435, 584, 735, 888, 1043, 1200, 1288, 1449, 1612, 1706, 1873, 2042, 2142, 2315, 2419, 2596, 2704, 2885, 2997, 3182, 3298, 3416, 3607, 3729, 3853, 3979, 4178, 4308, 4440, 4574, 4710, 4848, 4988, 5130, 5274, 5420, 5568, 5718, 5870, 6024, 6109, 6267, 6427, 6589, 6682, 6848, 7016, 7115, 7287, 7390, 7566, 7673, 7853, 7964, 8148, 8263, 8380, 8570, 8691, 8814, 9010, 9137, 9266, 9397, 9530, 9665, 9802, 9941
显然是满足题目要求的
但按7#mathe的结论,1-10000间可取到至少96个数,如果96个数该怎么取呢?
事实上,14楼可以有一个71个数的方案:
1,144,289,436,585,736,889,1044,1201,1289,1450,1613,1707,1874,2043,2143,2316,2420,2597,2705,2886,2998,3183,3299,3417,3608,3730,3854,3980,4179,4309,4441,4575,4711,4849,4989,5131,5275,5421,5569,5719,5871,6025,6110,6268,6428,6590,6683,6849,7017,7116,7288,7391,7567,7674,7854,7965,8149,8264,8381,8571,8692,8815,9011,9138,9267,9398,9531,9666,9803,9942
15# northwolves
5是mod 97的原根.根据mathe所说的(Ruzsa construction), 用mathematica得到的结果:
s={}; Do], {i, 96}]; Print]
{86,96,117,305,364,365,369,412,538,577,605,619,791,815,916,938,953,1182,1350,1352,1377,1406,1495,1556,1695,1846,2259,2345,2450,2501,2594,2630,2649,2752,2851,2869,2979,3067,3125,3133,3348,3490,3647,3673,3679,3753,3810,4011,4045,4273,4338,4355,4400,4407,4440,4470,4516,4519,4560,4701,4856,4872,5008,5132,5226,5416,5491,5833,5871,5883,5966,6058,6142,6464,6980,6991,7000,7078,7091,7308,7438,7578,7649,7762,7815,7883,8060,8219,8292,8327,8613,8685,8762,8965,8988,9294}
这个错了,应该
Mod
改为
Mod
这个根据中国剩余定理p-1关于p的数论倒数为p-1,p关于p-1的数论倒数为1,所以为
$(p-1)^2g^i+i*p(mod p(p-1))$