选数字

数学星空

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<p-1}$,只要$b!=0$,都可以构成一个解.所以通过适当的选择a和b,我们可以让最大元素适当的减少,比如对于10000,使用这种方法,选择素数101应该是问题不大的.

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]

1. 
   
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. }

复制代码