"""Final verification: push each finalist as far as is cheap, and record ranges."""
from math import isqrt
import json

def det_bareiss(M):
    M = [r[:] for r in M]
    n = len(M)
    if n == 0:
        return 1
    sign, prev = 1, 1
    for k in range(n - 1):
        if M[k][k] == 0:
            piv = next((r for r in range(k + 1, n) if M[r][k] != 0), None)
            if piv is None:
                return 0
            M[k], M[piv] = M[piv], M[k]
            sign = -sign
        for i in range(k + 1, n):
            Mik, Mkk = M[i][k], M[k][k]
            for j in range(k + 1, n):
                M[i][j] = (M[i][j] * Mkk - Mik * M[k][j]) // prev
        prev = M[k][k]
    return sign * M[n - 1][n - 1]


res = {}

# 1. det [ i AND j == 0 ]
N1 = 130
d = [det_bareiss([[1 if (i & j) == 0 else 0 for j in range(1, n + 1)]
                  for i in range(1, n + 1)]) for n in range(1, N1 + 1)]
res["and_zero"] = {"N": N1, "values": sorted(set(d)), "max_abs": max(abs(x) for x in d),
                   "nonzero": sum(1 for x in d if x)}
print("and_zero:", res["and_zero"])

# 2. det [ i+j is a base-10 palindrome ]
def is_pal(m):
    s = str(m)
    return s == s[::-1]


N2 = 130
pal = {m for m in range(1, 3 * N2) if is_pal(m)}
d = [det_bareiss([[1 if (i + j) in pal else 0 for j in range(1, n + 1)]
                  for i in range(1, n + 1)]) for n in range(1, N2 + 1)]
res["pal_sum"] = {"N": N2, "values": sorted(set(d)), "max_abs": max(abs(x) for x in d),
                  "nonzero": sum(1 for x in d if x)}
print("pal_sum:", res["pal_sum"])

# 3. Hankel determinants: Rudin-Shapiro and Baum-Sweet, further
L = 400


def rs(n):
    return (-1) ** sum(1 for k in range(24) if (n >> k) & 3 == 3)


def bs(n):
    if n == 0:
        return 1
    run = 0
    for ch in bin(n)[2:]:
        if ch == "0":
            run += 1
        else:
            if run % 2 == 1:
                return 0
            run = 0
    return 0 if run % 2 == 1 else 1


for nm, f in (("rudin_shapiro", rs), ("baum_sweet", bs)):
    a = [f(n) for n in range(L)]
    zeros = [n for n in range(1, 111)
             if det_bareiss([[a[i + j] for j in range(n)] for i in range(n)]) == 0]
    res[f"hankel_{nm}"] = {"N": 110, "zeros": zeros}
    print(f"hankel_{nm}:", res[f"hankel_{nm}"])

# 4. permutations with i+sigma(i) in S
def perfect(n, pred):
    adj = {i: [j for j in range(1, n + 1) if pred(i + j)] for i in range(1, n + 1)}
    mr = [-1] * (n + 1)
    def aug(u, seen):
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                if mr[v] == -1 or aug(mr[v], seen):
                    mr[v] = u
                    return True
        return False
    return all(aug(u, [False] * (n + 1)) for u in range(1, n + 1))


sq = lambda m: isqrt(m) ** 2 == m
tri = lambda m: isqrt(8 * m + 1) ** 2 == 8 * m + 1
for nm, pred in (("square", sq), ("triangular", tri)):
    bad = [n for n in range(1, 261) if not perfect(n, pred)]
    res[f"perm_{nm}"] = {"N": 260, "fails": bad}
    print(f"perm_{nm}:", res[f"perm_{nm}"])

json.dump(res, open("/private/tmp/claude-501/-Users-philipweiss-novel/df47b768-6632-45b7-87c6-030f4d5fa425/scratchpad/verify.json", "w"), indent=1)
print("WROTE")