"""Exact enumeration of periodic grids, gcd supports and restricted density factors.""" from fractions import Fraction as F from functools import cache from itertools import combinations from math import gcd, lcm, prod def phi_sieve(limit): phi = list(range(limit + 1)) for p in range(2, limit + 1): if phi[p] == p: for n in range(p, limit + 1, p): phi[n] -= phi[n] // p return phi @cache def factors(n): result = {} p = 2 while p * p <= n: while n % p == 0: result[p] = result.get(p, 0) + 1 n //= p p += 1 if n > 1: result[n] = 1 return result def mu(n): powers = factors(n).values() return 0 if any(e > 1 for e in powers) else (-1) ** len(powers) def K_over_kappa(n): # Writing p**2 / p**e avoids nonintegral powers in the exact arithmetic. return prod((F(p * p, p**e * (p*p-p+1)) for p, e in factors(n).items()), start=F(1)) def multiplier(g, d): return g * prod((F(p-1, p) for p in factors(g) if d % p), start=F(1)) def divisors(n): return [j for j in range(1, n + 1) if n % j == 0] def density(D, support): out = F(0) for d in divisors(D): c = sum(mu(a) * K_over_kappa(d * a) for a in divisors(D // d)) # Independent Euler product: exact valuation j below ord_p(D), or j >= ord_p(D). local = F(1) for p, e in factors(D).items(): j = factors(d).get(p, 0) W = 1 + F(p, (p-1)**2) if j == e: mass = F(p*p, p**e * (p-1)**2) else: mass = F(1) if j == 0 else F(1, (p-1) * p**(j-1)) local *= mass / W assert c == local and c > 0 costs = [multiplier(g, d) for g in support if d % (D // g) == 0] if costs: out += c / min(costs)**2 return out def main(): periods = range(1, 25) cutoffs = (5, 12, 25, 48, 64) # phi(n)^2 >= n/2 by multiplying the elementary prime-power inequalities. limit = 2 * max(cutoffs)**2 phi = phi_sieve(max(periods) * limit) envelope_count = density_count = grid_visits = 0 for D in periods: classes = divisors(D) all_supports = [S for k in range(1, len(classes)+1) for S in combinations(classes, k)] for S in all_supports: G = density(D, S) assert 0 < G <= K_over_kappa(D) * prod(F(p+1, p) for p in factors(D)) density_count += 1 assert density(D, (1,)) == K_over_kappa(D) assert density(D, classes) == K_over_kappa(D) * prod(F(p+1, p) for p in factors(D)) for B in cutoffs: eligible = [b for b in range(2, 2*B**2 + 1) if phi[b] <= B] qlist = [q for q in range(D, 2*B**2 + 1, D) if phi[q] <= B] actual = {g: set() for g in classes} for q in qlist: for j in range(1, q): r = gcd(j, q) actual[gcd(j, D)].add((j // r, q // r)) grid_visits += 1 by_class = {} for g in classes: den = {b for b in eligible if b % (D // g) == 0 and phi[g * b] <= B} assert actual[g] == {(a, b) for b in den for a in range(1, b) if gcd(a, b) == 1} by_class[g] = den for S in all_supports: union = set().union(*(by_class[g] for g in S)) predicted = set() for b in eligible: d = gcd(b, D) costs = [multiplier(g, d) for g in S if d % (D // g) == 0] if costs and phi[b] * min(costs) <= B: predicted.add(b) assert union == predicted envelope_count += 1 assert by_class[1] == {b for b in eligible if b % D == 0} assert set().union(*by_class.values()) == {b for b in eligible if phi[lcm(b, D)] <= B} print(f"Periods 1..24, cutoffs {cutoffs}. Enumerated {grid_visits} proper grid numerators with multiplicity.") print(f"Passed {envelope_count} support/cutoff comparisons and {density_count} exact density comparisons.") for D, S in [(3,(1,)), (5,(1,)), (8,(1,)), (12,(2,3)), (12,tuple(divisors(12)))]: print(f"D={D}, support={S}: K_D/kappa={K_over_kappa(D)}, G/kappa={density(D,S)}") if __name__ == "__main__": main()