手串上穿有六颗珠子，求各珠子上的数字。

wayne

完美差分集 Perfect Difference Sethttp://mathworld.wolfram.com/PerfectDifferenceSet.html

A set of residues (mod ) such that every nonzero residue can be uniquely expressed in the form . Examples include (mod 7) and (mod 13). A necessary condition for a difference set to exist is that be of the form . A sufficient condition is that be a prime power. Perfect sets can be used in the construction of perfect rulers.

mathe

1. #include<stdio.h>
   
2. #include <string.h>
   
3. 
   
4. #ifndef N
   
5. #define N  5
   
6. #endif
   
7. #define TS ((N-1)*N+1)
   
8. #define WORDC   ((TS+sizeof(int)-1)/sizeof(int))
   
9. #define OFFSET(x)  ((x)/32)
   
10. #define INDEX(x)   ((x)&31)
    
11. #define ISSET(x)   ((ts[OFFSET(x)]&(1<<INDEX(x)))!=0)
    
12. #define REVERT(x)  (ts[OFFSET(x)]^=(1<<INDEX(x)))
    
13. 
    
14. int db[N][N];
    
15. int cc;
    
16. int du;
    
17. int ts[WORDC];
    
18. int sel;
    
19. 
    
20. void set_used(int x)
    
21. {
    
22.     if(!ISSET(x)){
    
23.        REVERT(x); REVERT(TS-x);
    
24.     }
    
25. }
    
26. 
    
27. void set_unused(int x)
    
28. {
    
29.     if(ISSET(x)){
    
30.        REVERT(x); REVERT(TS-x);
    
31.     }
    
32. }
    
33. 
    
34. void init()
    
35. {
    
36.     db[0][0]=1; cc=1; du=1;sel=1;
    
37.     set_used(1);
    
38. }
    
39. 
    
40. int left_test(int row, int rc)
    
41. {
    
42.     int cur_sum=sel;
    
43.     int k;
    
44.     for(k=rc-1;k>=0;k--){
    
45.         cur_sum+=db[row][k];
    
46.         if(cur_sum<TS&&!ISSET(cur_sum)){
    
47.             set_used(cur_sum);
    
48.             continue;
    
49.         }
    
50.         for(;k<rc-1;k++){
    
51.             cur_sum-=db[row][k];
    
52.             set_unused(cur_sum);
    
53.         }
    
54.         return 0;
    
55.     }
    
56.     return 1;
    
57. }
    
58. 
    
59. int right_test(int row, int rc)
    
60. {
    
61.     int cur_sum=sel;
    
62.     int k;
    
63.     for(k=0;k<rc;k++){
    
64.         cur_sum+=db[row][k];
    
65.         if(cur_sum<TS&&!ISSET(cur_sum)){
    
66.              set_used(cur_sum);
    
67.              continue;
    
68.         }
    
69.         for(;k>0;k--){
    
70.             cur_sum-=db[row][k];
    
71.             set_unused(cur_sum);
    
72.         }
    
73.         return 0;
    
74.     }
    
75.     return 1;
    
76. }
    
77. 
    
78. void reverse(int r, int c)
    
79. {
    
80.     int i;
    
81.     for(i=0;i<c/2;i++){
    
82.        int tmp=db[r][i];
    
83.        db[r][i]=db[r][c-1-i];
    
84.        db[r][c-1-i]=tmp;
    
85.     }
    
86. }
    
87. 
    
88. int merge_test(int r1, int c1, int r2, int c2, int d1, int d2)
    
