选数字

数学星空

northwolves

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 ... wiley 发表于 2010-1-24 18:29

"5是mod 97的原根" 这个怎么求呢?请详细讲解一下,多谢

mathe

求一个素数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

wiley

22# northwolves 是用 mathematica 带的 PrimitiveRoot 函数 (不过只得到一个原根. wikipedia上说有办法可以从一个得到所有的). 根据mathe说的, 取 p=101 得到100个元素的解: p = 101; r = PrimitiveRoot[p]; s = {}; Do[s = Append[s, Mod[p*i + (p - 1)*r^i, p (p - 1)]], {i, p - 1}]; s = Sort; Print[s - First + 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$ 的上界, 所以有改进的空间, 楼主可以试试其他的选择, 比如换一个原根.

风云剑

主题帖里暗藏有秘密，不过现在不能告诉你。 gxqcn 发表于 2010-1-24 08:25

这不等于告诉大家了吗

KeyTo9_Fans

哪有告诉大家？ 我还摸不着头脑呢。 只是胃口被他吊起来了而已。

数学星空

取 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

楼主把7069设成了背景色... 不过mathe已经给了9972的解了, 所以那个数好像没什么意义. ----- ----- ----- ----- ----- 回楼上的, 还要加一个自由度(等价于29楼的b), 我是根据你那片文章44页上的Lindstrom的公式. p = 103; r = PrimitiveRoot[p]; f = 35; s = {}; Do[s = Append[s, Mod[p*f*i + (p - 1)*r^i, p (p - 1)]], {i, p - 1}]; s = Sort; Print[s - First + 1]

数学星空

呵,多谢!

mathe

如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]

2. gb(p)=
3. {
4. local(r,v,m,u,d,di,bd,bv);
5. v=vector(p-1);bv=vector(p-1);
6. m=p*(p-1);bd=0;
7. r=component(znprimroot(p),2);
8. for(f=1,p-2,
9. if(gcd(f,p-1)!=1,next());
10. for(a=1,p-1,
11. for(t=1,p-1,
12. u=Mod(t*p*f,m)+a*(p-1)*Mod(r,m)^t;
13. v[t]=component(u,2);
14. );
15. v=vecsort(v);
16. d=m+v[1]-v[p-1];di=1;
17. for(t=2,p-1,
18. u=v[t]-v[t-1];
19. if(u>d,d=u;di=t)
20. );u=v[di];
21. if(d>bd,
22. for(t=1,p-1,
23. if(v[t]>=u,bv[t]=v[t]-u+1,bv[t]=v[t]+m-u+1)
24. );
25. bv=vecsort(bv);bd=d
26. )
27. );
28. );
29. bv
30. }

复制代码