"""Verify the finite degree ranges for a cubic earlier projection in Section 7.""" from functools import cache from math import isqrt def primes_up_to(bound): sieve = bytearray(b"\x01") * (bound + 1) sieve[:2] = b"\x00\x00" for prime in range(2, isqrt(bound) + 1): if sieve[prime]: sieve[prime * prime::prime] = bytes((bound - prime * prime) // prime + 1) return [n for n, is_prime in enumerate(sieve) if is_prime] @cache def divisor_degree(first, last): moments = (first + 2) // 3 - 1 if (1 << moments) <= last or moments < 2: return 0 degree = moments + 1 for prime in primes_up_to(2 * last): threshold = prime ** (moments + 1) power = prime while power <= 2 * last: phi = power - power // prime if threshold <= (2 * last) ** phi: break degree += phi power *= prime return degree def excluded(first, last, length): moments = (first + 2) // 3 - 1 even_moment = 2 * (moments // 2) grid_span = length * last // 3 difference = 2 * divisor_degree(first, last) - grid_span return difference > 0 and difference ** even_moment > last * grid_span ** even_moment if __name__ == "__main__": assert primes_up_to(10) == [2, 3, 5, 7] for length, expected in ((3, 114), (4, 192), (5, 216)): surviving = [n for n in range(4, 600) if not excluded(n, n, length)] assert max(surviving) == expected assert all(excluded(a, a + 99, length) for a in range(600, 6000, 100)) print(f"Later length {length}: degree at most {max(surviving)}")