#!/usr/bin/env python3 """gjacob.py -- programme 0019: the one-class (Jacobi) covering problem. THE OBJECT. For n >= 1 let P_n = p_1...p_n be the n-th primorial and g(P_n) the Jacobsthal function: the maximal gap between consecutive integers coprime to P_n. OEIS: g(P_n) = A048670(n), and A058989(n) = A048670(n) - 1 is the maximal run of consecutive integers each divisible by a prime <= p_n. LEMMA 1 (covering form, proved in ../DERIVATION.md). Write a "configuration" as one residue c_p per prime p <= p_n. Then A058989(n) = max{ R : there exist c_p with [0,R-1] subset of U_p {c_p mod p} } A048670(n) = A058989(n) + 1 . This is the ONE-CLASS sub-case of 0017's two-class twin problem: no prescribed difference. By Lemma 2, any one-class covering is also a two-class covering (take a_p = c_p), so G_2(x#) >= g(x#): the one-class exponent is a LOWER BOUND ON THE DIFFICULTY of the twin covering lane. A method that cannot beat the "2 kappa" barrier here cannot beat it for twins. USAGE gjacob.py brute [nmax] validate Lemma 1 against A048670 gjacob.py exponent [nmax] beta_eff-style exponent table over the 64 terms gjacob.py capacity n Rmax the counting certificate (Lemma 3) and its vacuity gjacob.py covering n R [tries] find/verify a one-class covering (certified lower bound) """ import math import sys # OEIS A048670 (b-file, accessed 2026-09-21): g(p_n#) for n = 1..64. # a(8)-a(16) Alekseyev 2009; a(25)-a(49) Hagedorn; a(50)-a(57) Ziller/Gerbicz; # a(58)-a(64) Bozek 2021. A048670 = {1: 2, 2: 4, 3: 6, 4: 10, 5: 14, 6: 22, 7: 26, 8: 34, 9: 40, 10: 46, 11: 58, 12: 66, 13: 74, 14: 90, 15: 100, 16: 106, 17: 118, 18: 132, 19: 152, 20: 174, 21: 190, 22: 200, 23: 216, 24: 234, 25: 258, 26: 264, 27: 282, 28: 300, 29: 312, 30: 330, 31: 354, 32: 378, 33: 388, 34: 414, 35: 432, 36: 450, 37: 476, 38: 492, 39: 510, 40: 538, 41: 550, 42: 574, 43: 600, 44: 616, 45: 642, 46: 660, 47: 686, 48: 718, 49: 742, 50: 762, 51: 798, 52: 810, 53: 834, 54: 858, 55: 876, 56: 908, 57: 926, 58: 954, 59: 978, 60: 1002, 61: 1030, 62: 1058, 63: 1098, 64: 1110} def primes_first(n): out, x = [], 2 while len(out) < n: if all(x % d for d in range(2, int(x ** 0.5) + 1)): out.append(x) x += 1 return out def primorial(n): P = 1 for p in primes_first(n): P *= p return P # ---------------------------------------------------------------- Lemma 1 def brute(n): """exact g(p_n#) by scanning the full period (no covering search)""" P = primes_first(n) M = 1 for p in P: M *= p cop = bytearray([1]) * (M + 1) cop[0] = 0 for p in P: cop[p::p] = bytearray(len(cop[p::p])) # consecutive coprime residues, cyclically idx = [i for i in range(M) if cop[i]] best = 0 for a, b in zip(idx, idx[1:]): best = max(best, b - a) if idx: best = max(best, M - idx[-1] + idx[0]) return best def covering_ok(P, c, R): for j in range(R): if not any(j % p == c[i] for i, p in enumerate(P)): return False return True # ---------------------------------------------------------------- Lemma 3 def capacity(n, Rmax): """cap(R) = sum over primes of the largest number of positions of [0,R-1] one class can cover. cap(R) < R would refute R outright.""" P = primes_first(n) out = [] for R in range(2, Rmax + 1): cap = sum(((R - 1) // p + 1) for p in P) out.append((R, cap)) return out # ---------------------------------------------------------------- exponents def exponent(nmax=64): rows = [] for n in range(1, nmax + 1): p = primes_first(n)[-1] g = A048670[n] run = g - 1 gam = math.log(g) / math.log(p) if p > 1 and g > 1 else float("nan") rows.append((n, p, g, run, gam)) return rows def main(): if len(sys.argv) < 2: print(__doc__) return 2 mode = sys.argv[1] if mode == "brute": nmax = int(sys.argv[2]) if len(sys.argv) > 2 else 7 print("Lemma 1 validated against OEIS A048670 by full-period scan") print(" %-4s %-6s %-12s %-10s %-10s %s" % ("n", "p_n", "period", "g (brute)", "A048670", "match")) for n in range(2, nmax + 1): g = brute(n) print(" %-4d %-6d %-12d %-10d %-10d %s" % (n, primes_first(n)[-1], primorial(n), g, A048670[n], "YES" if g == A048670[n] else "NO")) print() print(" The brute force scans every residue mod p_n# and takes the largest") print(" cyclic gap between coprimes: it does not search coverings, so it") print(" validates the reformulation independently of any search code.") return 0 if mode == "exponent": nmax = int(sys.argv[2]) if len(sys.argv) > 2 else 64 rows = exponent(nmax) print("THE ONE-CLASS EXPONENT over the exact 64-term ladder A048670") print(" gamma(n) = log g(p_n#) / log p_n (the local exponent in x)") print(" shape predictions: x^2 (Iwaniec) ; x log^2 x (conjecture) ;") print(" x log x log_3 x / log_2 x (FGKMT lower bound)") print() print(" %-4s %-6s %-7s %-8s %-9s %-9s %-9s %s" % ("n", "p_n", "g", "run", "gamma", "g/(p logp)", "g/(p log2p)", "gamma_shape")) for (n, p, g, run, gam) in rows: if n < 10 or n % 5 == 0 or n == 64: l1 = math.log(p) l2 = math.log(l1) if l1 > 1 else 0.0 l3 = math.log(l2) if l2 > 0 else 0.0 shape = 1 + 2 * l2 / l1 # from the conjectured x log^2 x print(" %-4d %-6d %-7d %-8d %-9.4f %-9.3f %-9.3f %.4f" % (n, p, g, run, gam, g / (p * l1), g / (p * l1 * l1), shape)) print() gs = [(1 + 2 * math.log(math.log(primes_first(n)[-1])) / math.log(primes_first(n)[-1])) for n in (13, 64)] last = rows[-1] print(" gamma at n=13 (p=41) : %.4f" % rows[12][4]) print(" gamma at n=64 (p=311) : %.4f" % last[4]) print(" Iwaniec's theorem allows exponent 2 exactly (g << (omega log omega)^2),") print(" and for n = x# that is x^2 (1+o(1)): at p=311, x^2 = %d vs g = %d, a factor %.1f." % (last[1] ** 2, last[2], last[1] ** 2 / last[2])) lo = last[1] * math.log(last[1]) * math.log(math.log(math.log(last[1]))) / math.log(math.log(last[1])) print(" FGKMT's lower bound gives about %.0f at p=311: g exceeds it by a factor %.2f." % (lo, last[2] / lo)) print(" So at the largest computed level the theorem is ~%.0fx the truth and the" % (last[1] ** 2 / last[2])) print(" construction is within a factor ~%.1f: THAT interval is the open problem." % (last[2] / lo)) print() print(" Required saving for the target: g = o(x^2) needs a factor psi(x) -> infinity.") print(" Iwaniec : (omega log omega)^2 -> x^2 (1+o(1)) NOT o(x^2)") print(" single-log saving : omega^2 log omega -> x^2 / log x = o(x^2)") print(" Jacobsthal conj. : omega^2 -> x^2 / log^2 x = o(x^2)") return 0 if mode == "capacity": n = int(sys.argv[2]); Rmax = int(sys.argv[3]) rows = capacity(n, Rmax) fire = [r for r in rows if r[1] < r[0]] print("Counting certificate (Lemma 3) at n=%d, R <= %d" % (n, Rmax)) print(" %-8s %-10s %s" % ("R", "cap(R)", "cap(R)-R")) for R, cap in rows[:5] + rows[-5:]: print(" %-8d %-10d %+d" % (R, cap, cap - R)) print() print(" R in [2,%d] refutable by counting alone: %d" % (Rmax, len(fire))) print(" => the counting certificate is VACUOUS; only search (and a real method)") print(" can bound the run from above.") return 0 if mode == "covering": n = int(sys.argv[2]); R = int(sys.argv[3]) tries = int(sys.argv[4]) if len(sys.argv) > 4 else 20000 P = primes_first(n) import random rng = random.Random(20260921) best, bestc = 0, None for _ in range(tries): c = [rng.randrange(p) for p in P] j = 0 while j < R and any(j % p == c[i] for i, p in enumerate(P)): j += 1 if j > best: best, bestc = j, list(c) ok = covering_ok(P, bestc, best) print("one-class covering, n=%d (primes 2..%d), target R=%d, %d random tries" % (n, P[-1], R, tries)) print(" best prefix found: %d (verified: %s)" % (best, ok)) print(" => A058989(%d) >= %d and A048670(%d) >= %d" % (n, best, n, best + 1)) print(" published value A048670(%d) = %d" % (n, A048670.get(n, -1))) print(" residues:", bestc) return 0 print("unknown mode", mode) return 2 if __name__ == "__main__": sys.exit(main())