back to table · edit · history · where entries came from · files · download
10236 bytes, as of the version from 2026-10-25 10:19 (current). Recorded here, not run.
"""Independent checks for T482. Run: sage -python checks.py.
For the private draft set NUMBERDB_API_KEY and add --stored. The checks use
explicit rooted-tree objects (no generating-function recurrence), independent
OEIS decimals, exact Catalan/Motzkin/Cayley counts, and the public check.py.
The comparisons check finite and narrow balls before overlap/containment.
"""
import json
import math
import os
import sys
from pathlib import Path
from functools import lru_cache
if os.environ.get('NUMBERDB_KEY_FROM_STDIN') == '1':
os.environ['NUMBERDB_API_KEY'] = sys.stdin.read().strip()
os.environ.pop('NUMBERDB_KEY_FROM_STDIN',None)
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.rational_field import QQ
from sage.rings.real_arb import RealBallField
from generate import compute, coefficients, CLASSES, TreeAmplitudes
from check import exactness, agrees_with, measure, names_its_rings
def decimal(text):
return QQ(int(text.replace('.','')))/10**len(text.split('.')[1])
def source_interval(text):
"""Published final digit allowed one unit in its last place."""
return B(decimal(text), QQ(1)/10**len(text.split('.')[1]))
def encloses(outer,inner):
return outer.lower() < inner.lower() and inner.upper() < outer.upper()
def tight(x, digits=98):
assert x.is_finite() and B(x.rad()) < B(10)**(-digits), x
def compatible(x,y):
tight(x); tight(y)
assert x.overlaps(y), (x,y)
@lru_cache(None)
def size(t):
return 1+sum(size(c) for c in t)
@lru_cache(None)
def identity(t):
return len(set(t)) == len(t) and all(identity(c) for c in t)
@lru_cache(None)
def bounded(t,k):
return len(t)<=k and all(bounded(c,k) for c in t)
@lru_cache(None)
def no_unary(t):
return len(t)!=1 and all(no_unary(c) for c in t)
def rootings(t):
adjacency=[]
def visit(t,parent=None):
v=len(adjacency); adjacency.append([])
if parent is not None:
adjacency[v].append(parent); adjacency[parent].append(v)
for child in t:visit(child,v)
visit(t)
def encode(v,parent):
return tuple(sorted(encode(w,v) for w in adjacency[v] if w!=parent))
return {encode(v,None) for v in range(len(adjacency))}, [len(a) for a in adjacency]
def independent_counts(N=10):
trees={1:[()]}
for n in range(2,N+1):
catalog=sorted(t for m in range(1,n) for t in trees[m])
def branches(remaining,start=0):
if remaining==0:
yield ();return
for i in range(start,len(catalog)):
t=catalog[i]
if size(t)<=remaining:
for rest in branches(remaining-size(t),i):
yield (t,)+rest
trees[n]=list(branches(n-1))
out={}
for n, ts in trees.items():
free={}
for t in ts:
rr,dd=rootings(t);free[min(rr)]=(rr,dd)
values={'rooted':len(ts),'free':len(free),
'identity-rooted':sum(identity(t) for t in ts),
'identity-free':sum(len(rr)==n for rr,dd in free.values()),
'series-reduced-rooted':sum(sum(len(rr) for rr,dd in [v]) for v in free.values() if 2 not in v[1]),
'series-reduced-free':sum(2 not in dd for rr,dd in free.values()),
'degree-bounded-2':sum(bounded(t,2) for t in ts),
'degree-bounded-3':sum(bounded(t,3) for t in ts),
'planted':len(trees.get(n-1,[])),
'series-reduced-planted':sum(no_unary(t) for t in trees.get(n-1,[]))}
for k,v in values.items():out[k,n]=ZZ(v)
return out
def count_arrays(N):
a={k:coefficients(k,N) for k in ('rooted','identity','series','2','3')}
out={k:[ZZ(0)]*(N+1) for k in CLASSES}
for n in range(1,N+1):
for kind,root,free in [('rooted','rooted','free'),('identity','identity-rooted','identity-free')]:
seq=a[kind]
square=sum(seq[i]*seq[n-i] for i in range(1,n))
diagonal=seq[n//2] if n%2==0 else 0
out[root][n]=seq[n]
numerator=2*seq[n]-square+(diagonal if kind=='rooted' else -diagonal)
assert numerator%2==0
out[free][n]=numerator//2
h=a['series']
square=sum(h[i]*h[n-i] for i in range(1,n))
prevsquare=sum(h[i]*h[n-1-i] for i in range(1,n-1))
diagonal=h[n//2] if n%2==0 else 0
prevdiag=h[(n-1)//2] if n%2 else 0
out['series-reduced-rooted'][n]=h[n]+h[n-1]-(prevsquare+prevdiag)//2
out['series-reduced-free'][n]=h[n]+h[n-1]-(square+prevsquare-diagonal+prevdiag)//2
out['planted'][n]=a['rooted'][n-1]
out['series-reduced-planted'][n]=h[n-1]
out['degree-bounded-2'][n]=a['2'][n]
out['degree-bounded-3'][n]=a['3'][n]
out['plane'][n]=ZZ(math.comb(2*(n-1),n-1))//n
m=n-1
out['plane-binary'][n]=sum(ZZ(math.comb(m,2*j))*math.comb(2*j,j)//(j+1) for j in range(m//2+1))
out['labelled-rooted'][n]=ZZ(n)**(n-1)
out['labelled-free'][n]=ZZ(1) if n==1 else ZZ(n)**(n-2)
return out
B=RealBallField(600)
print('Control: explicit enumeration produces 4 rooted and 2 free trees on 4 nodes.',flush=True)
ind=independent_counts()
assert ind['rooted',4]==4 and ind['free',4]==2
counts=count_arrays(800)
assert not agrees_with(ind,lambda key:counts[key[0]][key[1]])
print('Explicit enumeration: all ten unordered/planted classes, n=1..10, agree.',flush=True)
# These digit strings are independent inputs, transcribed from the indicated
# OEIS pages on 2026-10-25. They are not outputs of this generator.
published={
'rooted':'0.439924012571025304040903391434544764798085407940119857653493545022635400420476460537986', # A187770
'free':'0.5349496061423070145503797110520683981431165140569900939770768102375232178806406723978326224185911044466937', # A086308
'identity-rooted':'0.3625364233974198712298411097408713812865256408189512533230825639621448038', # A004111
'series-reduced-planted':'0.1924225474701550354144525345664845514828912790855223729854471406053655209', # A001678
'series-reduced-rooted':'0.4213018528699249210965028', # A001679
'series-reduced-free':'0.684447272004914061023163279794145361469033868145768075109924585532604582794', # A000014
}
values,radii,evidence=compute(100)
print('Certified computation finished.',flush=True)
assert not exactness(values)
assert not names_its_rings(str(Path(__file__).with_name('generate.py')))
for k,text in published.items():
tight(values[k]);assert encloses(source_interval(text), values[k]),k
# Genitrini Table 2 uses sqrt(pi) in the denominator, unlike this table.
# Its final printed digits differ by 1.29e-18 and 8.71e-19 from certified
# values also supported by OEIS. Test only its first 17 fractional digits.
# This is a low-precision independent check, not a bound for our entries.
assert encloses(source_interval('0.64257907974426947'), values['identity-rooted']*B.pi().sqrt())
assert encloses(source_interval('0.77974501018732044'), values['rooted']*B.pi().sqrt())
# The corrigendum's decimals carry numerical rounding errors near their ends;
# compare only the six unambiguous fractional digits, not all nine printed.
assert encloses(source_interval('0.299388'), values['identity-free'])
print('Published amplitude checks: six OEIS decimals, two Genitrini coefficients, corrected identity-free value.',flush=True)
for k in CLASSES:
if k in ('free','identity-free','series-reduced-free','labelled-free'):alpha=QQ(5)/2
else:alpha=QQ(3)/2
if k in ('rooted','free','planted'):rho=radii['rooted']
elif k.startswith('identity'):rho=radii['identity']
elif k.startswith('series'):rho=radii['series']
elif k.startswith('degree'):rho=radii[k[-1]]
elif k=='plane':rho=B(1)/4
elif k=='plane-binary':rho=B(1)/3
else:rho=B(1).exp()**(-1)
errors=[]
for n in (200,400,800):
estimate=B(counts[k][n])*rho**n*B(n)**alpha
if k.startswith('labelled'):estimate/=ZZ(math.factorial(n))
tight(estimate,90)
errors.append(abs(estimate/values[k]-1))
assert errors[2]<errors[1]<errors[0] and errors[2]<QQ(1)/50,(k,errors)
print('count-limit',k,'relative error at n=800',errors[2],flush=True)
vhigh,_,_=compute(130)
for k in CLASSES:compatible(values[k],vhigh[k])
print('All fourteen agree at 100 and 130 requested digits.',flush=True)
def identities(v):
compatible(v['free'],2*B.pi()*v['rooted']**3)
compatible(v['identity-free'],2*B.pi()*v['identity-rooted']**3)
compatible(v['planted'],radii['rooted']*v['rooted'])
compatible(v['series-reduced-planted'],radii['series']*v['series-reduced-rooted'])
compatible(v['series-reduced-free'],(1+radii['series'])*2*B.pi()*v['series-reduced-rooted']**3)
compatible(16*B.pi()*v['plane']**2,B(1))
compatible(4*B.pi()*v['plane-binary']**2,B(3))
compatible(2*B.pi()*v['labelled-rooted']**2,B(1))
compatible(v['labelled-rooted'],v['labelled-free'])
identities(values)
print('All amplitude identities passed.',flush=True)
print('Evidence',json.dumps(evidence),flush=True)
print('Size',measure(values),flush=True)
if '--stored' in sys.argv or os.environ.get('CHECK_STORED')=='1':
report=TreeAmplitudes().verify(sample=None);print(report);assert report.ok
doc=numberdb.table('T482')
def walk(node,keys=()):
if isinstance(node,dict) and 'number' in node:
yield keys,node
elif isinstance(node,dict):
for k,v in node.items():yield from walk(v,keys+(str(k),))
elif isinstance(node,list):
for e in node:
yield (e['params']['class'],e['params']['size'],e['params']['labelling']),e
stored={}
for keys,e in walk(doc['Numbers']):
assert len(keys)==3 and keys[1]=='nodes',keys
raw=e['number'];assert isinstance(raw,str)
# Decimal form: one unit in the last written decimal place.
stored[keys[0]]=source_interval(raw)
compatible(stored[keys[0]],vhigh[keys[0]])
assert set(stored)==set(CLASSES)
identities(stored)
for k,text in published.items():assert source_interval(text).overlaps(stored[k])
print('Stored values: all fourteen verified, independent decimal checks and all nine identities passed.')