ghosts.py
Checks: GROWTH: The ghosts are the witnesses' records theorem; known.
Cited on: GROWTH.
To run it: save ghosts.py, with growth.py beside it; standard library only.
"""
ghosts.py -- a seed whose walk picks as many ghosts as a set of witness
primes allows: the ghosts up to x are the witnesses' records.
QUESTION. Is the number of ghosts a walk over Z picks before its lock
unbounded over seeds? g(w) is the least prime = 1 mod w, h(w) the least
prime = 1 mod w^2. C(x, W): W a set of odd primes, each w with w^3 > x,
g(w) <= x and g(w) < w^2, no w dividing another's w' - 1; the seed is a
product of distinct primes r > x, one per prime l <= x not in W,
r = 1 mod l^(e_l) (l^(e_l) the largest power of l at most x), no w in W
dividing r - 1. So lambda(seed) holds every l^(e_l) and no w in W.
BY HAND (fixed before the engine was written, the closed form of R
before the sets below). R is the set of w-adic records: the primes
p <= x outside W at which some w in W reaches a new largest v_w(p - 1)
among the primes. As p - 1 < w^3, v_w(p - 1) <= 2, so the records of w
are g(w) and h(w) when h(w) <= x: R = sorted(G u H), G = {g(w)},
H = {h(w) <= x}. Invariant: the seated ghosts are the records below the
next pick, and v_w(lambda) is the largest v_w(q - 1) over them (the
seed puts no w in lambda, a ghost's dowry adds q - 1, and every other
prime power of a p - 1 with p <= x is in lambda from the start). The
least unseated record p* is a candidate (p* | lambda, (p* - 1) not
dividing lambda), and a candidate below it would be a record below it,
all seated: so p* is picked, at price p*. Every other price exceeds x
or p*: a w in W opens at w^2 > g(w) while g(w) is unseated and at
w^3 > x after; 2 at 2^(v + 3) and a seated ghost at g^(e_g + 1), both
past x; a non-candidate below x at its full price p^(v + 2) > x; a seed
prime or any prime above x at more than x. Once R is seated no
candidate is left at most x. PREDICTION P: the ghosts up to x are R, in
order, each at its own price, and the next pick costs more than x.
(First frozen as "exactly G", which fails where w^2 < x: x = 110,
W = {5} picks 11 and 101 = 4 x 25 + 1.)
DESIGN. Two arms. The brute walk takes the least m >= 2 with
lambda(Mm) not dividing lambda(M), tried in order, with its own lambda
and no door formula; the second arm is growth.py's walk_to_lock. THE
FAMILY: x = 100, 400, 1000, 2500, at each x the window (A, 2A],
ceil(x^(1/3)) <= A <= x/2, whose W_A (the window's primes w with
g(w) <= x, g(w) < w^2) gives the largest |G|. THE CORNER: every window
the search admits for x = 30..400. THE SETS, built where w^2 < x: E(x)
the primes meeting C(x, W)'s conditions, C(x) those with w^2 < x; F1
every x = 30..1000, every {w} with w in C(x); F2 x = 100, 150, ...,
1000, every pair in E(x) meeting C(x), no w | w' - 1; F3 x = 400, 1000,
2500, every nonempty subset of C(x) with no w | w' - 1.
CONTROLS (read first): the brute walk from 11, 71 and 20231 ghosts [5],
[5, 7], [5, 7, 17] and locks 7, 17, 19; x = 110, W = {5} gives
R = [11, 101], and x = 200, W = {7, 11} gives [23, 29, 197]. BREAKS,
one per step the induction leans on: at x = 400 the seed built with
one w of W left in lambda loses g(w) from its ghosts; at x = 110,
W = {5}, a seed prime r with v_5(r - 1) = 1 leaves the ghosts [101],
and one with v_5(r - 1) = 2 leaves none.
KILL: over every family above, the brute walk's picks of price <= x not
all ghosts at their own price, or not R, or its next pick <= x; on the
family, walk_to_lock's ghosts up to x not R. Beside it, records(x, W)
against sorted(G u H). What makes the sets readable is printed, not
gated: the sets with H nonempty, with |H| >= 2, with a record two
witnesses share, and with a non-record candidate below max R.
FINDINGS (from the printed run; the controls and the three breaks
passed first: the x = 400 break leaves 41 in lambda and its ghost 83
goes, the other seven stay; r = 2411 and 2551 at x = 110).
P held everywhere: the ghosts up to x are R, each at its own price,
then a pick past x, and records(x, W) = sorted(G u H) at every set.
On the family every w^2 > x, so R = G, and both arms agree:
x = 100 A = 21 W = [23, 29, 41] G = [47, 59, 83]
x = 400 A = 40 |G| = 8, G = [83, 107, 173, 269, 283, 293, 317,
367] (predicted at least 8)
x = 1000 A = 100 |G| = 15, from 227 to 907
x = 2500 A = 222 |G| = 26, from 467 to 2383; the seed is 341
primes, omega_odd(lambda) 340
and the brute walk's next pick is a seed prime's deepening. Every
least move was a prime power. The corner: 33131 (x, A) windows, 8191
distinct (x, W), 1859 with some w^2 < x; only 20 windows, all with
W = {7, 11}, have ghosts beyond G. The sets: F1 4117, F2 2259, F3 493,
6832 distinct (x, W) in all (F3 repeats some of F1 and F2), H
nonempty at 1330 of them; per family H nonempty at 768, 510 and 64
(over 4, 94 and 64 witness sets), |H| >= 2 at 0, 6 and 16; a
non-record candidate at the seed below max R at 768, 1977 and 423.
No record is shared: over x = 30..5000 no pair w, v in E(x)
with no divisor between them has v | g(w) - 1, so G is never smaller
than W there (h(w) is never shared: 2 w^2 v + 1 > x), and the
frozen guess that F2 and F3 would hold shared records failed.
Run: 54.5 s, peak commit 19.7 MB, 23/23.
"""
import os
import time
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import growth # noqa: E402
CHECKS = []
LIMIT = 200000
SPF = list(range(LIMIT + 1))
for _i in range(2, int(LIMIT ** 0.5) + 1):
if SPF[_i] == _i:
for _j in range(_i * _i, LIMIT + 1, _i):
if SPF[_j] == _j:
SPF[_j] = _i
def check(name, ok, detail=""):
CHECKS.append((name, ok))
print(f" [{'PASS' if ok else 'FAIL'}] {name} {detail}")
def fac(n):
assert n <= LIMIT
f = {}
while n > 1:
p = SPF[n]
f[p] = f.get(p, 0) + 1
n //= p
return f
def is_p(n):
return 2 <= n <= LIMIT and SPF[n] == n
def lam_pp(p, a):
if a == 0:
return {}
if p == 2:
x = a - 1 if a <= 2 else a - 2
return {2: x} if x else {}
out = fac(p - 1)
if a > 1:
out[p] = a - 1
return out
def lam(mf):
out = {}
for p, a in mf.items():
for q, e in lam_pp(p, a).items():
out[q] = max(out.get(q, 0), e)
return out
def divides(a, b):
return all(b.get(q, 0) >= e for q, e in a.items())
def least_m(mf, lf):
m = 2
while True:
assert m <= LIMIT, "no raising move below the limit"
if not all(divides(lam_pp(p, mf.get(p, 0) + e), lf)
for p, e in fac(m).items()):
return m
m += 1
def kind(q, mf, lf):
if mf.get(q, 0):
return "deepen"
if lf.get(q, 0) == 0:
return "fresh"
if not divides(fac(q - 1), lf):
return "ghost"
return "full"
def brute_walk(seed):
"""[(price, prime, kind)] up to and including the first non-ghost."""
mf, out = dict(seed), []
while True:
lf = lam(mf)
m = least_m(mf, lf)
f = fac(m)
assert len(f) == 1, f"least move {m} not a prime power"
(q, r), = f.items()
k = kind(q, mf, lf)
out.append((m, q, k))
mf[q] = mf.get(q, 0) + r
if k != "ghost":
return out
def g_of(w, x):
p = w + 1
while p <= x:
if is_p(p):
return p
p += w
return None
def window(x, A):
W = []
for w in range(A + 1, 2 * A + 1):
if is_p(w) and w ** 3 > x:
g = g_of(w, x)
if g is not None and g < w * w:
W.append(w)
return W
def seed_of(x, W):
seed, Wset = {}, set(W)
for l in range(2, x + 1):
if not is_p(l) or l in Wset:
continue
pe = l
while pe * l <= x:
pe *= l
r = (x // pe + 1) * pe + 1
while not (is_p(r) and r not in seed
and not any(w in fac(r - 1) for w in Wset)):
r += pe
assert r <= LIMIT, "no seed prime below the limit"
seed[r] = 1
return seed
def records(x, W):
"""R: the primes p <= x outside W at which some w in W reaches a new
largest v_w(p - 1) among the primes."""
best, out = {w: 0 for w in W}, []
for p in range(2, x + 1):
if not is_p(p) or p in W:
continue
f = fac(p - 1)
if any(f.get(w, 0) > best[w] for w in W):
out.append(p)
for w in W:
best[w] = max(best[w], f.get(w, 0))
return out
def walk_le(x, W):
"""The brute walk's picks of price <= x, and its next pick."""
run = brute_walk(seed_of(x, W))
le = [(m, q, k) for m, q, k in run if m <= x]
nxt = run[len(le)] if len(run) > len(le) else None
return le, nxt
def matches_r(x, W):
le, nxt = walk_le(x, W)
return (all(k == "ghost" and m == q for m, q, k in le)
and [q for _, q, _ in le] == records(x, W)
and nxt is not None and nxt[0] > x), le
def section_corner():
print("THE CORNER: every admitted window, w^2 < x among them")
for x, W, want in [(110, [5], [11, 101]), (200, [7, 11], [23, 29, 197])]:
ok, le = matches_r(x, W)
got = [q for _, q, _ in le]
check(f"control x = {x}, W = {W}", ok and got == want
and records(x, W) == want, f"ghosts to x {got}")
if not all(ok for _, ok in CHECKS):
return ["control"]
n = bad = extra = 0
fired, pairs, beyond, small = [], set(), set(), set()
for x in range(30, 401):
lo = 1
while lo ** 3 < x:
lo += 1
for A in range(lo, x // 2 + 1):
W = window(x, A)
if not W:
continue
n += 1
pairs.add((x, tuple(W)))
if min(W) ** 2 < x:
small.add((x, tuple(W)))
ok, le = matches_r(x, W)
G = sorted({g_of(w, x) for w in W})
if len(le) > len(G):
extra += 1
beyond.add(tuple(W))
if not ok:
bad += 1
fired.append((x, A))
print(f" {n} (x, A) windows, x = 30..400, {len(pairs)} distinct "
f"(x, W), {len(small)} with some w^2 < x: {extra} windows with "
f"ghosts beyond "
f"G, at the witness sets {sorted(beyond)}; {bad} off R "
f"{fired[:5]}")
check("P the ghosts to x are the records R over the corner",
bad == 0, f"({n} windows)")
return fired
def section_controls():
print("CONTROLS")
want = {11: ([5], 7), 71: ([5, 7], 17), 20231: ([5, 7, 17], 19)}
for s, (gh, lock) in want.items():
run = brute_walk({s: 1})
got = [q for _, q, k in run if k == "ghost"]
check(f"brute walk from {s}", got == gh and run[-1][1] == lock,
f"ghosts {got}, lock {run[-1][1]}")
def best_window(x):
best = None
lo = 1
while lo ** 3 < x:
lo += 1
for A in range(lo, x // 2 + 1):
W = window(x, A)
G = sorted({g_of(w, x) for w in W})
if best is None or len(G) > len(best[2]):
best = (A, W, G)
return best
def section_break():
print("BREAK at x = 400")
A, W, G = best_window(400)
w0 = W[0]
run = brute_walk(seed_of(400, W[1:]))
got = [q for _, q, k in run if k == "ghost" and q <= 400]
check("one witness left in lambda loses its ghost",
g_of(w0, 400) not in got and got == records(400, W[1:]),
f"w = {w0}, g(w) = {g_of(w0, 400)}; ghosts {got}")
def section_family():
print("THE FAMILY")
fired = []
for x in (100, 400, 1000, 2500):
t0 = time.time()
A, W, G = best_window(x)
seed = seed_of(x, W)
lf = lam(seed)
om = sum(1 for q in lf if q > 2)
run = brute_walk(seed)
picks_le = [(m, q, k) for m, q, k in run if m <= x]
ok_b = ([q for _, q, _ in picks_le] == G
and all(k == "ghost" and m == q for m, q, k in picks_le)
and len(run) > len(G) and run[len(G)][0] > x)
nxt = run[len(G)] if len(run) > len(G) else None
gh, lock, _, _ = growth.walk_to_lock(seed, extra=0)
ok_g = [q for q in gh if q <= x] == G
print(f" x = {x}: A = {A}, |W| = {len(W)}, |G| = {len(G)}, "
f"seed primes {len(seed)}, omega_odd(lambda) {om}")
if x <= 400:
print(f" W = {W}")
print(f" G = {G}")
else:
print(f" G from {G[0]} to {G[-1]}")
print(f" R = G: {records(x, W) == G}; "
f"brute: {len(run)} picks; past G {nxt}; "
f"growth.py: {len(gh)} ghosts, lock {lock}; "
f"{time.time() - t0:.1f} s")
check(f"x = {x} brute walk picks G, then past x", ok_b)
check(f"x = {x} walk_to_lock's ghosts to x are G", ok_g)
if not (ok_b and ok_g):
fired.append(x)
return fired
def h_of(w, x):
"""The least prime = 1 mod w^2, if at most x."""
return g_of(w * w, x)
def eligible(x):
return [w for w in range(2, x) if is_p(w) and w ** 3 > x
and g_of(w, x) is not None and g_of(w, x) < w * w]
def nodiv(W):
return not any(w != v and (v - 1) % w == 0 for w in W for v in W)
def predicted(x, W):
"""sorted(G u H): v_w(p - 1) <= 2 for p <= x, so each w has at most
two records, g(w) and h(w)."""
out = {g_of(w, x) for w in W}
out |= {h_of(w, x) for w in W if h_of(w, x) is not None}
return sorted(out)
def picks_le(x, seed):
run = brute_walk(seed)
le = [(m, q, k) for m, q, k in run if m <= x]
nxt = run[len(le)] if len(run) > len(le) else None
return le, nxt
def section_breaks():
print("BREAKS at x = 110, W = {5}: a seed prime starts v_5(lambda)")
x, W = 110, [5]
for mod, want in [(5, [101]), (25, [])]:
seed = seed_of(x, W)
r = max(seed) + 1
while not (is_p(r) and (r - 1) % mod == 0
and fac(r - 1).get(5, 0) == (1 if mod == 5 else 2)):
r += 1
seed[r] = 1
le, nxt = picks_le(x, seed)
got = [q for _, q, _ in le]
check(f"r = {r}, v_5(r - 1) = {fac(r - 1)[5]}: ghosts to x {want}",
got == want and all(k == "ghost" for _, _, k in le)
and nxt is not None and nxt[0] > x,
f"got {got}, next {nxt}")
def run_sets(name, sets):
"""sets: [(x, W)]. The kill and the readability prints."""
bad, fired = 0, []
n = hne = h2 = shared = nonrec = prop = 0
hsets = set()
for x, W in sets:
R = predicted(x, W)
prop += records(x, W) != R
le, nxt = picks_le(x, seed_of(x, W))
ok = ([q for _, q, _ in le] == R
and all(k == "ghost" and m == q for m, q, k in le)
and nxt is not None and nxt[0] > x)
n += 1
if not ok:
bad += 1
fired.append((x, tuple(W)))
H = [h_of(w, x) for w in W if h_of(w, x) is not None]
hne += len(H) > 0
if H:
hsets.add(tuple(W))
h2 += len(H) >= 2
shared += any(sum((p - 1) % w == 0 for w in W) >= 2 for p in R)
nonrec += any(is_p(p) and p not in W and p not in R
and any((p - 1) % w == 0 for w in W)
for p in range(2, max(R)))
print(f" {name}: {n} sets; H nonempty {hne} (witness sets "
f"{len(hsets)}), |H| >= 2 {h2}, a shared record {shared}, a "
f"non-record candidate at the seed below max R {nonrec}")
print(f" {name}: off sorted(G u H): {bad} {fired[:5]}")
check(f"{name} records(x, W) = sorted(G u H)", prop == 0,
f"({prop} differ)")
check(f"{name} the ghosts to x are sorted(G u H), then past x",
bad == 0, f"({n} sets)")
return fired
def section_sets():
print("THE SETS at the corner w^2 < x")
f1 = [(x, [w]) for x in range(30, 1001) for w in eligible(x)
if w * w < x]
f2 = []
for x in range(100, 1001, 50):
E = eligible(x)
for i, w in enumerate(E):
for v in E[i + 1:]:
if (w * w < x or v * v < x) and nodiv([w, v]):
f2.append((x, [w, v]))
f3 = []
for x in (400, 1000, 2500):
C = [w for w in eligible(x) if w * w < x]
for mask in range(1, 1 << len(C)):
W = [C[i] for i in range(len(C)) if mask >> i & 1]
if nodiv(W):
f3.append((x, W))
shared = 0
for x in range(30, 5001):
E = eligible(x)
Es = set(E)
shared += sum(1 for w in E for v in fac(g_of(w, x) - 1)
if v != w and v in Es and nodiv([w, v]))
print(f" x = 30..5000: {shared} pairs w, v in E(x), no divisor between "
f"them, with v | g(w) - 1 (a record two witnesses share)")
union = {(x, tuple(W)) for x, W in f1 + f2 + f3}
print(f" F1 u F2 u F3: {len(union)} distinct (x, W), H nonempty at "
f"{sum(1 for x, W in union if any(h_of(w, x) for w in W))}")
fired = []
for name, sets in (("F1", f1), ("F2", f2), ("F3", f3)):
t0 = time.time()
fired += run_sets(name, sets)
print(f" {name}: {time.time() - t0:.1f} s")
return fired
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)
section_break()
section_breaks()
fired = section_family() + section_corner() + section_sets()
print("KILL")
print(f" {'FIRED at ' + str(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()