growth.py
Checks: CASCADE: A dead level past 0 at odd p is a full-price opening over Z criterion; rule; GROWTH: The three fates theorem; GROWTH: The wall is Adams' number property; GROWTH: The wall over F₂[x] theorem; GROWTH: The lock-prime law theorem; rule; GROWTH: The two-adic prices theorem; IMAGE: The gap rule.
Cited on: CASCADE, GROWTH, IMAGE.
To run it: save growth.py; standard library only.
"""growth.py -- a modulus grown by the cheapest move a demand admits: the
three fates, the wall mortality stops at, the prime the dynamics demand
locks onto, and the two facts about -1 that price the prime 2.
QUESTION. A GROWTH LAW is a structural demand on extensions plus the
greedy move: from the state Z/M, extend to Z/Mm with m >= 2 the least
multiplier the demand admits. The demands are stated without the word
prime:
independence Z/Mm = Z/M x Z/m, i.e. gcd(m, M) = 1;
new idempotents
the idempotent count grows, omega(Mm) > omega(M);
dynamics lambda(Mm) > lambda(M), lambda the unit group's
exponent (the Carmichael function);
new orders the set of unit orders the ring realizes grows;
transparency M grows while lambda stays fixed;
rate among m <= H, maximize the idempotent doublings bought
per bit, (omega(Mm) - omega(M)) / log2(m).
What does each demand grow, where does it stop if it stops, and what
decides where it goes?
THE OBJECT. States are positive integers M, carried as factorizations;
lambda(p^a) = p^(a-1)(p - 1) at odd p, lambda(2) = 1, lambda(4) = 2,
lambda(2^a) = 2^(a-2) at a >= 3, lambda of a product the lcm. The WALL
W(L) is the largest M with lambda(M) | L. A trajectory's LIMIT is the
supernatural number it converges to, a product over the primes with
exponents in {0, 1, ..., infinity}, and the three FATES are properties
of that limit: BREADTH, every prime seated; DEPTH, some prime at
infinite exponent; MORTALITY, the limit a finite integer. They are not
a partition; that each greedy law realizes exactly one of them is a
fact about greed.
THE ARGUMENT (written before the engine).
(1) THE LEAST-NEW LEMMA. The least m >= 2 with gcd(m, M) = 1 is the
least prime q not dividing M: every 2 <= m < q has its prime
factors below q, all of which divide M. So greedy independence
never picks a composite, and from any seed its picks are the
primes the seed lacks in increasing order (THE HEALING RULE):
from 1 it is the primorial tower. The least m adding a new prime
factor is the same q, so new idempotents grows the same tower.
(2) ORDERS ARE DIVISORS. A finite abelian group of exponent lambda
realizes exactly the divisors of lambda as element orders, so the
new-orders demand is the dynamics demand.
(3) THE RATE ARGMAX. From p_k#, a single new prime q buys one
doubling for log2 q bits; two new primes q < q' buy two for
log2 q + log2 q' > 2 log2 q; a multiplier with an old factor pays
bits for nothing. So the unique maximizer is the next prime.
(4) THE WALL. lambda(a) | lambda(b) when a | b, and lambda(lcm) =
lcm(lambda), so {M : lambda(M) | L} is closed under lcm; it is
finite since (p - 1) | L bounds p and the exponents are bounded.
Its maximum is W(L) = 2^(v_2(L) + 2) x prod p^(v_p(L) + 1) over
the odd p with (p - 1) | L, at even L, and W(odd L) = 2. Along a
transparent walk lambda(M) = L throughout, so the walk stays
among the divisors of W(L); and it cannot stop below the wall,
because while M < W(L) the least prime factor p of W(L)/M is
admissible (Mp | W(L), so lambda(Mp) divides L and is divided
by lambda(M) = L). So it dies at exactly W(lambda(seed)).
(5) ADAMS' NUMBER. "lambda(M) | L" and "z^L = 1 (mod M) for every
unit z" are one condition, so W(L) is the number Adams defined,
the gcd over the integers y of y^s (y^L - 1) for s large (J. F.
Adams, On the groups J(X) II, Topology 3, 1965), and his theorem
gives W(L) = denominator(B_L / 2L) at even L: 24, 240, 504, 480,
264, 65520 at L = 2..12, the orders of the image of the
J-homomorphism. This script computes the gcd and the Bernoulli
numbers from scratch; it uses no homotopy. The squarefree
kernel of W(L) is the von Staudt-Clausen product
prod_{(p - 1) | L} p.
(6) THE WALL OVER F_2[x]. At an irreducible g of degree d the unit
group of F_2[x]/(g^a) has exponent (2^d - 1) 2^(ceil log2 a):
the units are F_(2^d)^x times the 1-units 1 + g F_2[x]/(g^a),
and (1 + u)^(2^j) = 1 + u^(2^j) is 1 at every such u iff
2^j >= a. So lambda(g^a) | L iff (2^d - 1) | L and a <= 2^(v_2 L), and
W(L) = prod over d with (2^d - 1) | L of
(the product of the irreducibles of degree d)^(2^v_2 L).
At L = (2^n - 1) 2^v the admissible degrees are the divisors of
n and W(L) = (x^(2^n) + x)^(2^v). The wall exists over both rings
for the same reason; its value is the ring's.
(7) THE DOOR MENU. lambda(Mm) is the lcm of lambda at the prime
powers exactly dividing Mm, so a lambda-raising m has one prime
power part q^r that raises lambda alone; the least raising move is
a prime power, the least at each q being q^r with r its DOOR. With
a = v_q(M) and v = v_q(lambda): at odd q, a >= 1, the door is v - a + 2 (q - 1
already divides lambda, and the q-part must pass v); at odd q,
a = 0, it is 1 if (q - 1) does not divide lambda, else v + 2; at
q = 2 it is the scan over lambda(2^j) = 1, 2, 2, 4, .... Least
moves at distinct primes are powers of distinct primes, so they
never tie:
greedy dynamics over Z needs no tie-break.
(8) THE LOCK. Call a least move a DEEPENING (q | M), a FRESH OPENING
(q coprime to M and to lambda), a GHOST (q coprime to M, q |
lambda, (q - 1) not dividing lambda), or an opening at FULL PRICE
(q coprime to M, q | lambda, (q - 1) | lambda, at q^(v + 2), or
2^(v + 3) at 2). Every pick but a ghost leaves v_q(lambda) =
a_q - 1 (THE RECURRENCE INVARIANT;
a_q - 2 at q = 2 once a_q >= 3), which holds q's door at 1, price
q, from then on, while every other least move is nondecreasing as
lambda grows and never costs q. So the first pick that is not a
ghost locks the trajectory onto q. A ghost at a prime q' is legal only while
(q' - 1) does not divide lambda, which only gets harder, so
ghosts come in increasing order; and a later ghost divides
lambda(seed), since the factors a ghost q' adds are factors of
q' - 1 < q'. So the
lock falls within omega_odd(lambda(seed)) + 1 picks and the basin
map seed -> lock prime is computable. A ghost's DOWRY, the
factors of q' - 1 it adds to lambda, can shut a cheaper lock:
seed 11 ghosts 5 and locks 7; seed 71 ghosts 5, 7 and locks 17;
the prime seed 20231, with 20230 = 2 x 5 x 7 x 17^2, ghosts 5, 7,
17 and locks 19, the bound attained. From 1
the walk is 3, 9, 27, ...: 2's first door from the void is 2,
price 4.
(9) EVERY PRIME IS SOME SEED'S LOCK. For odd q put B = lcm of
{p - 1 : p <= q} and of l^(c_l) for the primes l < q, c_l least
with l^(c_l + 2) > q; take a prime P = 1 (mod B), P != 1 (mod
q), which Dirichlet supplies since q does not divide B. The seed
qP has lambda = P - 1; q's door is 1, price q (q does not divide
P - 1); every opening below q is shut ((l - 1) | B) with its least
move l^(v_l + 2) >= l^(c_l + 2) > q; every other least move costs
more than q; no ghost fires below q. So the first pick deepens q. At
q = 2 the seed 2 locks at 2 and no blocker is needed.
(10) THE COLD OPENINGS. From every M >= 3 lambda is even, so the opening
at 2 (M odd) costs 2^(v + 3) >= 16 and the opening at 3 (M prime
to 3) costs 3^(v_3 + 2) >= 9; every prime q >= 5 opens at its
face value q from lambda = 2.
(11) THE TWO-ADIC PRICES. Z_2^x = {+-1} x (1 + 4 Z_2), where every
odd Z_p^x is procyclic: this SPLITTING is the finite fact
lambda(2^a) = 2^(a-2) at a >= 3. A COUNTERFEIT column at 2 with the
odd pattern lambda*(2^a) = 2^(a-1), agreeing at a = 1, 2, turns
the splitting off and leaves the EVENNESS (-1 has order 2 in
every odd residue field) alone. On odd M > 1 the real 2-door is
v + 3, the counterfeit v + 2; at M >= 3 prime to 3 the 3-door is
v_3 + 2 in both. The
cold opening at 2 is the two together: floor 16 real, 8
counterfeit. The walk from 4 pays 4 then 2, 2, ... (lambda(4) =
lambda(8)) and pays 2, 2, ... under the counterfeit. At a
characteristic p a rise of v_p(lambda) is carried by a norm
h p^(v_p(lambda) + 1) + 1 cheaper than p's opening at full price:
h <= p - 1 at odd p, but at 2 that price 2^(v + 3) admits h in
{1, 2, 3}, and
h = 2, the norm 2^(v + 2) + 1, raises by two; the counterfeit
admits h = 1
only. The two
facts are the two valuations of -1 - 1 = -2.
DESIGN. Standard library only; one process.
A the chart. The least-new lemma over every M <= 10^5 against a
direct scan; the healing rule, seeds 1..100 x 25 steps; new idempotents =
independence over M <= 10^5; realized orders = divisors of lambda
over 3 <= M <= 1200, each unit checked to satisfy a^lambda = 1 and
its order read as the least divisor d of lambda with a^d = 1; the rate argmax from p_k#, k = 1..6, over
m <= 1000; the transparent walk from every seed 2..100.
B the wall. POSITIVE CONTROL first, stopping the run when it fails:
Bernoulli numbers by the exact recurrence, whose denominators
must match von Staudt-Clausen at every even L <= 200. Then W(L)
against Adams' gcd at (s, K) = (20, 60) and (40, 120) at every
L <= 200, and against denominator(B_L / 2L) at every even
L <= 200; the kernel and W(odd L) = 2 print, the closed form
making them. Over
F_2[x]: POSITIVE CONTROL, the exponent law against the unit group
computed element by element at every g^a of degree <= 9 with
deg g <= 4 and a <= 5;
then the closed form of W(L) against brute search over every
monic of degree <= 10, every L <= 64 whose wall has degree
<= 10, and every state
with lambda | L tested for dividing W(L); the special form at
n <= 4, v <= 2.
C the lock. POSITIVE CONTROL, run before section A since every
section reads lambda, and stopping the run when it fails: the
formula against the unit group's exponent from element orders,
every M <= 300. The door menu against the brute least
lambda-raising m at every M <= 20000; the least moves distinct, a
print ((7) makes them powers of distinct primes); the least
move's kind, one of the four of (8), counted. Seeds 1..2000, each
walked to its lock and 30 steps past it: the first non-ghost pick
locks, the invariant holds at every step, ghosts increase and
divide lambda(seed), so number at most omega_odd(lambda(seed)). The
specimens of (8). The cold openings over the same M. The blockers
at every prime q <= 47.
D the two-adic prices, both tables, odd 3 <= M <= 20000; the 3-door
in both worlds at every 3 <= M <= 20000 prime to 3, even M
included, where the counterfeit moves lambda; the carriers'
rises print, being arithmetic.
PREDICTIONS, fixed before the run (the figures are those of the scripts
this one replaces; the argument above says why each should hold).
A1 least-new lemma 100000/100000; healing 100/100 seeds; new idempotents =
independence 100000/100000; orders = divisors at 1198/1198 rings.
A2 the rate argmax is p_(k+1) at k = 1..6, unique.
A3 every transparent walk from 2..100 dies at W(lambda(seed)); seed
73 climbs to W(72) = 20,174,525,280 in 13 steps.
A4 (added when the claim was widened from greed to every policy)
every seed 2..100 with W(lambda(seed)) <= 10^5: the states any
transparent policy reaches, searched over every admissible m, are
exactly the multiples of the seed dividing W, the only state with
no admissible move is W, and the longest run has Omega(W/seed)
moves.
B1 the control matches at 100/100 even L. W(L) = Adams' gcd at both
(s, K) at every L <= 200, = denominator(B_L / 2L) at every even
L; 24, 240, 504, 480, 264, 65520 at L = 2..12, 138181680 at 36;
kernel = the von Staudt-Clausen product; W(odd L) = 2.
B2 F_2[x]: the exponent law holds at every tested prime power; the
closed form matches brute at 44 values of L with 0 lattice
failures; the special form holds at every (n, v) tested.
C1 the control holds at 299/299; the menu matches brute at
20000/20000, costs distinct, kinds exclusive.
C2 2000/2000 seeds lock at the first non-ghost pick and stay locked
30 steps, invariant at every step, the wander bound at every
seed; the largest wander below 2000 is at most 3.
C3 seed 11 ghosts [5], locks 7; 71 ghosts [5, 7], locks 17; 20231
ghosts [5, 7, 17], locks 19; seed 1 walks 3, 9, 27; seed 4's
walk pays 4 then 2.
C4 cold-opening minima 16 and 9 over 3 <= M <= 20000; every
5 <= q <= 47 opens at q from lambda = 2.
C5 the blocker seed locks at q, wander 0, at all 15 primes q <= 47;
P = 5 at q = 3, 13 at q = 5, 7; 61 at 11, 13; 241 at 17; 2161 at
19; 23761 at 23; 55441 at 29, 31, 37, 41, 43; 1275121 at 47.
D1 real 2-door v + 3 and counterfeit v + 2 at every odd M > 1, price
floors 16 and 8; the 3-door identical in both; the carriers
under the full-price opening {1, 2, 3} with rises {1, 2, 1} real
and {1} with rise 1 counterfeit, every odd p <= 50 admitting 1..p - 1 with
rise 1; the walk from 4 real [4, 2, 2, ...], counterfeit
[2, 2, 2, ...]; the prime powers among 2^k + 1, k <= 20, exactly
3, 5, 9, 17, 257, 65537.
A KILL is any printed disagreement in these sections: one of them
refutes the claim that section is named for. (Ruled on a code read:
C1's distinctness, B1's kernel and W(odd L) = 2, C2's wander bound and
D1's carriers hold by construction and print; "kinds exclusive" is
kind()'s if-chain; A4 searches states past W, to 4W.)
FINDINGS. Every prediction landed: 38/38 checks PASS.
A1 least-new lemma and new idempotents = independence at 100000/100000; the
healing rule at 100/100 seeds; orders = divisors at 1198/1198
rings (437,784 units read).
A2 the rate argmax from p_k#, k = 1..6: 3, 5, 7, 11, 13, 17, each
unique.
A3 all 99 transparent walks die at W(lambda(seed)) with no admissible
m <= 2000 left; seed 73 dies at 20174525280 after 13 steps.
A4 over the 80 seeds 2..100 with W <= 10^5, searched over every
move to a state up to 4W, the reachable set is the seed's
multiples dividing W, W the only dead state, the longest run
Omega(W/seed), 0 off in each.
B1 the control 100/100; W(L) = Adams' gcd at both (s, K), L <= 200,
and = denominator(B_L / 2L) at every even L <= 200, 0 off; the
table 24, 240, 504, 480, 264, 65520, W(36) = 138181680; the kernel
the von Staudt-Clausen product at every L; W(odd L) = 2.
B2 the exponent law at all 26 g^a of degree <= 9 with deg g <= 4,
a <= 5; the closed
form the brute maximum at 44 values of L, every state with
lambda | L dividing W(L); the special form at all 12 (n, v).
C1 the lambda control 299/299; the menu = brute at 20000/20000,
costs distinct; the least move's kind: 10967 deepenings, 6782
fresh openings, 2251 ghosts, no opening at full price.
C2 2000/2000 seeds lock at the first non-ghost pick and hold 30
more steps with the invariant; the largest wander below 2000 is
2, first at seed 71 (the bound's 3 is attained at 20231).
C3 11 -> [5] -> 7; 71 -> [5, 7] -> 17; 20231 -> [5, 7, 17] -> 19;
seed 1 walks 3, 9, 27. The full-price kind is not empty. It is
least only when no prime = 1 (mod q^(v + 1)) lies below its
price, since such a prime would divide M, lifting v_q(lambda), or
open at its own face value. At q = 3, v = 2 the candidates 28 and
55 are composite, and a prime seed P with P = 1 (mod lcm{l - 1 :
l prime, 5 <= l < 81}), 27 not dividing P - 1, shuts every
cheaper move: the least such P, 961440481 (least by cascade.py's
construction, prime by Miller-Rabin, deterministic there), opens
3 at 81 and locks at 3, the invariant set by the opening itself.
C4 cold-opening minima 16 and 9; every 5 <= q <= 47 opens at q from
lambda = 2.
C5 all 15 primes q <= 47 lock their blocker seeds with wander 0, at
the recorded P.
D1 the real 2-door v + 3 and the counterfeit v + 2 at every odd
3 <= M <= 20000, price floors 16 and 8, the 3-door unmoved at
every 3 <= M <= 20000 prime to 3, even M included; the carriers
{1, 2, 3} rising {1, 2, 1} against {1} rising 1, and 1..p - 1
rising 1 at every odd p <= 47; seed 4 pays [4, 2, 2, ...] real and
[2, 2, 2, ...] counterfeit; the prime powers among 2^k + 1,
k <= 20, are 3, 5, 9, 17, 257, 65537.
Tiers: the chart, the wall (4) and its closed form over F_2[x] (6),
the door menu, the lock, every prime a lock (9), the cold openings
(10) and the two-adic prices are theorems, each proved above and
verified in the ranges printed; the wall being Adams' number is a
property (one condition, two names), its Bernoulli form Adams'
theorem, checked here at every even L <= 200.
RUN RECORD. 38/38, 1.8 s wall, 10 MB peak commit under a memory guard. After
the first run the lambda control moved ahead of section A, which reads
lambda first; the second run printed the same 38/38. Review then found
the full-price kind; with its specimen check added the run prints
39/39. A4's three checks, added when the claim was widened to every
policy, print 42/42 in 2.0 s. A code read then made the checks that
held by construction prints (C1's distinctness, B1's kernel and
W(odd L), C2's wander bound, D1's carriers), widened A4's search to 4W
and the 3-door to even M, and made the controls stop the run: 38/38,
2.9 s, 9.5 MB. A later code read made A1 check a^lambda = 1 at every
unit and C4 read lambda instead of least_move's formula: 38/38.
"""
from fractions import Fraction
from math import comb, gcd, log2
CHECKS = []
def check(name, ok, detail=""):
CHECKS.append(bool(ok))
print(f" [{'PASS' if ok else 'FAIL'}] {name}"
+ (f" -- {detail}" if detail else ""))
def control(name, ok, detail=""):
check(name, ok, detail)
if not ok:
print(" control failed: run stopped")
raise SystemExit(1)
def section(title):
print()
print("=" * 72)
print(title)
print("=" * 72)
# ------------------------------------------------------------ arithmetic
def primes_up_to(n):
s = bytearray([1]) * (n + 1)
s[0] = s[1] = 0
for i in range(2, int(n ** 0.5) + 1):
if s[i]:
s[i * i::i] = bytearray(len(s[i * i::i]))
return [i for i in range(n + 1) if s[i]]
PRIMES = primes_up_to(20000)
def factor(n):
"""Trial division by the primes to 20000, as a {prime: exponent} map:
exact when what is left past them is 1 or below 4 * 10^8 (a prime
then), so for every n up to 4 * 10^8 and any 20000-smooth n."""
f = {}
for p in PRIMES:
if p * p > n:
break
while n % p == 0:
f[p] = f.get(p, 0) + 1
n //= p
if n > 1:
f[n] = f.get(n, 0) + 1
return f
def is_prime(n):
return n >= 2 and factor(n) == {n: 1}
def value(f):
v = 1
for p, e in f.items():
v *= p ** e
return v
def merge_max(a, b):
out = dict(a)
for p, e in b.items():
if e > out.get(p, 0):
out[p] = e
return out
def merge_add(a, b):
out = dict(a)
for p, e in b.items():
out[p] = out.get(p, 0) + e
return out
def divides(a, b):
"""The factorization a divides the factorization b."""
return all(e <= b.get(p, 0) for p, e in a.items())
def lcm(a, b):
return a // gcd(a, b) * b
def v2(n):
return (n & -n).bit_length() - 1
def lam_pp(p, a, counterfeit=False):
"""lambda(p^a) as a factorization. The counterfeit column at 2 wears
the odd pattern 2^(a-1)."""
if a == 0:
return {}
if p == 2:
x = a - 1 if (counterfeit or a <= 2) else a - 2
return {2: x} if x else {}
out = factor(p - 1)
if a > 1:
out[p] = a - 1
return out
def lam(mf, counterfeit=False):
out = {}
for p, e in mf.items():
out = merge_max(out, lam_pp(p, e, counterfeit))
return out
def lam_int(M):
return value(lam(factor(M))) if M > 1 else 1
def wall(L):
"""W(L), the largest M with lambda(M) | L, by the closed form, its
odd primes the d + 1 over the divisors d of L; L < 4 * 10^8."""
if L % 2:
return 2
assert L < 4 * 10 ** 8
lf = factor(L)
divs = [1]
for p, e in lf.items():
divs = [d * p ** k for d in divs for k in range(e + 1)]
w = 2 ** (lf[2] + 2)
for d in divs:
if d > 1 and is_prime(d + 1):
w *= (d + 1) ** (lf.get(d + 1, 0) + 1)
return w
# ------------------------------------------------------- the least moves
def least_move(q, a, lamf, counterfeit=False):
"""The least q^r, r the door, raising lambda where v_q(M) = a."""
if q == 2:
j = a + 1
while divides(lam_pp(2, j, counterfeit), lamf):
j += 1
return 2 ** (j - a)
v = lamf.get(q, 0)
if a >= 1:
assert v - a + 2 >= 1
return q ** (v - a + 2)
if not divides(factor(q - 1), lamf):
return q
return q ** (v + 2)
def menu(mf, lamf, counterfeit=False):
"""Every least move below the running least, and the least one."""
best, bq, moves = None, None, {}
for q in PRIMES:
if best is not None and q >= best:
break
d = least_move(q, mf.get(q, 0), lamf, counterfeit)
moves[q] = d
if best is None or d < best:
best, bq = d, q
return bq, best, moves
def kind(q, mf, lamf):
if mf.get(q, 0):
return "deepen"
if lamf.get(q, 0) == 0:
return "fresh"
if not divides(factor(q - 1), lamf):
return "ghost"
return "full"
def step(mf, q, cost):
r = 0
while cost > 1:
cost //= q
r += 1
mf = dict(mf)
mf[q] = mf.get(q, 0) + r
return mf
def walk_to_lock(seed_f, extra=30):
"""Greedy dynamics from a seed: the ghosts, the lock prime, and
whether the lock pick and `extra` more steps stay on it with the
recurrence invariant intact."""
mf = dict(seed_f)
lamf = lam(mf)
ghosts, lock, ok, tail = [], None, True, 0
while tail <= extra:
q, cost, _ = menu(mf, lamf)
k = kind(q, mf, lamf)
if lock is None:
if k == "ghost":
ghosts.append(q)
else:
lock = q
elif q != lock or k != "deepen":
return ghosts, lock, False, mf
mf = step(mf, q, cost)
lamf = lam(mf)
if lock is not None:
a, v = mf[lock], lamf.get(lock, 0)
if lock == 2 and a >= 3:
ok = ok and v == a - 2
else:
ok = ok and v == a - 1
tail += 1
return ghosts, lock, ok, mf
def omega_odd(f):
return sum(1 for p in f if p != 2)
# ------------------------------------------------------------- section A
def section_a():
section("A THE CHART: what each demand grows")
bad_new = bad_mem = 0
for M in range(1, 100001):
q = next(p for p in PRIMES if M % p)
m = 2
while gcd(m, M) != 1:
m += 1
bad_new += m != q
m = 2
while all(M % p == 0 for p in factor(m)):
m += 1
bad_mem += m != q
check("A1 least-new lemma: the least coprime m is the least absent "
"prime", bad_new == 0, f"100000 states, {bad_new} off")
check("A1 new idempotents picks what independence picks", bad_mem == 0,
f"100000 states, {bad_mem} off")
bad = 0
for seed in range(1, 101):
M, picks = seed, []
for _ in range(25):
m = 2
while gcd(m, M) != 1:
m += 1
picks.append(m)
M *= m
bad += picks != [p for p in PRIMES if seed % p][:25]
check("A1 healing: the picks are the seed's missing primes in order",
bad == 0, f"100 seeds x 25 steps, {bad} seeds off")
bad = units = 0
for M in range(3, 1201):
lf = lam(factor(M))
L = value(lf)
orders = set()
for a in range(1, M):
if gcd(a, M) != 1:
continue
units += 1
bad += pow(a, L, M) != 1
o = L
for p in lf:
while o % p == 0 and pow(a, o // p, M) == 1:
o //= p
orders.add(o)
bad += orders != {d for d in range(1, L + 1) if L % d == 0}
check("A1 the realized unit orders are the divisors of lambda",
bad == 0, f"1198 rings, {units} units, {bad} off")
rows = []
for k in range(1, 7):
M = 1
for p in PRIMES[:k]:
M *= p
have = set(factor(M))
rates = sorted(((len(set(factor(m)) - have) / log2(m), m)
for m in range(2, 1001)), reverse=True)
rows.append((k, rates[0][1], rates[0][0] - rates[1][0] > 1e-12))
print(" rate argmax from p_k#, k = 1..6:", [m for _, m, _ in rows])
check("A2 the rate's unique argmax is the next prime",
all(m == PRIMES[k] and u for k, m, u in rows))
bad, spec = 0, None
for seed in range(2, 101):
mf, steps = factor(seed), 0
L = value(lam(mf))
while True:
m = 2
while m <= 2000 and value(lam(merge_add(mf, factor(m)))) != L:
m += 1
if m > 2000:
break
mf = merge_add(mf, factor(m))
steps += 1
bad += value(mf) != wall(L)
if seed == 73:
spec = (value(mf), steps)
print(f" seed 73 dies at {spec[0]} after {spec[1]} steps")
check("A3 every transparent walk dies at W(lambda(seed)), no "
"admissible m <= 2000 left", bad == 0, f"99 seeds, {bad} off")
check("A3 seed 73 climbs to W(72) = 20174525280 in 13 steps",
spec == (20174525280, 13) and wall(72) == 20174525280)
seeds = lat = ends = long = 0
for seed in range(2, 101):
L = lam_int(seed)
W = wall(L)
if W > 10 ** 5:
continue
seeds += 1
depth, todo, dead = {seed: 0}, [seed], set()
while todo:
M = todo.pop()
moves = [m for m in range(2, 4 * W // M + 1)
if lam_int(M * m) == L]
if not moves:
dead.add(M)
for m in moves:
if depth.get(M * m, -1) < depth[M] + 1:
depth[M * m] = depth[M] + 1
todo.append(M * m)
lat += set(depth) == {M for M in range(seed, W + 1, seed)
if W % M == 0}
ends += dead == {W}
long += max(depth.values()) == sum(factor(W // seed).values())
print(f" every transparent policy, {seeds} seeds with W <= 10^5, "
"states searched to 4W")
check("A4 the reachable states are the seed's multiples dividing W",
lat == seeds, f"{seeds - lat} off")
check("A4 every policy ends at W and only there", ends == seeds,
f"{seeds - ends} off")
check("A4 the longest run has Omega(W/seed) moves", long == seeds,
f"{seeds - long} off")
# ------------------------------------------------------------- section B
def bernoulli(n):
B = [Fraction(1)]
for m in range(1, n + 1):
B.append(-sum(comb(m + 1, k) * B[k] for k in range(m)) / (m + 1))
return B
def vsc(L):
"""The von Staudt-Clausen product over the p with (p - 1) | L."""
out = 1
for p in PRIMES:
if p - 1 > L:
break
if L % (p - 1) == 0:
out *= p
return out
def adams(L, s, K):
g = 0
for k in range(2, K + 1):
g = gcd(g, k ** s * (k ** L - 1))
return g
def section_b_z():
section("B THE WALL over Z: Adams' number")
B = bernoulli(200)
ok = sum(B[L].denominator == vsc(L) for L in range(2, 201, 2))
control("B1 control: denominator(B_L) is the von Staudt-Clausen "
"product at even L <= 200", ok == 100, f"{ok}/100")
bad_a = bad_b = bad_k = 0
for L in range(1, 201):
W = wall(L)
bad_a += W != adams(L, 20, 60) or W != adams(L, 40, 120)
if L % 2 == 0:
bad_b += W != (B[L] / (2 * L)).denominator
kern = 1
for p in factor(W):
kern *= p
bad_k += kern != vsc(L)
table = [wall(L) for L in range(2, 13, 2)]
print(" W(L) at L = 2..12:", table, " W(36) =", wall(36))
check("B1 W(L) is Adams' gcd at (s, K) = (20, 60) and (40, 120), "
"L <= 200", bad_a == 0, f"{bad_a} off")
check("B1 W(L) = denominator(B_L / 2L) at every even L <= 200",
bad_b == 0, f"{bad_b} off")
check("B1 the table 24, 240, 504, 480, 264, 65520 and W(36) = "
"138181680", table == [24, 240, 504, 480, 264, 65520]
and wall(36) == 138181680)
print(f" squarefree kernel of W(L) against the von Staudt-Clausen "
f"product, L <= 200: {bad_k} off; W(odd L) = 2 at every odd "
f"L <= 200: {all(wall(L) == 2 for L in range(1, 201, 2))} "
"(the closed form)")
# ------------------------------------------------- F_2[x] on int encodings
# bit i is the coefficient of x^i: 2 = x, 3 = x + 1, 7 = x^2 + x + 1.
def pdeg(a):
return a.bit_length() - 1
def pmul(a, b):
r = 0
while b:
if b & 1:
r ^= a
a <<= 1
b >>= 1
return r
def pdivmod(a, b):
q, db = 0, pdeg(b)
while a and pdeg(a) >= db:
s = pdeg(a) - db
q |= 1 << s
a ^= b << s
return q, a
def pdivides(a, b):
return pdivmod(b, a)[1] == 0
def ppow(a, n):
r = 1
for _ in range(n):
r = pmul(r, a)
return r
IRR = {}
for _d in range(1, 11):
_small = [g for e in range(1, _d // 2 + 1) for g in IRR[e]]
IRR[_d] = [f for f in range(1 << _d, 1 << (_d + 1))
if not any(pdivides(g, f) for g in _small)]
def pfactor(f):
out, d = {}, 1
while 2 * d <= pdeg(f):
for g in IRR[d]:
while pdivides(g, f):
f = pdivmod(f, g)[0]
out[g] = out.get(g, 0) + 1
d += 1
if pdeg(f) > 0:
out[f] = out.get(f, 0) + 1
return out
def lam_f2_pp(d, a):
return ((1 << d) - 1) << (a - 1).bit_length()
def lam_f2(f):
L = 1
for g, e in pfactor(f).items():
L = lcm(L, lam_f2_pp(pdeg(g), e))
return L
def wall_f2(L):
"""W(L) over F_2[x] by the closed form."""
A = 1 << v2(L)
w, d = 1, 1
while (1 << d) - 1 <= L:
if L % ((1 << d) - 1) == 0:
for g in IRR[d]:
w = pmul(w, ppow(g, A))
d += 1
return w
def section_b_f2():
section("B THE WALL over F_2[x]")
bad = tested = 0
for d in range(1, 5):
for g in IRR[d]:
for a in range(1, 6):
N = ppow(g, a)
if pdeg(N) > 9:
continue
best = 1
for u in range(1, 1 << pdeg(N)):
if pdivides(g, u):
continue
o, y = 1, u
while y != 1:
y = pdivmod(pmul(y, u), N)[1]
o += 1
best = lcm(best, o)
tested += 1
bad += best != lam_f2_pp(d, a)
control("B2 control: lambda(g^a) = (2^d - 1) 2^ceil(log2 a) at every "
"g^a of degree <= 9, deg g <= 4, a <= 5", bad == 0,
f"{tested} tested, {bad} off")
lam_of = {1: 1}
for f in range(2, 1 << 11):
lam_of[f] = lam_f2(f)
tested = bad = lat = 0
for L in range(1, 65):
W = wall_f2(L)
if pdeg(W) > 10:
continue
members = [f for f, l in lam_of.items() if L % l == 0]
tested += 1
bad += max(members, key=lambda f: (pdeg(f), f)) != W
lat += sum(not pdivides(f, W) for f in members)
check("B2 the closed form of W(L) is the brute maximum over every "
"monic of degree <= 10", bad == 0 and tested == 44,
f"{tested} values of L, {bad} off")
check("B2 every state with lambda | L divides W(L)", lat == 0,
f"{lat} failures")
bad = cases = 0
for n in range(1, 5):
for v in range(0, 3):
L = ((1 << n) - 1) << v
cases += 1
bad += wall_f2(L) != ppow((1 << (1 << n)) ^ 2, 1 << v)
check("B2 W((2^n - 1) 2^v) = (x^(2^n) + x)^(2^v), n <= 4, v <= 2",
bad == 0, f"{cases} (n, v), {bad} off")
# ------------------------------------------------------------- section C
FULL_SEED = 961440481
def is_prime_mr(n):
"""Miller-Rabin at the primes to 41, deterministic below 3.3 * 10^24."""
if n < 2:
return False
d, s = n - 1, 0
while d % 2 == 0:
d, s = d // 2, s + 1
for b in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41):
if n % b == 0:
return n == b
x = pow(b, d, n)
if x in (1, n - 1):
continue
for _ in range(s - 1):
x = x * x % n
if x == n - 1:
break
else:
return False
return True
def unit_exponent(M):
L = 1
for a in range(1, M):
if gcd(a, M) != 1:
continue
o, y = 1, a
while y != 1:
y = y * a % M
o += 1
L = lcm(L, o)
return L
def brute_least(mf):
L = value(lam(mf))
m = 2
while value(lam(merge_add(mf, factor(m)))) == L:
m += 1
return m
def blocker(q):
"""The least prime P = 1 (mod B), P != 1 (mod q), P != q."""
B = 1
for p in PRIMES:
if p > q:
break
B = lcm(B, p - 1)
for r in PRIMES:
if r >= q:
break
c = 0
while r ** (c + 2) <= q:
c += 1
B = lcm(B, r ** c)
P = B + 1
while P % q == 1 or P == q or not is_prime(P):
P += B
return P
def cold_opening(q, mf, lamf):
"""The least q^r raising lambda at a state prime to q, read off
lambda itself, never off least_move's formula."""
r = 1
while value(lam({**mf, q: r})) == value(lamf):
r += 1
return q ** r
def section_c():
section("C THE LOCK: the door menu and the prime dynamics locks onto")
bad_b = bad_d = 0
kinds = {}
cold2 = cold3 = 10 ** 9
for M in range(1, 20001):
mf = factor(M) if M > 1 else {}
lamf = lam(mf)
q, best, moves = menu(mf, lamf)
bad_b += brute_least(mf) != best
bad_d += len(set(moves.values())) != len(moves)
k = kind(q, mf, lamf)
kinds[k] = kinds.get(k, 0) + 1
if M >= 3 and M % 2:
cold2 = min(cold2, cold_opening(2, mf, lamf))
if M >= 3 and M % 3:
cold3 = min(cold3, cold_opening(3, mf, lamf))
print(" the least move's kind over M <= 20000:", kinds)
check("C1 the door menu is the brute least lambda-raising m",
bad_b == 0, f"20000 states, {bad_b} off")
print(f" least moves pairwise distinct at {20000 - bad_d} of 20000 "
"states ((7): powers of distinct primes)")
check("C1 no least move below 20000 is an opening at full price",
"full" not in kinds)
print(f" cold-opening minima, 3 <= M <= 20000: 2-opening {cold2}, "
f"3-opening {cold3}")
check("C4 the cold openings: 2 opens at >= 16, 3 at >= 9, both attained",
(cold2, cold3) == (16, 9))
check("C4 every 5 <= q <= 47 opens at q from lambda = 2",
all(value(lam({3: 1, q: 1})) != value(lam({3: 1}))
for q in PRIMES[2:15]))
bad, over, wmax, wseed = 0, 0, 0, None
for seed in range(1, 2001):
sf = factor(seed) if seed > 1 else {}
ghosts, lock, ok, _ = walk_to_lock(sf)
lam0 = lam(sf)
ok = (ok and lock is not None and ghosts == sorted(set(ghosts))
and all(lam0.get(g, 0) > 0 for g in ghosts))
bad += not ok
over += len(ghosts) > omega_odd(lam0)
if len(ghosts) > wmax:
wmax, wseed = len(ghosts), seed
print(f" largest wander below 2000: {wmax}, first at seed {wseed}; "
f"past omega_odd(lambda(seed)) at {over} seeds (the ghosts being "
"distinct odd primes dividing it)")
check("C2 the first non-ghost pick locks, 30 more steps stay locked, "
"the invariant holds, ghosts increase and divide lambda(seed)",
bad == 0, f"2000 seeds, {bad} off")
check("C2 the largest wander below 2000 is at most 3", wmax <= 3)
for seed, g_want, l_want in ((11, [5], 7), (71, [5, 7], 17),
(20231, [5, 7, 17], 19)):
ghosts, lock, ok, _ = walk_to_lock(factor(seed), extra=3)
print(f" seed {seed}: ghosts {ghosts}, lock {lock}")
check(f"C3 seed {seed} ghosts {g_want} and locks {l_want}",
ghosts == g_want and lock == l_want and ok)
check("C3 20231 is prime and 20230 = 2 x 5 x 7 x 17^2",
is_prime(20231) and factor(20230) == {2: 1, 5: 1, 7: 1, 17: 2})
mf, states = {}, []
for _ in range(3):
q, cost, _ = menu(mf, lam(mf))
mf = step(mf, q, cost)
states.append(value(mf))
check("C3 seed 1 walks 3, 9, 27", states == [3, 9, 27], str(states))
P = FULL_SEED
mf = {P: 1}
lamf = lam(mf)
q, cost, _ = menu(mf, lamf)
k = kind(q, mf, lamf)
ghosts, lock, ok, _ = walk_to_lock(mf, extra=5)
print(f" seed {P}: least move {q}^r = {cost}, kind {k}; lock {lock}")
check("C3 the full-price specimen: the prime seed 961440481 opens 3 "
"at 81, no prime = 1 mod 27 lies below 81, and it locks at 3",
is_prime_mr(P) and lamf.get(3) == 2 and (q, cost, k) ==
(3, 81, "full") and not any(is_prime(n) for n in (28, 55))
and lock == 3 and not ghosts and ok)
ghosts, lock, ok2, _ = walk_to_lock({2: 1}, extra=5)
ok_all = lock == 2 and not ghosts and ok2
blockers = {}
for q in PRIMES[1:15]:
P = blocker(q)
ghosts, lock, ok, _ = walk_to_lock({q: 1, P: 1}, extra=5)
blockers[q] = P
ok_all = ok_all and lock == q and not ghosts and ok
print(" blockers P by q:", blockers)
check("C5 every prime q <= 47 is its blocker seed's lock, wander 0",
ok_all)
check("C5 the blockers are 5; 13, 13; 61, 61; 241; 2161; 23761; "
"55441 five times; 1275121", blockers == {
3: 5, 5: 13, 7: 13, 11: 61, 13: 61, 17: 241, 19: 2161,
23: 23761, 29: 55441, 31: 55441, 37: 55441, 41: 55441,
43: 55441, 47: 1275121})
# ------------------------------------------------------------- section D
def section_d():
section("D THE TWO-ADIC PRICES: the real column at 2 and a counterfeit")
bad_r = bad_c = bad_3 = 0
floor_r = floor_c = 10 ** 9
for M in range(3, 20001, 2):
mf = factor(M)
lamf = lam(mf)
v = lamf.get(2, 0)
dr = least_move(2, 0, lamf)
dc = least_move(2, 0, lamf, counterfeit=True)
bad_r += dr != 2 ** (v + 3)
bad_c += dc != 2 ** (v + 2)
floor_r, floor_c = min(floor_r, dr), min(floor_c, dc)
for M in range(3, 20001):
if M % 3:
mf = factor(M)
bad_3 += (least_move(3, 0, lam(mf))
!= least_move(3, 0, lam(mf, True), True))
check("D1 real 2-door v+3, counterfeit v+2, at every odd 3 <= M <= 20000",
bad_r == bad_c == 0, f"{bad_r} and {bad_c} off")
check("D1 price floors 16 real and 8 counterfeit",
(floor_r, floor_c) == (16, 8), f"{floor_r}, {floor_c}")
check("D1 the 3-door is the same in both worlds at every "
"3 <= M <= 20000 prime to 3, even M included", bad_3 == 0,
f"{bad_3} off")
ok = True
for v in range(1, 9):
for cf, want_m, want_rise in ((False, [1, 2, 3], [1, 2, 1]),
(True, [1], [1])):
dr = 2 ** (v + 2) if cf else 2 ** (v + 3)
ms = [m for m in range(1, 64) if m * 2 ** (v + 1) + 1 < dr]
rises = [v2(m * 2 ** (v + 1)) - v for m in ms]
ok = ok and ms == want_m and rises == want_rise
for p in PRIMES[1:15]:
for v in range(1, 5):
ms = [m for m in range(1, 2 * p)
if m * p ** (v + 1) + 1 < p ** (v + 2)]
rises = []
for m in ms:
n, r = m * p ** (v + 1), 0
while n % p == 0:
n //= p
r += 1
rises.append(r - v)
ok = ok and ms == list(range(1, p)) and set(rises) == {1}
print(f" carriers under the full-price opening, {{1, 2, 3}} rising "
f"{{1, 2, 1}} real, {{1}} rising 1 counterfeit, 1..p-1 rising 1 "
f"at odd p <= 47: {ok} (arithmetic)")
walks = []
for cf in (False, True):
mf, pays = {2: 2}, []
for _ in range(8):
q, cost, _ = menu(mf, lam(mf, cf), cf)
pays.append(cost)
mf = step(mf, q, cost)
walks.append(pays)
print(" seed 4 pays, real:", walks[0], " counterfeit:", walks[1])
check("D1 the walk from 4: real [4, 2, 2, ...], counterfeit "
"[2, 2, 2, ...]", walks == [[4] + [2] * 7, [2] * 8])
pp = [2 ** k + 1 for k in range(1, 21) if len(factor(2 ** k + 1)) == 1]
print(" prime powers among 2^k + 1, k <= 20:", pp)
check("D1 they are 3, 5, 9, 17, 257, 65537",
pp == [3, 5, 9, 17, 257, 65537])
def section_control():
section("POSITIVE CONTROL: lambda, before any verdict reads it")
bad = sum(unit_exponent(M) != lam_int(M) for M in range(2, 301))
control("C1 control: the lambda formula is the unit group's exponent, "
"M <= 300", bad == 0, f"299 moduli, {bad} off")
def main():
section_control()
section_a()
section_b_z()
section_b_f2()
section_c()
section_d()
print()
print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed")
raise SystemExit(0 if all(CHECKS) else 1)
if __name__ == "__main__":
main()