15# northwolves
5是mod 97的原根.根据mathe所说的(Ruzsa construction), 用mathematica得到的结果:
s={}; Do], {i, 96}]; Print]
{86,96,117,305,364 ...
wiley 发表于 2010-1-24 18:29 http://bbs.emath.ac.cn/images/common/back.gif
"5是mod 97的原根" 这个怎么求呢?请详细讲解一下,多谢
求一个素数p的原根g,就是相当于找一个元素,它模p的次数为p-1,于是我们对于p-1的任意因子d,$g^{(p-1)/d}!=1(mod p)$,而原根g的数目为$\varphi(p-1)$比例是非常高的,所以我们可以随便选择一些数,判断它是否是原根,直到找到一个原根就可以了.
而对于上面的构造方法,简单扩展一下,就可以发现实际上对于任何${a+b*g^i*(p-1)+i*p|0<=i<p-1}$,只要$b!=0$,都可以构成一个解.所以通过适当的选择a和b,我们可以让最大元素适当的减少,比如对于10000,使用这种方法,选择素数101应该是问题不大的.
22# northwolves
是用 mathematica 带的 PrimitiveRoot 函数 (不过只得到一个原根.wikipedia上说有办法可以从一个得到所有的).
根据mathe说的, 取 p=101 得到100个元素的解:
p = 101; r = PrimitiveRoot;
s = {}; Do], {i, p - 1}];
s = Sort; Print + 1]
{1,202,217,235,359,503,563,629,694,787,822,848,1004,1142,1237,1321,1345,1383,1385,1397,1510,1520,1869,1892,1905,1974,1980,2066,2256,2295,2311,2314,2647,2744,2825,2958,3188,3262,3308,3398,3426,3515,3606,3678,3755,3812,4165,4454,4527,4561,4586,4631,4639,4682,4753,4784,4851,4852,4893,4900,5160,5164,5391,5396,5577,5640,5816,6109,6281,6432,6476,6619,6628,6713,6734,6875,6907,7090,7170,7249,7299,7336,7524,7541,7571,7867,7889,8272,8443,8546,8730,9118,9138,9257,9268,9573,9823,9850,9879,9933}
取 p=103, 并且随机的试了几个b, 得到一个102个元素的子集且只有一个大于10000:
{1,168,238,293,300,435,440,451,482,491,736,738,1068,1105,1133,1695,1762,1839,1874,2003,2101,2109,2219,2367,2426,2452,2618,2638,2733,2746,2920,3159,3217,3309,3624,3805,3943,3962,4014,4173,4198,4222,4527,4603,4717,4804,5050,5082,5195,5278,5554,5558,5622,5651,5726,5729,5978,6271,6444,6561,6575,6804,7038,7044,7200,7426,7550,7604,7640,7767,7861,7952,7982,8093,8213,8247,8270,8292,8313,8352,8393,8641,8668,8714,8729,8767,8777,8851,8863,8932,9051,9101,9324,9454,9543,9587,9659,9811,9812,9829,9972,10005}
所以剔除最后一个, 得到101个元素的解.
20楼的文章给了一个 n^{1/2}+n^{1/4}+1 的上界, 所以有改进的空间, 楼主可以试试其他的选择, 比如换一个原根.
主题帖里暗藏有秘密，不过现在不能告诉你。:lol :lol
gxqcn 发表于 2010-1-24 08:25 http://bbs.emath.ac.cn/images/common/back.gif
:L 这不等于告诉大家了吗
哪有告诉大家？
我还摸不着头脑呢。:dizzy:
只是胃口被他吊起来了而已。:M:
取 p=103, 并且随机的试了几个b, 得到一个102个元素的子集且只有一个大于10000
我用mathematica7.0算出来不一样嘛....
{1,122,238,451,512,546,600,636,671,736,948,978,1025,1089,1105,1209,1266,1389,1580,1710,1725,1762,1773,2097,2101,2120,2452,2583,2638,2655,2746,2808,2920,2942,3059,3217,3302,3536,3542,3698,3795,3805,3942,3943,3984,3993,4198,4222,4265,4603,4635,4717,4745,4790,4804,4811,4850,5050,5278,5376,5505,5549,5554,5721,5822,5928,6041,6120,6271,6470,6503,7172,7304,7426,7439,7464,7742,7861,8072,8641,8668,8697,8699,8767,8843,8851,8863,8932,9060,9113,9153,9228,9231,9371,9454,9480,9737,9811,9829,10077,10163,10313}
本帖最后由 wiley 于 2010-1-25 15:16 编辑
楼主把7069设成了背景色...
不过mathe已经给了9972的解了, 所以那个数好像没什么意义.
----- ----- ----- ----- -----
回楼上的, 还要加一个自由度(等价于29楼的b), 我是根据你那片文章44页上的Lindstrom的公式.
p = 103; r = PrimitiveRoot; f = 35;
s = {}; Do], {i, p - 1}];
s = Sort; Print + 1]
呵,多谢!
如23#,数据还可以进行平移的，比如:
(16:59) gp > gb(103)
%6 = [1, 37, 64, 169, 174, 252, 352, 367, 563, 709, 950, 1145, 1221, 1519, 1550,
1639, 1769, 1793, 1894, 1940, 1946, 1963, 2210, 2277, 2280, 2296, 2322, 2487, 2
650, 2729, 2731, 2778, 2886, 2887, 2958, 3031, 3155, 3247, 3254, 3383, 3592, 378
4, 4130, 4169, 4227, 4257, 4479, 4661, 4705, 4718, 4939, 4943, 4953, 5128, 5218,
5278, 5331, 5385, 5418, 5590, 5684, 5750, 5848, 5970, 5981, 6010, 6129, 6243, 6
264, 6328, 6584, 6612, 6750, 6798, 6830, 7043, 7093, 7134, 7227, 7245, 7283, 740
6, 7414, 7457, 7532, 7638, 7733, 8000, 8261, 8322, 8812, 8880, 8889, 8954, 9097,
9500, 9535, 9555, 9617, 9639, 9651, 9676]
gb(p)=
{
local(r,v,m,u,d,di,bd,bv);
v=vector(p-1);bv=vector(p-1);
m=p*(p-1);bd=0;
r=component(znprimroot(p),2);
for(f=1,p-2,
if(gcd(f,p-1)!=1,next());
for(a=1,p-1,
for(t=1,p-1,
u=Mod(t*p*f,m)+a*(p-1)*Mod(r,m)^t;
v=component(u,2);
);
v=vecsort(v);
d=m+v-v;di=1;
for(t=2,p-1,
u=v-v;
if(u>d,d=u;di=t)
);u=v;
if(d>bd,
for(t=1,p-1,
if(v>=u,bv=v-u+1,bv=v+m-u+1)
);
bv=vecsort(bv);bd=d
)
);
);
bv
}