89. {
    
90.     int i,j;
    
91.     int tsb[WORDC];
    
92.     if(d1<0)reverse(r1,c1);
    
93.     if(d2<0)reverse(r2,c2);
    
94.     db[r1][c1]=sel;
    
95.     memcpy(tsb,ts,sizeof(tsb));
    
96.     for(i=0;i<=c2;i++)db[r1][i+c1+1]=db[r2][i];
    
97.     for(i=0;i<=c1;i++){
    
98.        int sum=0;
    
99.        for(j=i;j<=c1;j++)sum+=db[r1][j];
    
100.        if(i<c1){
     
101.            if(sum>=TS||ISSET(sum)){
     
102.                 goto restore_state;
     
103.            }
     
104.            set_used(sum);
     
105.        }
     
106.        for(;j<c1+c2+1;j++){
     
107.            sum+=db[r1][j];
     
108.            if(sum>=TS||ISSET(sum)){
     
109.               goto restore_state;
     
110.            }
     
111.            set_used(sum);
     
112.        }
     
113.     }
     
114.     for(i=r2;i<cc-1;i++){//move other row forward
     
115.         for(j=0;;j++){
     
116.             db[i][j]=db[i+1][j];
     
117.             if(db[i][j]==0)break;
     
118.         }
     
119.     }
     
120.     cc--;
     
121.     du++;
     
122.     return 1;
     
123. restore_state:
     
124.     db[r1][c1]=0;
     
125.     if(d1<0)reverse(r1,c1);
     
126.     if(d2<0)reverse(r2,c2);
     
127.     memcpy(ts,tsb,sizeof(tsb));
     
128.     return 0;
     
129. }
     
130. 
     
131. void merge_revert(int r1, int c1, int r2, int c2, int d1, int d2)
     
132. {
     
133.     int i,j;
     
134.     for(i=cc-1;i>=r2;i--){
     
135.         for(j=0;;j++){
     
136.             db[i+1][j]=db[i][j];
     
137.             if(db[i][j]==0)break;
     
138.         }
     
139.     }
     
140.     cc++;du--;
     
141.     for(i=0;i<=c1;i++){
     
142.        int sum=0;
     
143.        for(j=i;j<=c1;j++)sum+=db[r1][j];
     
144.        if(i<c1){
     
145.            set_unused(sum);
     
146.        }
     
147.        for(;j<c1+c2+1;j++){
     
148.            sum+=db[r1][j];
     
149.            set_unused(sum);
     
150.        }
     
151.     }
     
152.     db[r1][c1]=0;
     
153.     for(i=0;i<=c2;i++){
     
154.        db[r2][i]=db[r1][c1+1+i];
     
155.     }
     
156.     if(d1<0)reverse(r1,c1);
     
157.     if(d2<0)reverse(r2,c2);
     
158. }
     
159. void left_unset(int row, int rc)
     
160. {
     
161.     int cur_sum=sel;
     
162.     int k;
     
163.     for(k=rc-1;k>=0;k--){
     
164.         cur_sum+=db[row][k];
     
165.         set_unused(cur_sum);
     
166.     }
     
167. }
     
168. 
     
169. void right_unset(int row, int rc)
     
170. {
     
171.     int cur_sum=sel;
     
172.     int k;
     
173.     for(k=0;k<rc;k++){
     
174.         cur_sum+=db[row][k];
     
175.         set_unused(cur_sum);
     
176.     }
     
177. }
     
178. 
     
179. void go_next_sel()
     
180. {
     
181.     for(;sel<TS&&ISSET(sel);sel++);
     
182. }
     
183. 
     
184. int get_row_len(int row)
     
185. {
     
186.     int j;
     
187.     for(j=0;j<N;j++){
     
188.        if(db[row][j]==0)return j;
     
189.     }
     
190.     return j;
     
191. }
     
192. 
     
193. void output_result()
     
194. {
     
195.     int sum=TS;
     
196.     int k;
     
197.     for(k=0;k<N-1;k++){
     
198.        printf("%d ",db[0][k]);
     
199.        sum-=db[0][k];
     
200.     }
     
201.     printf("%d\n",sum);
     
202. }
     
203. 
     
204. void try_next()
     
