数学研发论坛

 找回密码
 欢迎注册
楼主: northwolves

[讨论] 选数字

[复制链接]
 楼主| 发表于 2010-1-24 15:24:07 | 显示全部楼层
7#中方法选择p=9973就可以得到一个有9972个数的方案
而题目中如果允许两两之和中的"两两"为同一个数,那么就正好是Optimal Golomb Ruler (http://www.research.att.com/~njas/sequences/A003022)
http://topic.csdn ...
mathe 发表于 2010-1-24 14:51

我个人觉得N取不到那么大.
$N<sqrt(\frac{10^8}{2})$,能验证但无法证明
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-1-24 15:45:43 | 显示全部楼层
再降低难度: 如果在1-1600间取数,N最大多少?取哪些数字?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-24 16:05:52 | 显示全部楼层
本帖最后由 KeyTo9_Fans 于 2010-1-24 16:25 编辑

5#给出的是满足楼主要求的可行解。我没有说那是最优解。因为我是用贪心的方法做了一下,发现和那个数列对上了。

还是mathe的方法好。可是mathe总是喜欢给式子,不喜欢举例子,让人很难吃得透。

另外,楼主的题目与9楼说的尺子没关系吧?

楼主并不要求把所有的和都加出来,可以留空位的。

11#把2的位置放错了吧?貌似应该放在根号外面,得到20000。(好像就是2#的结果)

所以mathe的9972还是可信的。

楼主不如把范围也一般化了吧?我们看看对于小范围的解是否有规律,然后再大致估算大范围的解。

#####

对不起,我理解错了。9楼说的是对的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-1-24 16:54:33 | 显示全部楼层
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
显然是满足题目要求的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-1-24 16:57:57 | 显示全部楼层
但按7#mathe的结论,1-10000间可取到至少96个数,如果96个数该怎么取呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-1-24 17:20:14 | 显示全部楼层
事实上,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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-24 18:29:35 | 显示全部楼层
15# northwolves

5是mod 97的原根.  根据mathe所说的(Ruzsa construction), 用mathematica得到的结果:

s={}; Do[s = Append[s, Mod[97*i + 96*5^i, 9312]], {i, 96}]; Print[Sort]

{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}

评分

参与人数 1鲜花 +2 收起 理由
northwolves + 2 验证通过!!!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-24 21:36:33 | 显示全部楼层
这个错了,应该
Mod[97*i + 96*5^i, 9312]
改为
Mod[97*i + 96*96*5^i, 9312]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-24 21:37:51 | 显示全部楼层
这个根据中国剩余定理p-1关于p的数论倒数为p-1,p关于p-1的数论倒数为1,所以为
$(p-1)^2g^i+i*p(mod p(p-1))$

评分

参与人数 1鲜花 +4 收起 理由
northwolves + 4 感谢mathe强大的理论支持!!!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-1-24 22:03:37 | 显示全部楼层
11.jpg
12.jpg
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-3-9 15:07 , Processed in 0.091403 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表