完美差分集 Perfect Difference Sethttp://mathworld.wolfram.com/PerfectDifferenceSet.html
A set of residues http://mathworld.wolfram.com/images/equations/PerfectDifferenceSet/Inline1.gif (mod http://mathworld.wolfram.com/images/equations/PerfectDifferenceSet/Inline2.gif) such that every nonzero residue can be uniquely expressed in the form http://mathworld.wolfram.com/images/equations/PerfectDifferenceSet/Inline3.gif. Examples include http://mathworld.wolfram.com/images/equations/PerfectDifferenceSet/Inline4.gif (mod 7) and http://mathworld.wolfram.com/images/equations/PerfectDifferenceSet/Inline5.gif (mod 13). A necessary condition for a difference set to exist is that http://mathworld.wolfram.com/images/equations/PerfectDifferenceSet/Inline6.gifbe of the form http://mathworld.wolfram.com/images/equations/PerfectDifferenceSet/Inline7.gif. A sufficient condition is that http://mathworld.wolfram.com/images/equations/PerfectDifferenceSet/Inline8.gif be a prime power. Perfect sets can be used in the construction of perfect rulers.
#include<stdio.h>
#include <string.h>
#ifndef N
#define N5
#endif
#define TS ((N-1)*N+1)
#define WORDC ((TS+sizeof(int)-1)/sizeof(int))
#define OFFSET(x)((x)/32)
#define INDEX(x) ((x)&31)
#define ISSET(x) ((ts&(1<<INDEX(x)))!=0)
#define REVERT(x)(ts^=(1<<INDEX(x)))
int db;
int cc;
int du;
int ts;
int sel;
void set_used(int x)
{
if(!ISSET(x)){
REVERT(x); REVERT(TS-x);
}
}
void set_unused(int x)
{
if(ISSET(x)){
REVERT(x); REVERT(TS-x);
}
}
void init()
{
db=1; cc=1; du=1;sel=1;
set_used(1);
}
int left_test(int row, int rc)
{
int cur_sum=sel;
int k;
for(k=rc-1;k>=0;k--){
cur_sum+=db;
if(cur_sum<TS&&!ISSET(cur_sum)){
set_used(cur_sum);
continue;
}
for(;k<rc-1;k++){
cur_sum-=db;
set_unused(cur_sum);
}
return 0;
}
return 1;
}
int right_test(int row, int rc)
{
int cur_sum=sel;
int k;
for(k=0;k<rc;k++){
cur_sum+=db;
if(cur_sum<TS&&!ISSET(cur_sum)){
set_used(cur_sum);
continue;
}
for(;k>0;k--){
cur_sum-=db;
set_unused(cur_sum);
}
return 0;
}
return 1;
}
void reverse(int r, int c)
{
int i;
for(i=0;i<c/2;i++){
int tmp=db;
db=db;
db=tmp;
}
}
int merge_test(int r1, int c1, int r2, int c2, int d1, int d2)
{
int i,j;
int tsb;
if(d1<0)reverse(r1,c1);
if(d2<0)reverse(r2,c2);
db=sel;
memcpy(tsb,ts,sizeof(tsb));
for(i=0;i<=c2;i++)db=db;
for(i=0;i<=c1;i++){
int sum=0;
for(j=i;j<=c1;j++)sum+=db;
if(i<c1){
if(sum>=TS||ISSET(sum)){
goto restore_state;
}
set_used(sum);
}
for(;j<c1+c2+1;j++){
sum+=db;
if(sum>=TS||ISSET(sum)){
goto restore_state;
}
set_used(sum);
}
}
for(i=r2;i<cc-1;i++){//move other row forward
for(j=0;;j++){
db=db;
if(db==0)break;
}
}
cc--;
du++;
return 1;
restore_state:
db=0;
if(d1<0)reverse(r1,c1);
if(d2<0)reverse(r2,c2);
memcpy(ts,tsb,sizeof(tsb));
return 0;
}
void merge_revert(int r1, int c1, int r2, int c2, int d1, int d2)
{
int i,j;
for(i=cc-1;i>=r2;i--){
for(j=0;;j++){
db=db;
if(db==0)break;
}
}
cc++;du--;
for(i=0;i<=c1;i++){
int sum=0;
for(j=i;j<=c1;j++)sum+=db;
if(i<c1){
set_unused(sum);
}
for(;j<c1+c2+1;j++){
sum+=db;
set_unused(sum);
}
}
db=0;
for(i=0;i<=c2;i++){
db=db;
}
if(d1<0)reverse(r1,c1);
if(d2<0)reverse(r2,c2);
}
void left_unset(int row, int rc)
{
int cur_sum=sel;
int k;
for(k=rc-1;k>=0;k--){
cur_sum+=db;
set_unused(cur_sum);
}
}
void right_unset(int row, int rc)
{
int cur_sum=sel;
int k;
for(k=0;k<rc;k++){
cur_sum+=db;
set_unused(cur_sum);
}
}
void go_next_sel()
{
for(;sel<TS&&ISSET(sel);sel++);
}
int get_row_len(int row)
{
int j;
for(j=0;j<N;j++){
if(db==0)return j;
}
return j;
}
void output_result()
{
int sum=TS;
int k;
for(k=0;k<N-1;k++){
printf("%d ",db);
sum-=db;
}
printf("%d\n",sum);
}
void try_next()
{
int try_sel;
int i,j;
go_next_sel();
try_sel=sel;
if(sel==TS){
output_result();
return;
}
set_used(sel);
if(du+cc<=N-2){
//try use sel in new row
db=sel;db=0;cc++;du++;
try_next();
sel = try_sel;//restore
du--;cc--;
}
if(du+cc<=N-1){
for(i=0;i<cc;i++){//try append after the right of one row
int j=get_row_len(i);
if(left_test(i,j)==0)continue;
db=sel;db=0;
du++;
try_next();
sel=try_sel;du--;db=0;
left_unset(i,j);
}
for(i=0;i<cc;i++){//try insert before first element
int j=get_row_len(i);
if(j<=1)continue;
if(right_test(i,j)==0)continue;
int k;
for(k=j;k>=0;k--)db=db;db=sel;
du++;
try_next();
sel=try_sel;du--;
for(k=0;k<=j;k++)db=db;
right_unset(i,j);
}
}
for(i=0;i<cc;i++){
int ri=get_row_len(i);
for(j=i+1;j<cc;j++){//try connect two rows
int rj=get_row_len(j);
if(merge_test(i,ri,j,rj,1,1)){
try_next();
sel=try_sel;
merge_revert(i,ri,j,rj,1,1);
}
if(rj>1){
if(merge_test(i,ri,j,rj,1,-1)){
try_next();
sel=try_sel;
merge_revert(i,ri,j,rj,1,-1);
}
}
if(ri>1){
if(merge_test(i,ri,j,rj,-1,1)){
try_next();
sel=try_sel;
merge_revert(i,ri,j,rj,-1,1);
}
}
if(ri>1&&rj>1){
if(merge_test(i,ri,j,rj,-1,-1)){
try_next();
sel=try_sel;
merge_revert(i,ri,j,rj,-1,-1);
}
}
}
}
set_unused(sel);
}
int main()
{
init();
try_next();
return 0;
}
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
mathe能打破纪录吗，:lol
其实这个代码非常容易并行。给个计算机集群应该很容易冲记录:)
计算机集群就算了。我的意思其实是 能不能仅仅利用PC的多核打破纪录，一般的PC都有4-8核。22#的代码还只是单进程的跑，代码里的数据结构不便于任务分解，感觉代码改动会很大
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/services/aop-cambridge-core/content/view/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，......,素数和它的次幂在自然数集的占比是很少的，所以这有解的珠子数也很少。
大概阅读了文章，主要思路如下
如果我们要找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)$的时间内构造出所有的解，但是这种方法不能证明不存在其它解
有限射影平面: https://arxiv.org/ftp/math/papers/0611/0611492.pdf
里面说明了如果$n-=1 (mod 4)$或者$n -=2(mod 4)$而且n包含4k+3形式的素因子的奇数次方，那么不存在长度为n+1的手串