205. {
     
206.     int try_sel;
     
207.     int i,j;
     
208.     go_next_sel();
     
209.     try_sel=sel;
     
210.     if(sel==TS){
     
211.         output_result();
     
212.         return;
     
213.     }
     
214.     set_used(sel);
     
215.     if(du+cc<=N-2){
     
216.         //try use sel in new row
     
217.         db[cc][0]=sel;db[cc][1]=0;cc++;du++;
     
218.         try_next();
     
219.         sel = try_sel;//restore
     
220.         du--;cc--;
     
221.     }
     
222.     if(du+cc<=N-1){
     
223.       for(i=0;i<cc;i++){//try append after the right of one row
     
224.         int j=get_row_len(i);
     
225.         if(left_test(i,j)==0)continue;
     
226.         db[i][j]=sel;db[i][j+1]=0;
     
227.         du++;
     
228.         try_next();
     
229.         sel=try_sel;du--;db[i][j]=0;
     
230.         left_unset(i,j);
     
231.       }
     
232.       for(i=0;i<cc;i++){//try insert before first element
     
233.         int j=get_row_len(i);
     
234.         if(j<=1)continue;
     
235.         if(right_test(i,j)==0)continue;
     
236.         int k;
     
237.         for(k=j;k>=0;k--)db[i][k+1]=db[i][k];db[i][0]=sel;
     
238.         du++;
     
239.         try_next();
     
240.         sel=try_sel;du--;
     
241.         for(k=0;k<=j;k++)db[i][k]=db[i][k+1];
     
242.         right_unset(i,j);
     
243.       }
     
244.     }
     
245.     for(i=0;i<cc;i++){
     
246.         int ri=get_row_len(i);
     
247.         for(j=i+1;j<cc;j++){//try connect two rows
     
248.             int rj=get_row_len(j);
     
249.             if(merge_test(i,ri,j,rj,1,1)){
     
250.                 try_next();
     
251.                 sel=try_sel;
     
252.                 merge_revert(i,ri,j,rj,1,1);
     
253.             }
     
254.             if(rj>1){
     
255.                 if(merge_test(i,ri,j,rj,1,-1)){
     
256.                     try_next();
     
257.                     sel=try_sel;
     
258.                     merge_revert(i,ri,j,rj,1,-1);
     
259.                 }
     
260.             }
     
261.             if(ri>1){
     
262.                 if(merge_test(i,ri,j,rj,-1,1)){
     
263.                     try_next();
     
264.                     sel=try_sel;
     
265.                     merge_revert(i,ri,j,rj,-1,1);
     
266.                 }
     
267.             }
     
268.             if(ri>1&&rj>1){
     
269.                 if(merge_test(i,ri,j,rj,-1,-1)){
     
270.                     try_next();
     
271.                     sel=try_sel;
     
272.                     merge_revert(i,ri,j,rj,-1,-1);
     
273.                 }
     
274.             }
     
275.         }
     
276.     }
     
277.     set_unused(sel);
     
278. }
     
279. 
     
280. int main()
     
281. {
     
282.     init();
     
283.     try_next();
     
284.     return 0;
     
285. }
     

复制代码

mathe

