""" cgreedy.py -- a policy between greed and freedom over Z: the c-greedy walk, which takes any lambda-raising multiplier m <= c m_0, m_0 the least one, and the dam that holds its support finite at every c. QUESTION. The c-greedy image I_c(s) is the set of limits of every run from s that takes, at each state M, any m >= 2 (over all integers) with lambda(Mm) != lambda(M) and m <= c m_0(M). c = 1 is the greedy walk and I_c grows with c. (i) At which c does I_c(1) gain a limit, below the first dam? (ii) Does some finite c hold a limit of infinite support, or is the dam ratio rho unbounded with no prime-pattern hypothesis? (iii) Does every limit at a finite c have an infinite exponent? BY HAND (frozen before this code). The TIDE m_0(M) is a prime power (the door lemma). At odd l, l's price l^door(l) exceeds l iff l is covered: unseated with (l - 1) | lambda, or seated with v_l(lambda) >= a_l. The tide ceiling tau(P) = max m_0(M) over the M >= 1 whose primes are all <= P; m_0(M) <= P(M) at odd P(M), the top prime having no witness. THE DAM: if c tau(P) < P+, the next prime, every run from a seed with primes <= P keeps them <= P (m_0 <= tau(P), every move <= c tau(P) < P+), so its support is finite and, M growing, some exponent infinite. tau(11) = 7: 7 is covered only by a seated prime = 1 mod 3 other than 7, = 1 mod 7, or 3^2 with a prime = 1 mod 9, all past 11; M = 55 has m_0 = 7. So c < 13/7 dams the void at 11. tau(P) exactly: a tide >= T > 4 within P is reachable iff it is with every prime of [T, P] seated once, 2 unseated, each odd l < T seated once or not (a deeper l only raises its own bar, and adds nothing to lambda: its bar forces v_l(N) >= a_l, so l^(a_l - 1) is in N already); with N the lcm of p - 1 over the seated set and k_l least with l^k >= T, seated l needs v_l(N) >= k_l - 1, unseated l needs (l - 1) | N and v_l(N) >= k_l - 2, 2 needs v_2(N) >= max(1, k_2 - 3). Feasible sets are closed under union, so the greatest one is found by striking every seated l whose bar fails until none does, then reading the struck l's unseated bars. THE TWO-ADIC DAM (by hand, frozen before its code). Every finite c is dammed iff rho(P) = P+/tau(P) is unbounded, and every tide pays 2's price, which is bounded through v_2(lambda). L1. Let M have 2^a || M and an odd prime factor, w the largest v_2(p - 1) over the odd p | M. With v = v_2(lambda(M)) = max(v_2(lambda(2^a)), w) and v_2(lambda(2^j)) = 0, 1, j - 2 at j = 1, 2, >= 3, the multiplier 2^(v + 3 - a) (>= 2, as v >= a - 2) takes 2 to the exponent v + 3, whose lambda has 2-part 2^(v+1), so it raises lambda: 2's price is <= 2^(v + 3 - a). If v = w that is <= 2^(w+3); if v > w >= 1 then a >= 3, v = a - 2, price <= 2. So 2's price is <= 2^(w+3), with equality at odd M (a = 0). A power of 2 alone has price <= 4. T1. tau(P) <= 2^(W(P)+3), W(P) the largest v_2(p - 1) over the odd primes p <= P (P >= 3): a tide is at most 2's price. L2. If 2^(e-1) = 1 mod 2j + 1 then j 2^e + 1 = 2j 2^(e-1) + 1 = 0 mod 2j + 1, and j 2^e + 1 > 2j + 1 at e >= 2. With L_J the lcm of the orders of 2 mod 2j + 1 over j <= J, every e = 1 + t L_J, t >= 1, makes j 2^e + 1 composite at every j <= J. T2. If j 2^e + 1 is composite for 1 <= j <= J, let P be the largest prime <= J 2^e. A prime p <= P with 2^e | p - 1 would be j 2^e + 1 with j < J, so W(P) <= e - 1, tau(P) <= 2^(e+2), and P+ > J 2^e + 1: rho(P) > J/4. If k 2^e + 1 is the least prime = 1 mod 2^e, the same at P the prime before it gives rho(P) > k/4 (at e = 1, k = 1, P = 2, outside T1, but tau(2) = 4 <= 2^(e+2)). T3. By L2, T2 holds at infinitely many e for every J: rho is unbounded, and every c-greedy walk from every seed is dammed. PREDICTIONS. P1: the price at 2 is <= max(4, 2^(w+3)) at every state tested and = 2^(w+3) at every odd M > 1. P2: the 2-bar never binds at P <= 10,000 (the striking rule with it dropped gives the same tau). P3: the least k with k 2^e + 1 prime, e <= 600, has records past 28 (rho > 7, past the table's 6.993) and a maximum between 300 and 3000. DESIGN. Four arms. TAU: tau(P) by the striking rule for every prime P <= 10,000, incremental in P over the prime powers T; its witness, the product of the greatest feasible set and of [tau, P] at the P where tau last rose (a witness at every later P too), has its m_0 read by growth.py's door menu. THE DAMS: the records of rho(P) = P+/tau(P) and, for c = 13/7, 2, 3, 4, 5, 6, the least P with rho(P) > c. THE CENSUS: the c-greedy graph from the void, every admissible m <= c m_0 over all integers, no prime barred, each exponent capped at B_p = floor(log_p 1000) + 3, past which no door and no admissibility reads it (a capped prime's lambda part a - 1, a - 2 at 2, exceeds every v_p(r - 1), r <= 1000). An infinite run ends at a state whose self-loops deepen capped primes only, so the limits are read off it: each self-loop state and nonempty union U of its self-loop labels gives the limit with U at inf, the other capped primes at a finite exponent >= B_p ("B+"), the rest as they stand; a LOCK PATTERN is a limit's support with the primes it sends to inf. Run at every c = m/t in [1, 11/5), t in 2, 3, 4, 5, 7, 8, 9, m <= 13 t: the image changes only where c crosses m/m_0 at a reachable state, so its lock patterns are exact below the dam (its finite exponents past a cap merged in B+). (Frozen below 13/7, the dam at 11; THE DAMS printed tau(7) = 5, a dam at 7 for c < 11/5, and the census was widened to it, every tide a state on 2, 3, 5, 7 holds being among the t.) Then at c = 11/5 itself, under a budget of 200,000 states. THE TWO-ADIC DAM: L1, growth.least_move's scan at 2 against max(4, 2^(w+3)) over the box (P <= 13) and 20,000 random states on the primes < 300 (2 at exponent 0..8, up to 12 odd primes at exponent 1..3), duplicates dropped, the box's values also against the least raising 2^r by growth.lam_int (which shares lam_pp's lambda(2^j), so the control at 17 is the independent one); L2, the orders, L_J, and j 2^e + 1 mod 2j + 1 at e = 1 + L_J for J <= 40, with the size of the P it yields; the TABLE, tau(P) against 2^(W(P)+3) at every prime 3 <= P <= 10,000, a consistency print only, since the rule's 2-bar builds the bound in, beside the striking rule rerun without its 2-bar, the arm that reads it; PROTH, for every e <= 600 the least k with k 2^e + 1 prime, by bridges.proth_prime (Miller-Rabin deterministic below 3 10^24, Proth's theorem above: a proof both ways). CONTROLS (read first): growth.py's m_0 equals brute_least on the box (a_2 <= 6, a_3 <= 4, a_5 <= 3, every other a <= 2 over the primes <= 13); c = 1 reaches 1, 3, 9, 27 in its first four states and one limit, 3^inf; c = 4/3 gives exactly 3^inf, 2^inf and 2^2 5^inf and no 7; c = 7/5 seats 7; 2's price at M = 17 is 2^7, at M = 4 it is 4; at J = 2, e = 5 the forms are 33 and 65. KILL. K1: tau(P) by the rule against the max m_0 over the box at every prime P <= 13; a mismatch kills the rule and all after it. K2: at every census c below 13/7, the largest prime a reachable state seats; above 11 kills the dam (as frozen); widened, a state past 7 below 11/5 kills it too. Beside them, gated: the witness's m_0 against tau(P) at every prime P <= 10,000 (the table attained, not only bounded), and the census at c = 11/5 complete, past 7 and within 37, the next dam (the dam at 7 sharp at its own ratio). K3: a state whose price at 2 exceeds max(4, 2^(w+3)), or an odd M > 1 where it differs from 2^(w+3): L1 and all after it die. K4: a j <= 40 with j 2^e + 1 != 0 mod 2j + 1 at e = 1 + L_J: L2 dies. T1 rests on L1, so on K3; a prime P <= 10,000 with tau(P) > 2^(W(P)+3) was frozen as a third kill and dropped after its first run (7/7), the rule's 2-bar making it unable to fire; the L1 states were deduplicated then. The KILL line reads FIRED iff a check fails. FINDINGS (from the printed run; the controls passed first: 3780 box states with m_0 equal to brute_least, the walk 1, 3, 9, 27, exactly 2^inf, 2^2*5^inf, 3^inf at 4/3, and 7 seated at 7/5). K1 silent: tau(2) = tau(3) = 4, tau(5) = tau(7) = 5, tau(11) = 7, tau(13) = 11, rule and box alike; the witness's m_0 is tau(P) at every prime P <= 10,000. tau/P: 0.636 at 11, 0.465 at 101, 0.225 at 1009, 0.183 at 9973. The dam ratio's records: 2.200 at P = 7 (tau 5, 11/5), 5.706 at 89 (records from P = 37 to 89 at tau 17, 97/17), 6.009 at 641 (tau 107, 643/107), 6.974 at 1579 (tau 227), 6.993 at 5861 (tau 839, 5867/839). Least dam: P = 7 for c = 13/7 and 2, 47 for 3, 67 for 4, 83 for 5, 641 for 6. The four record tides past 7, 17, 107, 227 and 839, have d - 1 = 2^4 or 2 r, r prime, and each is passed first at a P that is 1 mod 16, mod r or mod d: 17 held from P = 23, passed at 97 (= 1 mod 16); 107 from 233 to 643 (= 6*107 + 1); 227 from 643 to 1583 (= 14*113 + 1); 839 from 3373 to 5867 (= 14*419 + 1). 5 is passed at 11, 7 at 13. The census, K2 silent: no state below 11/5 seats a prime past 7. The image changes at c = 1, 4/3, 7/5, 8/5, 5/3, 7/4, 9/5, 2 and holds to 11/5, the lock patterns (support | at inf) arriving: 1 3|3 4/3 2|2; 2,5|5 7/5 2,5,7|5; 2,5,7|5,7; 2,5,7|7 8/5 2,5|2; 2,5,7|2 5/3 3,5|3; 3,5|3,5; 3,5|5; 5|5; 5,7|5; 5,7|5,7; 5,7|7 7/4 2,7|2; 2,7|7 9/5 2,3,5|3; 2,3,5|3,5; 2,3,5|5 2 2,3|2; 2,3|2,3; 2,3|3; 2,3,5|2; 2,3,5|2,3 25 patterns and 321 limit classes at 2 (1415 states). No pattern holds 3 and 7. At c = 11/5 itself (predicted by hand before the print, in no commit: M = 5 is reached at 5/3, m_0(5) = 5 and 11 raises it) the census completes at 72,760 states with top prime 23: the dam at 7 is passed exactly at its ratio, and the next dam (37, rho 2.412) holds. Predictions: 3^inf alone below 4/3, 2^inf and 2^2 5^inf at 4/3, 7 at 7/5 and 5 beside 3^inf at 5/3 held; rho past 2 by P = 200 and past 4 by 10,000 held (P = 7 and 67); "roughly like log P" FAILED as stated, the records stalling at 6.974 (1579) and 6.993 (5861), none from 5861 to 10,000; 11 entering below 13/7 FAILED, the dam sitting at 7. Run: 11.2 s, peak commit 142.6 MB, 12/12; the tide lines and the 11/5 census added after, the same 12/12 in 13.4 s. Carried: the budget runs at c = 2, 3, 4 dropped (no claim read them; the last printed top primes 47 and 59 under dams at 47 and 67), the witness and the 11/5 census made checks: 14/14 in 3.1 s, peak commit 92.4 MB. THE TWO-ADIC DAM (its controls passed first: 2's price 128 at 17 and 4 at 4, 33 and 65 composite). K3 silent, P1 held: the price at 2 is <= max(4, 2^(w+3)) at all 21,629 distinct states (the 3780 of the box and the 20,000 random drawn, duplicates dropped), = 2^(w+3) at all 2466 odd ones, the scan equal to lam_int's least raising 2^r on the box; the bound attained at 2467 of the 21,628 nonempty states. L1 holds, and with it T1. K4 silent: (2j + 1) | j 2^e + 1 at every j <= J <= 40, e = 1 + L_J. L_J = 4, 12, 120, 27720 at J = 2, 4, 8, 16, and 240360120 at J = 29, so T3's construction proves rho > 7.25 only at a P near 10^72355607.6: unconditional and astronomical. TABLE: tau(P) <= 2^(W(P)+3) at all 1228 primes 3 <= P <= 10,000 (built in by the rule), the least ratio 2^(W+3)/tau 1.377 (first at P = 7547); P2 held, the 2-bar alone stops the next tide at 0 primes (W = 2, 4, 8, 8, 8, 9 at P = 7, 89, 641, 1579, 5861, 9973). PROTH, P3 held: every record of the least k, (e, k), with rho > k/4 proved at the prime before k 2^e + 1: (1, 1), (3, 2), (5, 3), (9, 15), (22, 25), (31, 35), (58, 54), (76, 58), (86, 87), (99, 219), (135, 225), (217, 413), (301, 428), (383, 485), (422, 843), (425, 896); so rho > 8.75 at a P near 10^10.9 (the first past the table's 6.993) and rho > 224 near 10^130.9, the maximum at e <= 600; mean k 115.2, and k over e ln2 / 2 averages 1.12 at e >= 100. With the arm: 20/20 in 5.8 s, peak commit 97.5 MB; the least ratio printed to three places with its P, 20/20 in 6.4 s, 96.7 MB. """ import os import random import time from fractions import Fraction from math import gcd, log, log10 os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") import growth # noqa: E402 import bridges # noqa: E402 CHECKS = [] X = 10000 PR = growth.primes_up_to(X + 200) PM1 = {p: growth.factor(p - 1) for p in PR} CAPP = 1000 EMAX = 600 def check(name, ok, detail=""): CHECKS.append((name, bool(ok))) print(f" [{'PASS' if ok else 'FAIL'}] {name}" + (f" -- {detail}" if detail else "")) def next_prime(p): return next(q for q in PR if q > p) def lam(mf): """growth.lam by one pass of maxima, for states of many primes.""" out = {} for p, a in mf.items(): for r, e in growth.lam_pp(p, a).items(): if e > out.get(r, 0): out[r] = e return out def m0(mf): return growth.menu(mf, lam(mf))[1] def raises(mf, lf, m): return lam(growth.merge_add(mf, growth.factor(m))) != lf # ------------------------------------------------------------------- tau def feasible(T, P, bar2=True): """The greatest feasible seated set below T, or None: a tide >= T within the primes <= P (2's bar dropped at bar2=False).""" vhi = {} for p in PR: if p > P: break if p >= T: for r, e in PM1[p].items(): if r < T and e > vhi.get(r, 0): vhi[r] = e low = [l for l in PR if 3 <= l < T] Xs = {l for l in low if l <= P} while True: vN = dict(vhi) for l in Xs: for r, e in PM1[l].items(): if e > vN.get(r, 0): vN[r] = e strike = {l for l in Xs if l ** (vN.get(l, 0) + 1) < T} if not strike: break Xs -= strike for l in low: if l in Xs: continue if not growth.divides(PM1[l], vN): return None if l ** (vN.get(l, 0) + 2) < T: return None e2 = vN.get(2, 0) if bar2 and (e2 < 1 or 2 ** (e2 + 3) < T): return None return Xs def prime_powers(n): out = set() for p in PR: if p > n: break x = p while x <= n: out.add(x) x *= p return sorted(out) def tau_table(): """tau(P) for every prime P <= X, and a witness M as a factor map.""" pps = [t for t in prime_powers(X + 1) if t > 4] tau, i, out = 4, 0, {} best = {2: 2} for P in PR: if P > X: break while i < len(pps): s = feasible(pps[i], P) if s is None: break tau = pps[i] best = {l: 1 for l in s} best.update({p: 1 for p in PR if tau <= p <= P}) i += 1 out[P] = (tau, dict(best) if tau > 4 else {2: 2}) return out def brute_box(P): ps = [p for p in PR if p <= P] caps = {2: 6, 3: 4, 5: 3} states = [{}] for p in ps: states = [({**s, p: a} if a else dict(s)) for s in states for a in range(caps.get(p, 2) + 1)] return states # ---------------------------------------------------------------- census def cap_of(p): return int(log(CAPP) / log(p) + 1e-9) + 3 def capped(mf): return tuple(sorted((p, min(a, cap_of(p))) for p, a in mf.items())) def census(c, budget=None): """The c-greedy graph from the void. Returns (complete, states, limits, largest seated prime, largest tide).""" start = () seen, frontier, loops = {start}, [start], {} top, tide = 1, 3 while frontier: nxt = [] for s in frontier: mf = dict(s) lf = lam(mf) t = growth.menu(mf, lf)[1] tide = max(tide, t) for m in range(2, int(c * t) + 1): if not raises(mf, lf, m): continue f2 = growth.merge_add(mf, growth.factor(m)) assert max(f2) <= CAPP s2 = capped(f2) if s2 == s: loops.setdefault(s, set()).add( frozenset(growth.factor(m))) continue if s2 not in seen: seen.add(s2) nxt.append(s2) top = max(top, max(p for p, _ in s2)) if budget and len(seen) > budget: return False, len(seen), None, top, tide frontier = nxt limits = set() for s, labels in loops.items(): unions = set() for lab in labels: unions |= {u | lab for u in unions} | {lab} for u in unions: lim = tuple((p, "inf" if p in u else ("B+" if a == cap_of(p) else a)) for p, a in s) limits.add(lim) return True, len(seen), limits, top, tide def show(lim): return "*".join(f"{p}^{a}" if a != 1 else f"{p}" for p, a in lim) # ------------------------------------------------------------- the 2-door def v2(n): return (n & -n).bit_length() - 1 def price2(mf): return growth.least_move(2, mf.get(2, 0), lam(mf)) def bound2(mf): w = max((v2(p - 1) for p in mf if p > 2), default=None) return 4 if w is None else max(4, 2 ** (w + 3)) def brute2(mf): n = growth.value(mf) L, r = growth.lam_int(n), 1 while growth.lam_int(n * 2 ** r) == L: r += 1 return 2 ** r def order2(m): k, x = 1, 2 % m while x != 1: x, k = x * 2 % m, k + 1 return k # --------------------------------------------------------------- sections def section_controls(): print("CONTROLS") box = brute_box(13) bad = sum(m0(s) != growth.brute_least(s) for s in box) check("door menu m_0 = brute_least on the box", bad == 0, f"{len(box)} states, {bad} differ") path, mf = [1], {} for _ in range(3): lf = lam(mf) moves = [m for m in range(2, m0(mf) + 1) if raises(mf, lf, m)] mf = growth.merge_add(mf, growth.factor(moves[0])) path.append(growth.value(mf)) ok, n, lims, top, _ = census(Fraction(1)) check("c = 1: the walk 1, 3, 9, 27 and the one limit 3^inf", path == [1, 3, 9, 27] and ok and sorted(lims, key=str) == [((3, "inf"),)], f"path {path}, limits " + ", ".join(show(x) for x in sorted(lims, key=str))) ok, n, lims, top, _ = census(Fraction(4, 3)) want = {((3, "inf"),), ((2, "inf"),), ((2, 2), (5, "inf"))} check("c = 4/3: exactly 3^inf, 2^inf, 2^2*5^inf, no 7", ok and lims == want and top == 5, ", ".join(show(x) for x in sorted(lims, key=str)) + f"; top prime {top}") ok, n, lims, top, _ = census(Fraction(7, 5)) check("c = 7/5 seats 7", ok and top >= 7, f"top prime {top}") check("2's price at 17 is 2^7, at 4 is 4", price2({17: 1}) == 128 and price2({2: 2}) == 4, f"{price2({17: 1})}, {price2({2: 2})}") check("J = 2, e = 5: 33 and 65 composite, by 3 and 5", 33 % 3 == 0 and 65 % 5 == 0 and not bridges.proth_prime(1, 5) and not bridges.proth_prime(2, 5)) def section_tau(): print("TAU") t0 = time.time() tab = tau_table() for P in [p for p in PR if p <= 13]: bmax = max(m0(s) for s in brute_box(P)) check(f"K1 tau({P}) = brute max over the box", tab[P][0] == bmax, f"rule {tab[P][0]}, box {bmax}") bad = [P for P in tab if m0(tab[P][1]) != tab[P][0]] check(f"the witness's m_0 is tau(P) at every prime P <= {X}", not bad, f"{len(tab)} primes" + (f", NO at {bad[:10]}" if bad else "")) print(f" ({time.time() - t0:.1f} s)") return tab def section_dams(tab): print("THE DAMS: records of rho(P) = P+/tau(P)") rec = Fraction(0) for P in sorted(tab): rho = Fraction(next_prime(P), tab[P][0]) if rho > rec: rec = rho print(f" P = {P:5d} tau = {tab[P][0]:5d} P+ = " f"{next_prime(P):5d} rho = {float(rho):.3f}") held = sorted({tab[P][0] for P in tab if tab[P][0] > 4}) for d in [5, 7, 17, 107, 227, 839]: past = next((P for P in sorted(tab) if tab[P][0] > d), None) first = min((P for P in tab if tab[P][0] == d), default=None) print(f" the tide {d} (d - 1 = {growth.factor(d - 1)}) held " + (f"from P = {first}" if d in held else "never") + f", passed first at P = {past}") for P in [11, 101, 1009, 9973]: print(f" tau({P}) = {tab[P][0]}, tau/P = {tab[P][0] / P:.3f}") dams = {} for c in [Fraction(13, 7), 2, 3, 4, 5, 6]: hit = [P for P in sorted(tab) if Fraction(next_prime(P), tab[P][0]) > c] dams[c] = hit[0] if hit else None print(f" c = {str(c):5s}: least dam P = {dams[c]}") def lock(lim): """A limit's support and the primes it sends to inf.""" return (tuple(p for p, _ in lim), tuple(p for p, a in lim if a == "inf")) def section_census(tab): print("THE CENSUS from the void, exact below 11/5 (the dam at 7)") ts = [2, 3, 4, 5, 7, 8, 9] cs = sorted({Fraction(m, t) for t in ts for m in range(t, 13 * t + 1) if 1 <= Fraction(m, t) < Fraction(11, 5)}) prev, worst, worst7 = None, 1, 1 for c in cs: ok, n, lims, top, tide = census(c) if c < Fraction(13, 7): worst = max(worst, top) worst7 = max(worst7, top) if lims != prev: locks = {lock(x) for x in lims} new = sorted(locks - {lock(x) for x in (prev or set())}) print(f" c = {str(c):5s} ({float(c):.3f}): {n} states, " f"{len(lims)} limit classes, {len(locks)} lock " f"patterns, top prime {top}, tide {tide}") if c <= Fraction(4, 3): print(" limits: " + ", ".join( show(x) for x in sorted(lims, key=str))) print(" new (support | at inf): " + "; ".join( f"{','.join(map(str, a))} | {','.join(map(str, b))}" for a, b in new)) prev = lims check("K2 no census state below 13/7 seats a prime past 11", worst <= 11, f"largest seated {worst}") check("no census state below 11/5 seats a prime past 7", worst7 <= 7, f"largest seated {worst7} over {len(cs)} values") ok, n, lims, top, tide = census(Fraction(11, 5), budget=200000) nxt = min(P for P in tab if P > 7 and Fraction(next_prime(P), tab[P][0]) > Fraction(11, 5)) check("c = 11/5 completes past 7, within the next dam", ok and 7 < top <= nxt, f"top prime {top}, " f"{'complete' if ok else 'budget hit'} at {n} states, " f"next dam P = {nxt}") def two_l1(): print(" L1: the price at 2") box = brute_box(13) rng = random.Random(1629) odd = [p for p in PR if 2 < p < 300] rand = [] for _ in range(20000): mf = {p: rng.randint(1, 3) for p in rng.sample(odd, rng.randint(0, 12))} a = rng.randint(0, 8) if a: mf[2] = a rand.append(mf) seen, states = set(), [] for s in box + rand: key = tuple(sorted(s.items())) if key not in seen: seen.add(key) states.append(s) over = [s for s in states if price2(s) > bound2(s)] oddM = [s for s in states if s and 2 not in s] neq = [s for s in oddM if price2(s) != bound2(s)] brute_bad = [s for s in box if brute2(s) != price2(s)] check("K3 price at 2 <= max(4, 2^(w+3)) at every state", not over, f"{len(states)} distinct states ({len(box)} box, " f"{len(rand)} random drawn)" + (f"; over at {over[:3]}" if over else "")) check("K3 price at 2 = 2^(w+3) at every odd M > 1", not neq, f"{len(oddM)} odd states" + (f"; differs at {neq[:3]}" if neq else "")) check("the scan at 2 = the least raising 2^r by lam_int (box)", not brute_bad, f"{len(box)} states") full = [s for s in states if s] tight = sum(price2(s) == bound2(s) for s in full) print(f" the bound attained at {tight} of {len(full)} nonempty" " distinct states") def two_l2(): print(" L2: the covering, e = 1 + L_J") L, bad, rows = 1, [], {} for J in range(1, 41): o = order2(2 * J + 1) L = L * o // gcd(L, o) e = 1 + L for j in range(1, J + 1): if (j * pow(2, e, 2 * j + 1) + 1) % (2 * j + 1): bad.append((J, j)) rows[J] = (L, log10(J) + e * log10(2)) check("K4 (2j + 1) | j 2^e + 1 at every j <= J <= 40", not bad, f"{len(bad)} failures") for J in [2, 4, 8, 16, 29, 40]: print(f" J = {J:2d}: L_J = {rows[J][0]}, rho > {J / 4:g} at" f" a P near 10^{rows[J][1]:.1f}") def two_table(tab): print(f" TABLE: tau(P) against 2^(W(P)+3), P <= {X}") pps = [t for t in prime_powers(X + 1) if t > 4] W, over, binds, slack, n3 = 0, [], [], None, 0 for P in sorted(tab): if P > 2: W = max(W, v2(P - 1)) tau = tab[P][0] if P >= 3: n3 += 1 if tau > 2 ** (W + 3): over.append(P) r = 2 ** (W + 3) / tau if slack is None or r < slack[0]: slack = (r, P) nxt = next(t for t in pps if t > tau) if (feasible(nxt, P) is None and feasible(nxt, P, bar2=False) is not None): binds.append(P) print(f" tau(P) <= 2^(W(P)+3) at {n3 - len(over)} of {n3} primes" f" 3 <= P <= {X} (the rule's 2-bar builds this in: a" " consistency print, no kill)") print(f" the 2-bar alone stops the next tide at {len(binds)} primes" + (f": {binds[:12]}" if binds else "") + f"; least 2^(W+3)/tau over P >= 3: {slack[0]:.3f} at" f" P = {slack[1]}") for P in [7, 89, 641, 1579, 5861, 9973]: Wp = max(v2(p - 1) for p in PR if 2 < p <= P) print(f" P = {P:4d}: tau {tab[P][0]:4d}, W {Wp:2d}, " f"2^(W+3) = {2 ** (Wp + 3)}") def two_proth(): print(f" PROTH: the least k with k 2^e + 1 prime, e <= {EMAX}") rec, first7, ks = 0, None, {} for e in range(1, EMAX + 1): k = 1 while not bridges.proth_prime(k, e): k += 1 ks[e] = k if k > rec: rec = k print(f" e = {e:3d}: k = {k:4d}, rho > {k / 4:g} at the" " prime before k 2^e + 1" f" (~10^{log10(k) + e * log10(2):.1f})") if first7 is None and k > 28: first7 = e mean = sum(ks.values()) / len(ks) big = sum(ks[e] / (e * log(2) / 2) for e in ks if e >= 100) print(f" max k {rec}; first e with rho > 7 proved: {first7}; " f"mean k {mean:.1f}; mean k / (e ln2 / 2) over e >= 100: " f"{big / (EMAX - 99):.2f}") def section_two(tab): print("THE TWO-ADIC DAM: the tide is at most 2's price") t0 = time.time() two_l1() two_l2() two_table(tab) two_proth() print(f" ({time.time() - t0:.1f} s)") def main(): t0 = time.time() section_controls() if not all(ok for _, ok in CHECKS): print("CONTROL FAILED: nothing below is read.") raise SystemExit(1) tab = section_tau() if not all(ok for _, ok in CHECKS): print("K1 FIRED: the rule for tau is wrong; nothing below is read.") raise SystemExit(1) section_dams(tab) section_census(tab) section_two(tab) fired = not all(ok for _, ok in CHECKS) print("KILL") print(f" {'FIRED' if fired else 'silent'}") print(f"{sum(ok for _, ok in CHECKS)}/{len(CHECKS)} checks passed, " f"{time.time() - t0:.1f} s") raise SystemExit(0 if all(ok for _, ok in CHECKS) else 1) if __name__ == "__main__": main()