#!/usr/bin/env python3 """Exact integer recomputation of the corner-measurement right prime band. Band geometry, read off corner-measurement.js params()/enumerate(): Z = floor(x^v) v = 1/20 E1 = floor(x^(1-v-2*eta0)) eta0 = 1/100 -> exponent 93/100 elo = max(Z, E1) ( = E1 at every j here ) Tmax = floor((x-2)/(elo+1)) right prime band = { primes r' : Z < r' <= Tmax } x = 2^j, so every cutoff is floor(2^(j*p/q)) = integer q-th root of 2^(j*p): exact in Python ints, whereas the script uses Math.floor(Math.pow(2, j*alpha)). Section 5 of corner-measurement.md flags that float step as an unchecked limitation; this checks it. """ import math from fractions import Fraction def iroot(n: int, q: int) -> int: """floor(n ** (1/q)) for ints, exactly. Integer Newton, then a 1-step correction. (A linear walk down from a power-of-two seed is astronomically slow here: for E1 at j=200 the seed and the answer are both about 2^186 but differ by a huge absolute gap.)""" if n < 0: raise ValueError if n == 0: return 0 if q == 1: return n r = 1 << ((n.bit_length() + q - 1) // q) # >= the true root while True: nr = ((q - 1) * r + n // r ** (q - 1)) // q if nr >= r: break r = nr while r ** q > n: r -= 1 while (r + 1) ** q <= n: r += 1 return r def floor_two_pow(j: int, alpha: Fraction) -> int: """floor(2 ** (j*alpha)) exactly.""" num, den = (j * alpha).numerator, (j * alpha).denominator if num < 0: raise ValueError("negative exponent") return iroot(1 << num, den) if den > 1 else 1 << num def float_two_pow(j: int, alpha: Fraction) -> int: """What corner-measurement.js computes: Math.floor(Math.pow(2, j*alpha)).""" return math.floor(math.pow(2.0, j * float(alpha))) def primes_upto(n: int): if n < 2: return [] s = bytearray([1]) * (n + 1); s[0] = s[1] = 0 for p in range(2, math.isqrt(n) + 1): if s[p]: s[p * p::p] = bytearray(len(s[p * p::p])) return [i for i in range(n + 1) if s[i]] V_EXP = Fraction(6, 25) # w Z_EXP = Fraction(1, 20) # v ETA0 = Fraction(1, 100) E1_EXP = 1 - Z_EXP - 2 * ETA0 # 93/100 def band(j: int, exact: bool = True): two_pow = floor_two_pow if exact else float_two_pow x = (1 << j) if exact else 2.0 ** j Z = two_pow(j, Z_EXP) E1 = two_pow(j, E1_EXP) elo = max(Z, E1) Tmax = (x - 2) // (elo + 1) if exact else math.floor((x - 2) / (elo + 1)) return {"Z": Z, "E1": E1, "elo": elo, "Tmax": int(Tmax)} if __name__ == "__main__": PR = primes_upto(10 ** 7) pset = set(PR) print("# Exact band contents. band = primes in (Z, Tmax].") print("# j | Z | Tmax | #primes | the primes") counts = {} for j in list(range(20, 121)): b = band(j) ps = [p for p in PR if b["Z"] < p <= b["Tmax"]] counts[j] = len(ps) show = ",".join(map(str, ps[:8])) + ("..." if len(ps) > 8 else "") if j <= 60 or j % 5 == 0: print(f"{j:4d} | {b['Z']:6d} | {b['Tmax']:11d} | {len(ps):7d} | {show}") print("\n# First j at which the band holds at least k primes:") for k in range(1, 9): hit = [j for j in sorted(counts) if counts[j] >= k] print(f" k={k}: j = {hit[0] if hit else '>120'}" + (f" (holds for all j>= {hit[0]}? " f"{all(counts[t] >= k for t in range(hit[0], 121))})" if hit else "")) print("\n# The two numbers quoted in corner-measurement.md section 6:") for j in (70, 100): b = band(j) ps = [p for p in PR if b["Z"] < p <= b["Tmax"]] # the note's own PNT estimate, reproduced x = 2.0 ** j est = x ** 0.07 / (0.07 * math.log(x)) - x ** 0.05 / (0.05 * math.log(x)) print(f" j={j}: exact band = ({b['Z']}, {b['Tmax']}] -> {len(ps)} primes {ps}") print(f" note's PNT estimate = {est:.2f}") print("\n# Float vs exact cutoffs (section 5's unchecked limitation):") bad = [] for j in range(1, 501): e, f = band(j, exact=True), band(j, exact=False) if (e["Z"], e["E1"]) != (f["Z"], f["E1"]): bad.append((j, e, f)) print(f" j=1..500 checked; disagreements: {len(bad)}") for j, e, f in bad[:10]: print(f" j={j}: exact Z={e['Z']} E1={e['E1']} | float Z={f['Z']} E1={f['E1']}") # (An earlier margin block here computed min-distance-to-an-integer in floats and # overflowed on 2^num for large j. It is removed rather than repaired: section 2 of the # report answers the same question exactly and in closed form -- the float floor moves # only where 100 | j, and there the extra integer is a power of two.)