N=18
9 26 1 17 2 10 4 7 38 5 8 24 15 42 6 22 3 68
17 14 1 7 3 27 6 12 23 5 19 2 51 9 4 16 34 57
2 8 12 31 3 26 1 6 9 32 18 5 14 21 4 13 11 91
6 1 11 26 35 20 2 8 13 4 15 9 5 31 3 50 16 52
4 34 1 27 3 13 2 6 50 5 9 11 12 10 7 19 41 53
4 12 17 5 23 2 24 15 31 6 3 10 1 7 35 32 36 44
1 14 39 19 2 10 28 8 35 6 3 13 4 7 18 5 32 63
16 5 34 12 1 30 2 8 17 37 7 4 15 3 6 14 36 60
6 4 18 39 1 41 7 17 8 5 14 2 31 3 9 11 15 76
8 7 4 6 23 1 12 9 5 38 16 28 3 32 37 2 18 58
17 32 4 24 5 1 13 25 2 10 8 3 52 26 9 7 15 54
3 8 2 15 16 32 7 29 1 5 14 4 22 12 9 50 27 51
29 25 16 30 1 5 9 8 4 7 32 24 18 2 35 3 10 49
17 28 1 12 36 19 25 7 11 4 5 30 3 21 2 8 6 72
14 1 12 23 3 7 21 16 18 22 2 6 11 32 20 5 4 90
12 4 25 2 5 1 9 13 40 11 3 21 26 19 20 18 34 44
4 5 1 19 3 12 2 16 43 8 13 26 24 7 41 27 11 45
24 1 15 28 6 12 11 3 5 2 20 36 35 13 4 38 9 45
13 27 4 1 15 26 8 30 18 7 3 9 2 22 29 6 17 70
27 4 1 35 15 33 25 39 14 8 16 18 3 7 2 11 6 43
12 2 20 9 16 8 13 17 6 4 1 51 19 7 32 3 15 72
36 10 1 4 16 7 17 25 8 26 3 6 13 39 2 12 18 64
7 6 3 14 8 12 27 19 2 24 18 10 1 4 36 35 32 49
28 7 17 3 18 19 13 1 9 2 4 43 36 5 26 8 22 46
1 22 20 7 9 10 5 29 3 8 17 13 48 4 2 12 21 76
31 27 8 15 3 14 16 12 9 1 19 5 39 36 7 4 2 59
2 4 27 9 5 3 12 1 22 32 19 7 11 28 25 24 10 66
14 20 1 30 37 23 15 10 16 2 4 7 33 9 3 5 19 59
35 22 6 13 21 18 9 11 5 26 23 1 29 3 4 8 2 71
43 1 17 9 31 6 2 12 16 5 47 3 4 15 10 13 11 62
37 3 4 10 1 5 22 24 12 13 8 26 9 30 2 29 19 53
1 4 2 16 12 13 8 24 38 44 15 27 10 9 17 3 11 53
14 34 16 10 15 12 1 4 3 36 23 6 18 22 9 2 19 63
6 13 14 8 9 11 1 3 34 2 45 7 18 5 48 16 10 57
7 10 20 5 13 11 3 1 8 31 44 2 19 26 34 16 6 51
38 14 21 1 3 8 45 9 18 10 6 7 17 2 29 15 5 59
1 3 11 20 7 33 10 9 17 22 6 2 16 5 32 12 13 88
2 17 14 8 1 3 25 7 20 30 46 15 38 10 6 5 13 47
9 20 3 1 6 8 26 11 5 12 31 22 13 36 25 2 19 58
13 8 31 17 1 9 2 3 23 7 43 4 20 16 6 19 34 51
10 17 1 7 15 24 20 9 2 3 38 13 6 26 4 12 21 79
2 3 12 6 7 19 8 14 36 1 9 29 4 20 11 45 16 65
21 35 14 23 10 1 6 36 9 16 13 26 2 3 15 4 8 65
10 27 19 24 12 13 32 8 1 6 11 3 2 28 34 35 4 38
1 37 11 24 26 16 29 23 18 33 6 8 13 4 3 2 10 43
12 6 20 2 1 8 5 19 34 10 7 39 4 21 27 30 15 47
6 8 1 2 27 7 13 5 21 22 19 12 4 24 32 10 23 71
7 8 11 16 13 32 12 5 33 1 2 18 4 6 37 9 14 79
1 2 41 12 5 6 8 7 9 4 29 36 18 22 10 27 25 45
38 25 12 16 4 15 24 2 1 6 49 11 10 8 5 17 14 50
10 9 16 5 1 2 42 13 4 11 23 14 12 20 7 29 18 71

wayne

mathe能打破纪录吗，

mathe

其实这个代码非常容易并行。给个计算机集群应该很容易冲记录

wayne

计算机集群就算了。我的意思其实是 能不能仅仅利用PC的多核打破纪录，一般的PC都有4-8核。22#的代码还只是单进程的跑，代码里的数据结构不便于任务分解，感觉代码改动会很大

mathe

k=p^n        p        n        q=k^2+k+1        phi(q)/(6n)
3        3        1        13        2
4        2        2        21        1
5        5        1        31        5
7        7        1        57        6
8        2        3        73        4
9        3        2        91        6
11        11        1        133        18
13        13        1        183        20
16        2        4        273        6
17        17        1        307        51
19        19        1        831        42
23        23        1        553        78
25        5        2        651        30
27        3        3        757        42
29        29        1        871        132
31        31        1        993        110
32        2        5        1057        30
https://www.cambridge.org/core/s ... w/S2040618500034985
也就是说到现在为止找到的解都是符合文章模式的解

