#!/usr/bin/env python3 """Exact count, by CRT and inclusion-exclusion, of gap constellations in the twin-admissible tile T_x. T_x = { r mod P : r(r+2) coprime to every prime p <= x }, P = prod_{p<=x} p (lagspec.c's tile). N(H; I) = #{ r mod P : r+h in T_x for h in H, r+i not in T_x for i in I } = sum_{S subset I} (-1)^|S| prod_{p<=x} (p - nu_p(H u S)), nu_p(A) = |{-a, -a-2 mod p : a in A}|. Consecutive gaps (g1, ..., gk) = H = partial sums, I = every multiple of 6 strictly inside, not in H (tile points differ by multiples of 6). Subsets whose product vanishes are pruned with all supersets. Usage: ie4256.py x g1 [g2 ...] -> JSON line {x, gaps, count, D}; stdout only, deterministic. """ import json, sys def primes_upto(x): return [p for p in range(2, x + 1) if all(p % d for d in range(2, int(p ** 0.5) + 1))] def count(x, gaps): ps = primes_upto(x) H = [0] for g in gaps: H.append(H[-1] + g) I = [i for i in range(6, H[-1], 6) if i not in H] # forbidden residue sets per prime, as bitmasks over residues mod p def mask(p, a): return (1 << ((-a) % p)) | (1 << ((-a - 2) % p)) base = [0] * len(ps) for k, p in enumerate(ps): for a in H: base[k] |= mask(p, a) imask = [[mask(p, i) for k, p in enumerate(ps)] for i in I] total = 0 def rec(start, masks, sign): nonlocal total prod = 1 for k, p in enumerate(ps): prod *= p - bin(masks[k]).count("1") if prod == 0: return False total += sign * prod for t in range(start, len(I)): nm = [masks[k] | imask[t][k] for k in range(len(ps))] rec(t + 1, nm, -sign) return True rec(0, base, 1) D = 1 for p in ps: D *= p - bin(mask(p, 0)).count("1") return total, D if __name__ == "__main__": x = int(sys.argv[1]); gaps = [int(a) for a in sys.argv[2:]] c, D = count(x, gaps) print(json.dumps({"x": x, "gaps": gaps, "count": c, "D": D}))