#!/usr/bin/env python3 """Finite exact checks for the grid identities in proof.txt. Run with Python 3.""" import json from fractions import Fraction from math import gcd, lcm, prod def totients(limit): values = list(range(limit + 1)) for prime in range(2, limit + 1): if values[prime] == prime: for n in range(prime, limit + 1, prime): values[n] -= values[n] // prime return values def physical_fractions(grids, accepts): return { Fraction(j, q) for q in grids for j in range(1, q) if accepts(j) } def prime_divisors(n): factor = 2 while factor * factor <= n: if n % factor == 0: yield factor while n % factor == 0: n //= factor factor += 1 if n > 1: yield n def small_prime_means(): checks = 0 for primes in [(2,), (2, 3), (2, 3, 5), (2, 3, 5, 7)]: modulus = prod(primes) # All possible patterns of p | D occur among these divisors. for period in range(1, modulus + 1): if modulus % period: continue unweighted = Fraction(0) weighted = Fraction(0) for m in range(1, modulus + 1): h = prod(Fraction(p, p - 1) for p in primes if m % p == 0 and period % p) v = prod(Fraction(p - 1, p) for p in primes if m % p == period % p == 0) unweighted += h weighted += h * v simple = prod(1 + Fraction(1, p * (p - 1)) for p in primes if period % p) weighted_simple = simple * prod(1 - Fraction(1, p*p) for p in primes if period % p == 0) assert unweighted / modulus == simple assert weighted / modulus == weighted_simple checks += 2 return checks def main(): cutoffs = (2, 4, 8, 12, 16, 24, 32, 40) periods = (1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 24, 30, 32, 60, 210) # phi(q)^2/q >= 1/2 by the prime-power factors, including q=1. # This bounds every possible denominator or grid occurring below. limit = 2 * max(cutoffs)**2 phi = totients(limit) fractions_for_den = { b: {Fraction(a, b) for a in range(1, b) if gcd(a, b) == 1} for b in range(1, limit + 1) if phi[b] <= max(cutoffs) } counts = {"period_cutoffs": 0, "lcm_fibers": 0, "dyadic_cutoffs": 0, "sparse_pairs": 0, "truncated_prime_means": small_prime_means()} for B in cutoffs: admissible = {b for b in fractions_for_den if phi[b] <= B} for D in periods: if phi[D] > B: continue Q = sorted(q for q in admissible if q % D == 0) groups = {q: [] for q in Q} for b in admissible: grid = lcm(b, D) if grid in groups: groups[grid].append(b) general = physical_fractions(Q, lambda j: True) expected = {a for group in groups.values() for b in group for a in fractions_for_den[b]} assert expected == general units = physical_fractions(Q, lambda j: gcd(j, D) == 1) expected_units = {a for q in Q for a in fractions_for_den[q]} assert expected_units == units assert len(units) == sum(phi[q] for q in Q) - int(D == 1) assert len(general) + 1 == sum(phi[b] for group in groups.values() for b in group) for q, group in groups.items(): r = q // D h = prod(Fraction(p, p - 1) for p in prime_divisors(r) if D % p) v = prod(Fraction(p - 1, p) for p in prime_divisors(gcd(r, D))) lam = Fraction(r, h) assert phi[q] == phi[D] * lam assert sum(phi[b] for b in group) == D * lam * v counts["lcm_fibers"] += 1 if D >= 2 and D & (D - 1) == 0: L = D // 2 even = [u for u in admissible if u % 2 == 0 and L * phi[u] <= B] assert Q == sorted(L * u for u in even) assert len(units) == L * sum(phi[u] for u in even) assert len(general) + 1 == L * sum(phi[u] * (1 + int(u % 4 == 2)) for u in even) counts["dyadic_cutoffs"] += 1 if D == 5: for pair in ({1, 4}, {2, 3}): selected = physical_fractions(Q, lambda j: j % 5 in pair) predicted = { a for b in Q for a in fractions_for_den[b] if a.numerator % 5 in pair or b % 2 or 2 * phi[b] <= B } assert selected == predicted assert {1 - t for t in selected} == selected deficit = sum(phi[b] for b in Q if b % 2 == 0 and 2 * phi[b] > B) assert 2 * len(selected) == 2 * sum(phi[q] for q in Q) - deficit counts["sparse_pairs"] += 1 counts["period_cutoffs"] += 1 print(json.dumps({"status": "PASS", "method": "exact fractions and integer sieve", "maximum_cutoff": max(cutoffs), "denominator_limit": limit, **counts}, indent=2, sort_keys=True)) if __name__ == "__main__": main()