数学研发论坛

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

[转载] 手串上穿有六颗珠子,求各珠子上的数字。

[复制链接]
发表于 2019-2-13 11:19:43 | 显示全部楼层
完美差分集 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.


毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-13 11:42:29 | 显示全部楼层
  1. #include<stdio.h>
  2. #include <string.h>

  3. #ifndef N
  4. #define N  5
  5. #endif
  6. #define TS ((N-1)*N+1)
  7. #define WORDC   ((TS+sizeof(int)-1)/sizeof(int))
  8. #define OFFSET(x)  ((x)/32)
  9. #define INDEX(x)   ((x)&31)
  10. #define ISSET(x)   ((ts[OFFSET(x)]&(1<<INDEX(x)))!=0)
  11. #define REVERT(x)  (ts[OFFSET(x)]^=(1<<INDEX(x)))

  12. int db[N][N];
  13. int cc;
  14. int du;
  15. int ts[WORDC];
  16. int sel;

  17. void set_used(int x)
  18. {
  19.     if(!ISSET(x)){
  20.        REVERT(x); REVERT(TS-x);
  21.     }
  22. }

  23. void set_unused(int x)
  24. {
  25.     if(ISSET(x)){
  26.        REVERT(x); REVERT(TS-x);
  27.     }
  28. }

  29. void init()
  30. {
  31.     db[0][0]=1; cc=1; du=1;sel=1;
  32.     set_used(1);
  33. }

  34. int left_test(int row, int rc)
  35. {
  36.     int cur_sum=sel;
  37.     int k;
  38.     for(k=rc-1;k>=0;k--){
  39.         cur_sum+=db[row][k];
  40.         if(cur_sum<TS&&!ISSET(cur_sum)){
  41.             set_used(cur_sum);
  42.             continue;
  43.         }
  44.         for(;k<rc-1;k++){
  45.             cur_sum-=db[row][k];
  46.             set_unused(cur_sum);
  47.         }
  48.         return 0;
  49.     }
  50.     return 1;
  51. }

  52. int right_test(int row, int rc)
  53. {
  54.     int cur_sum=sel;
  55.     int k;
  56.     for(k=0;k<rc;k++){
  57.         cur_sum+=db[row][k];
  58.         if(cur_sum<TS&&!ISSET(cur_sum)){
  59.              set_used(cur_sum);
  60.              continue;
  61.         }
  62.         for(;k>0;k--){
  63.             cur_sum-=db[row][k];
  64.             set_unused(cur_sum);
  65.         }
  66.         return 0;
  67.     }
  68.     return 1;
  69. }

  70. void reverse(int r, int c)
  71. {
  72.     int i;
  73.     for(i=0;i<c/2;i++){
  74.        int tmp=db[r][i];
  75.        db[r][i]=db[r][c-1-i];
  76.        db[r][c-1-i]=tmp;
  77.     }
  78. }

  79. int merge_test(int r1, int c1, int r2, int c2, int d1, int d2)
  80. {
  81.     int i,j;
  82.     int tsb[WORDC];
  83.     if(d1<0)reverse(r1,c1);
  84.     if(d2<0)reverse(r2,c2);
  85.     db[r1][c1]=sel;
  86.     memcpy(tsb,ts,sizeof(tsb));
  87.     for(i=0;i<=c2;i++)db[r1][i+c1+1]=db[r2][i];
  88.     for(i=0;i<=c1;i++){
  89.        int sum=0;
  90.        for(j=i;j<=c1;j++)sum+=db[r1][j];
  91.        if(i<c1){
  92.            if(sum>=TS||ISSET(sum)){
  93.                 goto restore_state;
  94.            }
  95.            set_used(sum);
  96.        }
  97.        for(;j<c1+c2+1;j++){
  98.            sum+=db[r1][j];
  99.            if(sum>=TS||ISSET(sum)){
  100.               goto restore_state;
  101.            }
  102.            set_used(sum);
  103.        }
  104.     }
  105.     for(i=r2;i<cc-1;i++){//move other row forward
  106.         for(j=0;;j++){
  107.             db[i][j]=db[i+1][j];
  108.             if(db[i][j]==0)break;
  109.         }
  110.     }
  111.     cc--;
  112.     du++;
  113.     return 1;
  114. restore_state:
  115.     db[r1][c1]=0;
  116.     if(d1<0)reverse(r1,c1);
  117.     if(d2<0)reverse(r2,c2);
  118.     memcpy(ts,tsb,sizeof(tsb));
  119.     return 0;
  120. }

  121. void merge_revert(int r1, int c1, int r2, int c2, int d1, int d2)
  122. {
  123.     int i,j;
  124.     for(i=cc-1;i>=r2;i--){
  125.         for(j=0;;j++){
  126.             db[i+1][j]=db[i][j];
  127.             if(db[i][j]==0)break;
  128.         }
  129.     }
  130.     cc++;du--;
  131.     for(i=0;i<=c1;i++){
  132.        int sum=0;
  133.        for(j=i;j<=c1;j++)sum+=db[r1][j];
  134.        if(i<c1){
  135.            set_unused(sum);
  136.        }
  137.        for(;j<c1+c2+1;j++){
  138.            sum+=db[r1][j];
  139.            set_unused(sum);
  140.        }
  141.     }
  142.     db[r1][c1]=0;
  143.     for(i=0;i<=c2;i++){
  144.        db[r2][i]=db[r1][c1+1+i];
  145.     }
  146.     if(d1<0)reverse(r1,c1);
  147.     if(d2<0)reverse(r2,c2);
  148. }
  149. void left_unset(int row, int rc)
  150. {
  151.     int cur_sum=sel;
  152.     int k;
  153.     for(k=rc-1;k>=0;k--){
  154.         cur_sum+=db[row][k];
  155.         set_unused(cur_sum);
  156.     }
  157. }

  158. void right_unset(int row, int rc)
  159. {
  160.     int cur_sum=sel;
  161.     int k;
  162.     for(k=0;k<rc;k++){
  163.         cur_sum+=db[row][k];
  164.         set_unused(cur_sum);
  165.     }
  166. }

  167. void go_next_sel()
  168. {
  169.     for(;sel<TS&&ISSET(sel);sel++);
  170. }

  171. int get_row_len(int row)
  172. {
  173.     int j;
  174.     for(j=0;j<N;j++){
  175.        if(db[row][j]==0)return j;
  176.     }
  177.     return j;
  178. }

  179. void output_result()
  180. {
  181.     int sum=TS;
  182.     int k;
  183.     for(k=0;k<N-1;k++){
  184.        printf("%d ",db[0][k]);
  185.        sum-=db[0][k];
  186.     }
  187.     printf("%d\n",sum);
  188. }

  189. void try_next()
  190. {
  191.     int try_sel;
  192.     int i,j;
  193.     go_next_sel();
  194.     try_sel=sel;
  195.     if(sel==TS){
  196.         output_result();
  197.         return;
  198.     }
  199.     set_used(sel);
  200.     if(du+cc<=N-2){
  201.         //try use sel in new row
  202.         db[cc][0]=sel;db[cc][1]=0;cc++;du++;
  203.         try_next();
  204.         sel = try_sel;//restore
  205.         du--;cc--;
  206.     }
  207.     if(du+cc<=N-1){
  208.       for(i=0;i<cc;i++){//try append after the right of one row
  209.         int j=get_row_len(i);
  210.         if(left_test(i,j)==0)continue;
  211.         db[i][j]=sel;db[i][j+1]=0;
  212.         du++;
  213.         try_next();
  214.         sel=try_sel;du--;db[i][j]=0;
  215.         left_unset(i,j);
  216.       }
  217.       for(i=0;i<cc;i++){//try insert before first element
  218.         int j=get_row_len(i);
  219.         if(j<=1)continue;
  220.         if(right_test(i,j)==0)continue;
  221.         int k;
  222.         for(k=j;k>=0;k--)db[i][k+1]=db[i][k];db[i][0]=sel;
  223.         du++;
  224.         try_next();
  225.         sel=try_sel;du--;
  226.         for(k=0;k<=j;k++)db[i][k]=db[i][k+1];
  227.         right_unset(i,j);
  228.       }
  229.     }
  230.     for(i=0;i<cc;i++){
  231.         int ri=get_row_len(i);
  232.         for(j=i+1;j<cc;j++){//try connect two rows
  233.             int rj=get_row_len(j);
  234.             if(merge_test(i,ri,j,rj,1,1)){
  235.                 try_next();
  236.                 sel=try_sel;
  237.                 merge_revert(i,ri,j,rj,1,1);
  238.             }
  239.             if(rj>1){
  240.                 if(merge_test(i,ri,j,rj,1,-1)){
  241.                     try_next();
  242.                     sel=try_sel;
  243.                     merge_revert(i,ri,j,rj,1,-1);
  244.                 }
  245.             }
  246.             if(ri>1){
  247.                 if(merge_test(i,ri,j,rj,-1,1)){
  248.                     try_next();
  249.                     sel=try_sel;
  250.                     merge_revert(i,ri,j,rj,-1,1);
  251.                 }
  252.             }
  253.             if(ri>1&&rj>1){
  254.                 if(merge_test(i,ri,j,rj,-1,-1)){
  255.                     try_next();
  256.                     sel=try_sel;
  257.                     merge_revert(i,ri,j,rj,-1,-1);
  258.                 }
  259.             }
  260.         }
  261.     }
  262.     set_unused(sel);
  263. }

  264. int main()
  265. {
  266.     init();
  267.     try_next();
  268.     return 0;
  269. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-13 15:40:30 | 显示全部楼层
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

点评

l厉害!!!  发表于 2019-2-14 22:03
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-13 16:21:45 | 显示全部楼层
mathe能打破纪录吗,

点评

恩  发表于 2019-2-13 17:50
一周之内应该能打破记录~我们拭目以待吧  发表于 2019-2-13 16:27
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-13 19:01:57 来自手机 | 显示全部楼层
其实这个代码非常容易并行。给个计算机集群应该很容易冲记录
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-14 08:43:54 | 显示全部楼层
计算机集群就算了。我的意思其实是 能不能仅仅利用PC的多核打破纪录,一般的PC都有4-8核。22#的代码还只是单进程的跑,代码里的数据结构不便于任务分解,感觉代码改动会很大
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-14 10:32:49 | 显示全部楼层
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
也就是说到现在为止找到的解都是符合文章模式的解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-14 11:37:39 | 显示全部楼层
是不是如果手串上的珠子数减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,......,素数和它的次幂在自然数集的占比是很少的,所以这有解的珠子数也很少。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-14 11:40:27 | 显示全部楼层
大概阅读了文章,主要思路如下
如果我们要找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)$的时间内构造出所有的解,但是这种方法不能证明不存在其它解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-14 21:51:28 | 显示全部楼层
有限射影平面: https://arxiv.org/ftp/math/papers/0611/0611492.pdf
里面说明了如果$n-=1 (mod 4)$或者$n -=2(mod 4)$而且n包含4k+3形式的素因子的奇数次方,那么不存在长度为n+1的手串
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-7-20 06:47 , Processed in 0.057074 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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