白新岭

是不是如果手串上的珠子数减1后不能表示成素数或素数的次幂形式的都无解：例如7-1=6=2*3，是合数，所以无解（这合数不包括单素数次幂的形式）；11-1=2*5无解；13-1=2*6无解；以后的15，16，19，21，22，23，25，27，29，31，34，35，36，37，39，......,素数和它的次幂在自然数集的占比是很少的，所以这有解的珠子数也很少。

mathe

大概阅读了文章，主要思路如下
如果我们要找K棵珠子的手串，其中$K=p^e+1$,其中$p$是素数，记$r=p^e,q=r^2+r+1$, 我们计算的和将要覆盖1,2,...,q。
我们先选择r阶有限域$F_r$,比如取r=3,那么就是模3运算。另外我们需要选择$F_{r^3}$中一个生成元g
比如说我们选择$g$使得$g^3=g-1$,于是$F_{3r}$中任意一个元素可以写成$a+bg+cg^2$形式，其中a,b,c都是$F_r$中元素（也就是0,1,2)
经计算可以得知这样选择的g的阶是$3^3-1=26$,所以验证了g是生成元，也就是$F_{r^3}$中任意一个非零元还可以写成$g^h$的形式，其中$0<=h<=r^3-2=25$
由于，对于任意h满足$0<=h<=r^3-2$,存在唯一的$a_h,b_h,c_h$使得$g^h=a_h+b_hg+c_hg^2$，我们记$h=H(a_h,b_h,c_h)$或$h=H(a_h+b_hg+c_hg^2)$
现在我们把$F_{r^3}$中任意一个非零元素$a+bg+cg^2$看成$F_r$中射影平面上一个点$(a,b,c)$,那么需要注意如果有两个点u,v使得$H(u)-H(v)$是q的倍数，
那么它们表示的是射影平面上的同一个点，或者说存在$k\in F_r*$使得u的每个分量都是v对应分量的k倍.
于是文章证明对于此射影平面任意直线上的点列$P_0,P_1,...,P_r$(每条直线上正好r+1个点), 那么$H(P_0),H(P_1),...,H(P_r)$两两差关于q的余数各不相同。
比如我们选择直线$z=0$,所以上面的点分别为$(1,0,0), (0,1,0), (1,1,0),(1,2,0)$
对应$F_{r^3}$中的数$1,g,1+g,1+2g$,对应$g^0,g^1,g^9,g^3$,所以我们选中了数$0,1,3,9$，选中的数中必然有两个数相差1，通过平移将它们变为0和1，这里这一步可以省略
所以两两差模$q=13$分别为$1,3,9, 12, 2, 8, 10, 11, 6, 4, 5, 7$互不相同，验证了我们的结论。对应4棵珠子为$1-0=1,3-1=2,9-3=6,13-9=4$
选择不同的直线结果会相同。为了获取不同的结果，我们需要选择不同的生成元g，对应的，相当于找到$H(P_0),H(P_1),...,H(P_r)$，我们将每个$H(.)$在乘上一个和q互素的数字在模q就可以得到在不同坐标系下的$H(.)$
比如，我们可以将$g^0,g^1,g^9,g^3$全部指数乘以2得到$g^0,g^2,g^5,g^6$,然后平移为$g^8, g^10, g^0,g^1$,对应四颗珠子为$1-0=1,8-1=7,10-1=2,13-10=3$
通过这种方法，我们可以在$O(r^6)$的时间内构造出所有的解，但是这种方法不能证明不存在其它解

mathe

有限射影平面: https://arxiv.org/ftp/math/papers/0611/0611492.pdf
里面说明了如果$n-=1 (mod 4)$或者$n -=2(mod 4)$而且n包含4k+3形式的素因子的奇数次方，那么不存在长度为n+1的手串