""" 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()