cgreedy.py
Checks: IMAGE: The c-greedy walk is dammed theorem.
Cited on: IMAGE.
To run it: save cgreedy.py, with bridges.py, growth.py beside it; standard library only.
"""
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()