headroom.py
Checks: HEADROOM: The headroom property; HEADROOM: The ledger theorem; HEADROOM: The premium in closed form theorem; HEADROOM: Silence lands in a blind class theorem; rule; HEADROOM: The closure theorem; HEADROOM: The non-divisor bound theorem; observation; HEADROOM: No blindness is permanent theorem; observation; HEADROOM: The watcher's guaranteed blindness theorem; HEADROOM: The blind-density theorem theorem; HEADROOM: The least resolver is unbounded theorem.
Cited on: HEADROOM.
To run it: save headroom.py, with growth.py beside it; standard library only.
"""headroom.py -- what a probe learns of a grown state by offering it
moves: the headroom xi(M) = W(lambda(M))/M, what a move spends of it and
what it opens, the closure underneath, what it costs to tell apart two
states the reading merges, and the density of the probe's blind classes.
QUESTION. growth.py grows Z/M by the cheapest move a demand admits. The
demands that read lambda (the transparency demand and its complement)
answer one bit per offered move m: does lambda(Mm) equal lambda(M)?
What does that family of answers see of a state, how does the thing it
sees move under a move, and how coarse is it: which states does it
merge, what does it cost to split them, and how many are merged?
THE OBJECT. lambda is the Carmichael function and W(L) the wall, the
largest N with lambda(N) | L (growth.py, where the wall is Adams'
number). The HEADROOM of a state M is xi(M) = W(lambda(M))/M, an
integer since lambda(M) | lambda(M). A move m sends M to Mm; it is
TRANSPARENT when lambda(Mm) = lambda(M). The PROBE is the family of
lambda-reading demands; its READING of M is xi(M). Two distinct states
with one reading are a BLIND PAIR, and the states sharing a reading,
when two or more do, a BLIND CLASS. Along a move, the WALL GAIN is
Gamma(M, m) = W(lambda(Mm))/W(lambda(M)), the BURN is gcd(m, xi(M)),
the UNPAID PART is u(M, m) = m/gcd(m, xi(M)), and the PREMIUM is
G(M, m) = Gamma(M, m)/u(M, m). A move m RESOLVES a blind pair
(M1, M2) when xi(M1 m) != xi(M2 m); R is the set of resolvers;
kappa(xi) is the least integer >= 2 not dividing xi.
THE ARGUMENT (written before the engine).
(1) THE HEADROOM. {M : lambda(M) | L} is closed under lcm, so every
member divides W(L). lambda(M) | lambda(Mm) always; so m is
transparent iff Mm | W(lambda(M)) iff m | xi(M). A lambda-reading
demand's whole response to M is the indicator of the divisors of
xi(M): the reading is one number. By the wall's closed form, at
an odd prime l with (l - 1) | lambda (a DOOR of lambda),
v_l(xi) = v_l(lambda) + 1 - v_l(M); at a non-door odd l, v_l(xi)
= v_l(M) = 0 (l | M forces (l - 1) | lambda); at 2, v_2(xi) =
v_2(lambda) + 2 - v_2(M) at even lambda and 1 - v_2(M) at odd.
Neither the reading nor the support determines the other: 855 and
2565 share the support {3, 5, 19} and read 161616 and 53872; 10
and 11 read 24 on the supports {2, 5} and {11}.
(2) THE LEDGER. xi(Mm) = xi(M) Gamma/m. Mm divides its own wall
Gamma W(lambda(M)) = Gamma xi(M) M, so m | Gamma xi; prime by
prime, v_l(u) = max(0, v_l(m) - v_l(xi)) <= v_l(Gamma). So G is
an integer and
xi(Mm) = (xi(M)/gcd(m, xi(M))) G(M, m):
the burn is truncated subtraction in the exponents, and a move
never destroys more headroom than it spends. SPLITTING: Gamma
telescopes, Gamma(M, ab) = Gamma(M, a) Gamma(Ma, b), so
G(M, a) G(Ma, b) = G(M, ab) k, k = u(M, ab)/(u(M, a) u(Ma, b)),
and k is an integer: with x = v_l(xi(M)), a_l, b_l the
exponents and g_l = v_l(G(M, a)), v_l(xi(Ma)) = x - min(a_l, x) +
g_l, and min(a_l + b_l, x) <= min(a_l, x) + min(b_l, x -
min(a_l, x) + g_l) in both cases a_l >= x and a_l < x. Equality
holds iff at every l | b, g_l = 0 or b_l <= x - a_l. So a split
move never undercounts the premium, and of the four parts only
the wall gain is a ratio of one function at the two endpoints.
(3) THE PREMIUM IN CLOSED FORM. lambda(Mm) = lcm(lambda(M),
lambda(l^(c_l + e_l)) : l | m), c_l = v_l(M), e_l = v_l(m), and
c_l = v_l(W(lambda(M))) - v_l(xi(M)), whose first term is a
function of lambda(M). So G(M, m) is a function of lambda(M), m
and the exponents v_l(xi(M)) at the primes l of m, and of
nothing else; at a move prime to M every c_l is 0 and G is a
function of lambda(M) and m. The exponents are needed: lambda(3) =
lambda(8) = 2, and m = 3 has premium 7 at 3 (xi = 8) and 1 at 8
(xi = 3). The primes of a move interact: at lambda = 1, 5 opens
the doors 3, 5, 7 opens 3, 7, and 35 opens 3, 5, 7 and 13, since
13 - 1 = 12 takes its 4 from lambda(5) and its 3 from lambda(7).
On a prime q not dividing M the wall gain's odd part is the
COHORT (odd p newly doors of lambda' = lambda(Mq), each at
v_p(lambda') + 1) times the BUMPS at the old odd doors, each at
v_p(lambda') - v_p(lambda). From the state 1 the cohort of q is
{p odd prime : (p - 1) | (q - 1)}.
(4) SILENCE. A prime q not dividing M with (q - 1) not dividing
lambda = lambda(M) is SILENT at M when G(M, q) = 1: the reading
does not move while lambda does. Then u = q and W(L') = q W(lambda),
L' = lcm(lambda, q - 1). Every door of L' other than q is a door
of lambda at the same exponent, and v_2(L') = v_2(lambda); so
every door p != q of q - 1 has (p - 1) | g = gcd(q - 1, lambda)
and v_p(q - 1) <= v_p(lambda), whence v_p(q - 1) = v_p(g), and
v_2(q - 1) = v_2(g).
Hence W(q - 1) = q W(g): every prime silent at M lies in the
blind class xi = W(g). At lambda = 2 silence is exactly membership
of the class xi = 24. At odd lambda nothing is silent: W's 2-part
is 2 and a prime q > 2 sends it to at least 8. Conversely every
prime q = 1 (mod lambda) with xi(q) = W(lambda), q not dividing
M, is silent at M. Off that class lie the silent q with lambda
not dividing q - 1: since lambda(W(lambda)) = lambda at lambda =
lambda(M) ((5), idempotence) and lambda(W(g)) | g, W(g) !=
W(lambda) at every proper divisor g, so they read another class.
(5) THE CLOSURE. M -> M* = W(lambda(M)) is inflationary (M | M*),
monotone (M | M' gives lambda(M) | lambda(M'), and W is monotone
under divisibility) and idempotent (lambda(M*) = lambda(M): one
way by M | M*, the other by the definition of W). The fixed
points are the TOMBSTONES, xi = 1, and every W(L) is one. A
tombstone above 2 is divisible by 24 (lambda even, so 2^3 and the
door 3); 2 is the only tombstone with odd lambda. The tombstones
are one infinite blind class: W(2^k) >= 2^(k+2) at k >= 1.
(6) BLINDNESS AND ITS CURE. A blind pair has different lambdas, since
M = W(lambda)/xi. A divisor d of xi keeps the pair blind (both
read xi/d). RESOLUTION CRITERION: d resolves iff the wall gains
differ, since xi(M_i d) = xi Gamma_i/d. So every resolver is a
non-divisor of xi, and the least one is at least kappa(xi), a
prime power (a least non-divisor p^a r, r > 1 prime to p, has
both parts dividing xi, hence their product). NO PERMANENT
BLINDNESS: a prime q = 1 (mod lcm(lambda_1, lambda_2)) not
dividing M_1 M_2 (Dirichlet) sends both lambdas to q - 1; the
walls agree and the readings W(q - 1)/(M_i q) differ. The next
reading is no function of the reading and the move: 2 and 24
read 1, and 5 sends them to 24 and 2. On multipliers d prime to
M_1 M_2, Gamma_i depends on d only through lambda(d), so R is a
union of lambda-fibres there. A WATCHER sees the readings at
M_i d for the divisors d of a move it is handed; the moves that
keep a pair blind at every such reading are those whose divisors
all miss R, a divisor-closed family containing every divisor of
xi, so a pair survives at least tau(xi) - 1 moves with
certainty. A move blind at its end but split inside (9 and 513,
reading 56, under 57 = 3 19, split at 3) is a resolver whose
multiple is not one: R is not an up-set.
(7) THE BLIND-DENSITY THEOREM. For every even lambda, the primes
q = 1 (mod lambda) with xi(q) = W(lambda) have a positive
relative density among the primes. Within that progression the
conditions read v_p(q - 1) <= v_p(lambda) at every door p of
lambda and (p - 1) not dividing q - 1 at every odd prime p off
them, p != q: all DECREASING events in the valuation vector
(v_l(q - 1))_l. Under the prime measure the coordinates are
independent (Dirichlet: the density of the residue class 1 mod
D is prod 1/phi(l^a) over l^a || D), each a chain, so Harris's
inequality gives P(E and F) >= P(E) P(F) for decreasing E, F.
Write delta_T for the relative density, inside the progression,
of the conditions at the doors and at the p <= T, a residue
condition, and eps(T) for the upper density among all primes of
the q with (p - 1) | (q - 1) for some prime p > T, p != q; inside
the progression that event has relative upper density at most
phi(lambda) eps(T). The class share lies in [delta_T -
phi(lambda) eps(T), delta_T], and delta_T' >= delta_T (1 -
phi(lambda) eps(T)) for T' > T. So if eps(T) -> 0 the class has
density lim delta_T > 0. eps(T) << (log T)^(-c), uniformly in
x, is Theorem 3 of Luca, Pizarro-Madariaga and Pomerance, "On
the counting function of irregular primes", Indag. Math. 26
(2015) 147-161, its two parameters at 1 and -1, and the
lambda = 2 case of
the theorem is Theorem 3 of Pomerance and Wagstaff, "The
denominators of the Bernoulli numbers" (Acta Arith., doi
10.4064/aa210601-16-11; arXiv:2105.13252) for the denominator
6q, both read
in full;
theirs never caps a valuation, so the class at a general lambda
is their set cut by a residue condition. The record's own
derivation of the tail, redundant with the 2015 theorem, is
Erdos and Wagstaff's Theorem 2 carried to the shifted primes:
their three classes
for q - 1 = (p - 1) n, against loglog p, with every count by
Pollack's Theorem 1.1 ("Nonnegative multiplicative functions on
sifted sets, and the square roots of -1 modulo shifted primes",
Glasgow Math. J. 62 (2020) 187-199; a Shiu bound over a sifted
set) applied
to z^Omega on {n : dn + 1 prime}. The Chernoff exponents are
d1 = 1/3 - (2/3) log(3/2) = 0.0630 for the "few factors" classes
and eta = (7/6) log(7/6) - 1/6 = 0.0132 for the third, whose
union over t_i = exp(i^(2/eta)) costs a square root, so eps(T)
<< (log T)^(-eta/2). The proof needs only d1 > 0.
THE TAIL, step by step. q - 1 = (p - 1) n with p > T prime,
p != q, n >= 2; L = loglog p; Omega_p(n) counts the prime
factors of n below p with multiplicity. Every q counted by
eps(T) falls in one of three classes. (1) Omega(p - 1) < (2/3)
L. (2) Omega_p(n) < (2/3) L. (3) both at least (2/3) L, whence
Omega_p(q - 1) >= (4/3) L, since every prime of p - 1 is below
p. The tool is Pollack's Theorem 1.1: f multiplicative with
f(l^v) <= A^v and f(n) <<_e n^e, E_l a union of at most k
nonzero classes mod l for each prime l <= x, S the integers in
no E_l; then the sum of f over S in (x - y, x] is << (y/log x)
exp(sum_(l <= x) (f(l) - nu(l))/l) for x^a < y <= x. For the
set {n : dn + 1 prime} take E_l = {-1/d} at l not dividing d:
exp(-sum nu(l)/l) is the Brun-Titchmarsh 1/log x, and the l | d
return at most d/phi(d). The Chernoff step takes f =
z^Omega_p, z < 1 for "few factors", z > 1 for "many".
(1) z = 2/3 on {n <= y : n + 1 prime}: #{p <= y : Omega(p - 1)
< (2/3) loglog y} << y/(log y)^(1 + d1). Each such p
carries pi(x; p - 1, 1) << x/(phi(p - 1) log(x/p)) primes
q. Summed over p <= sqrt(x) by parts this is << pi(x)
(loglog T)/(log T)^d1; over p > sqrt(x), dyadically in
x/p, it is << pi(x) (loglog x)^2/(log x)^d1. Both vanish.
(2) p <= sqrt(x), d = p - 1, X = x/d: z = 2/3 on {n <= X :
dn + 1 prime} gives << (d/phi(d)) (X/log X) (log p)^(-d1)
class-(2) primes, and the sum over p > T of 1/(phi(p - 1)
(log p)^d1) tends to 0. For p > sqrt(x), n < sqrt(x) < p,
so Omega(n) < (2/3) loglog x; the same tool with f = 1 on
the two conditions p prime and n(p - 1) + 1 prime bounds
each n's count by << (n/phi(n)) x/(n log^2 x), and the sum
of 1/phi(n) over n <= sqrt(x) with Omega(n) < (2/3) loglog
x is << (log x)^(1 - d1): total << pi(x)/(log x)^d1.
(3) z = 7/6 on {n <= x : n + 1 prime} gives #{q <= x :
Omega_t(q - 1) >= (7/6) loglog t} << pi(x) (log t)^(-eta),
uniformly in t <= x. With t_i = exp(i^(2/eta)), a q with
Omega_p(q - 1) >= (4/3) loglog p for some p in
[t_(i-1), t_i) has Omega_(t_i)(q - 1) >= (7/6) loglog t_i
once i is large, and sum over t_i > T of (log t_i)^(-eta)
= sum i^(-2) is << (log T)^(-eta/2).
This is Erdos and Wagstaff's proof of their Theorem 2 (Lemmas
1 to 4) with each integer count replaced by its shifted-prime
count. The dyadic sum in (1) costs a second loglog x, which
changes nothing.
COROLLARIES. The silent set at every even lambda has positive
density ((4), converse). Every reading W(lambda), lambda even,
hosts infinitely many blind pairs, so the least resolver is
unbounded: along L_n = lcm(1, ..., n) every prime r <= n + 1 is
a door (2 by the wall's 2-part) at an exponent with
r^(v_r(W) + 1) > n + 1, so kappa(W(L_n)) > n + 1.
The class xi = 24 is a Bernoulli class: by von Staudt-Clausen
the denominator of B_(q-1) is the product of the p with
(p - 1) | (q - 1), so for q >= 11 the class is exactly the primes
with denom(B_(q-1)) = 6q; 5 and 7 have that denominator and read
48 and 72.
DESIGN. Standard library; one process. growth.py supplies value,
lambda on a factorization and at a prime power, a Miller-Rabin test,
its prime list, merge_max, the Bernoulli numbers and the wall, which
C2 alone calls, beside wall_f, this file's copy of the wall formula,
which C2 and every other wall read use. fac factors through a
smallest-prime-factor sieve to 10^7, which also backs is_prime and
the main prime list; P5 reads growth's own primes, and lambda factors
p - 1 with growth's factor.
C POSITIVE CONTROLS. C1 lambda against the unit group's exponent
at every M <= 300. C2 the wall formula against the brute largest
M <= 2 W(L) with lambda(M) | L, even L <= 24: a formula missing a
door p of the true wall leaves the admissible (p/2^i) W(L), 2^i in
[p/2, p) dividing W(L), inside the search. C1 and C2 run before any
verdict and stop the
run if either fails. C3 the exact
product-measure density of a residue condition against its prime
count below 10^7 (delta_T at T = 7, known as 1/4: q = 3 mod 4 and
q != 1 mod 3), its own check, run as D2's first row and read before
D2's.
H the headroom. H1 m transparent iff m | xi(M), every M < 400, m <
200. H2 the exponent formula of xi at 2, at every door of lambda
and at every prime of M or xi, every M < 2000, and v_l(M) = 0 at
every odd non-door l among them, each door's exponent read against
H2's own loop over the divisors of L, which shares divisors_f and
is_prime with wall_f, beside a direct test L % (p - 1) == 0 at the
primes of M and xi. A door wall_f drops fails H1 at every door
probed below 400 (37, 199, 211, 241, 337, 397) but not at 401, and
H2 when its p - 1 divides some lambda(M), M < 2000 (401 fails it,
2003 does not). C2 reads both wall_f and growth.wall, and catches a
door either drops only among 3, 5, 7, 11, 13, 17, 19 and 23, the
doors its even L <= 24 reach. H3 the two witnesses that neither
determines the other.
L the ledger. L1 G an integer, M < 400, m < 60; the identity
xi(Mm) = (xi/gcd(m, xi)) G then holds by the definitions. L2 the
splitting inequality and its equality condition, every split
m = ab of those moves, and a split whose unpaid parts do not
telescope: from 1, u(12) = 6 against u(3) u(4 at 3) = 3.
P the premium. P1 G recomputed from (lambda(M), m, v_l(xi) at
l | m) alone equals G, the same range. P2 the coprime case a
function of lambda(M) and m (every pair of states M < 1500 with
one lambda, moves m < 60 prime to both). P3 the 3/8 witness. P4
the premiums 4, 24, 8 of 3, 5, 15 from 1, and the doors 5, 7 and
35 open from the states 1 and 2. P5 the cohort-and-bump
factorization on every prime q < 200 not dividing M < 400, read
off wall_f's own factors, so it tests lambda(M) | lambda(Mq) and
the bookkeeping.
S silence. S1 every silent q < 10^5 at 25 even lambda lies in the
class xi = W(gcd(q - 1, lambda)). At lambda = 2 the silent primes
are the class xi = 24 by the definitions (W(q - 1) = 24q is
xi(q) = 24): both counts printed, not checked. S3 no prime
q < 10^4 is silent at an odd lambda (states 1, 2). S4 the
converse at lambda = 4, 6, 8, 12: every q = 1 (mod lambda),
q < 10^5, with xi(q) = W(lambda) is silent at a state of that
lambda. Printed beside S1: at each lambda, the silent count, the
count off the class (lambda not dividing q - 1), the least off;
the off ones reading xi = W(lambda) (predicted none); the lambda
> 2 where the off part is not the majority. Added after the
first run: S5 asserts that majority at every lambda > 2, no off one
reading W(lambda), and lambda(W(lambda)) = lambda at every swept
lambda; none off at lambda = 2 is no check, every odd q being 1
mod 2.
W the closure. W1 inflationary, monotone, idempotent over
M <= 3000 (monotone on every divisor pair). W2 every tombstone
W(lambda(M)) for M < 10^5 is a fixed point, divisible by 24 above
2, and 2 is the only one of odd lambda; "every W(L) is one" is so
checked at the L that lambda takes below 10^5 and at L = 2^k.
W3 W(2^k) is a tombstone and at least 2^(k+2), 1 <= k <= 40.
R resolution: the blind pairs among the states 2..1499 counted,
each check run at one representative pair per blind class. That
blind pairs have
different lambdas, and the criterion, hold by the definitions
(M = W(lambda)/xi; xi(M_i d) = xi Gamma_i/d) and are not checked:
a check of either computes the same quantity twice. R3 least resolver
>= kappa(xi), kappa a prime power; the share attaining it
printed. The Dirichlet resolver for each representative pair, the
least prime q found, the largest printed; that it splits holds by
construction (lambda(aq) = q - 1, xi(aq) = W(q - 1)/(aq)). R5 the
2/24 witness. R6 R a union of lambda-fibres on d < 200 prime to
both, the fibres with two or more d counted. R7 the watcher:
every divisor of xi keeps the pair blind at every internal
reading; the 9/513/57 witness.
D the density. D1 the Bernoulli class: over primes 11 <= q < 10^6,
xi(q) = 24 iff the von Staudt-Clausen product of q - 1 is 6q;
B_2..B_40 exact against that product; 5 and 7 as stated. D2 delta_T exact
at T = 7, 11, 23, 47 against the empirical share among the
primes in (T, 10^7]. D3 Harris exactly: delta at the primes 5
.. 47, off the doors of 2, is at least the product of the
densities at 5 .. 23 and at 29 .. 47, in exact rationals. D4 the class
conditions at lambda = 4, 6, 8, 12, 24: class membership within
q = 1 (mod lambda), q < 10^6, equals the decreasing-event
reading. D5 the unboundedness: kappa(W(L_n)) > n + 1 for n <= 30,
and at each even L_n, n = 2..8, two primes q with xi(q) = W(L_n),
found by search. d1 and eta printed.
PREDICTIONS, fixed before the run.
Every identity check reads zero violations: C1, C2, H1-H3, L1, L2,
P1-P5, S1-S4, W1-W3, R3-R7, D1, D3, D4, D5. C3 and D2: exact and
empirical within 2 10^-3 (the binomial sd at 6.6 10^5 primes is
at most 5.3 10^-4, at T = 7, and the primes up to T are excluded). R3: the share
attaining kappa near 0.94, as an earlier run read over 96 classes.
D2's delta_T at T = 7, 11, 23, 47: 0.25, 0.1875, 0.16875, 0.16108, an
earlier run's exact values. D5: a pair of class members found at every
even lcm, n <= 8, below 10^9. d1, eta: 0.0630, 0.0132.
A KILL is any identity violation, which kills the claim it tests; a
D2 gap above 2 10^-3, which kills the measure the density proof runs
on; a D3 inequality failing, which kills the positivity step. A
control out of its band voids the verdicts that lean on it. An
earlier run's figure not reproduced with the identities green is
a definition to read, not a kill.
THE ARGUMENT'S CORRECTION, made on the first run and before any
finding was written. (7) read the class of W(lambda) inside q = 1
(mod lambda) as the decreasing events alone. D4's first run printed 3
violations, q = 5, 7, 13 at lambda = 4, 6, 12: there q = lambda + 1 is
itself a door of lambda, so xi(q) = W(lambda)/q. The reading holds for
every q != lambda + 1, one prime per lambda, and the density is
untouched. C3 is run as D2's first row (T = 7).
FINDINGS. 31/31 checks PASS, no kill, every prediction met but S2 and
R4, which hold by construction and are prints.
C lambda is the unit exponent at every M <= 300; the wall formula
agrees with brute at every even L <= 24.
H transparent iff m | xi(M) at every M < 400, m < 200; the exponent
formula at every prime of every M < 2000; 855 and 2565 on the
support {3, 5, 19} read 161616 and 53872, 10 and 11 both read 24.
L G an integer at 23142 moves; 52668 splits, the inequality at
all of them and the equality condition exact, 51029 of them
(0.969) with equality; from 1, 12 = 3 4 leaves unpaid 6 against
3 then 1, the premiums 4 1 against 2.
P the closed form at every move of L; the coprime premium a
function of lambda and m over 8321 cells; 3 pays 7 at 3 and 1 at
8; from 1, 3, 5 and 15 pay 4, 24 and 8; from 1 and from 2, 5
opens {3, 5}, 7 opens {3, 7} and 35 opens {3, 5, 7, 13}; the
cohort-and-bump form at every prime q < 200.
S 19326 silent primes below 10^5 at 25 even lambda, every one in
the class W(gcd(q - 1, lambda)); at lambda = 2, 1133 silent and
1133 in the class 24, the same set; nothing silent at odd lambda;
1212 class members silent at lambda = 4, 6, 8, 12. Off the class:
0 at lambda = 2; 820 of 1262 at 4 (least 23), 588 of 1066 at 6
(59), 914 of 1049 at 12 (83), 449 of 456 at 60 (839), all 149 at
180; the majority at all 24 lambda > 2, the least share at 6; no
off one reads W(lambda).
W the closure's three laws at M <= 3000; 15293 tombstones reached
from M < 10^5, each fixed, divisible by 24 above 2, 2 the only
one with odd lambda; W(2^k) fixed and at least 2^(k+2), 1 <= k <= 40.
R 96 blind classes, 4542 blind pairs among the states 2..1499; the
least resolver at least kappa at every class and equal to it at
90 of 96 (0.938); the Dirichlet prime, which splits by
construction, reaches 111827; 2 and 24 go to 24 and 2 under 5; 10 and
11 (reading 24, kappa 5) split first at 5, into 264 and 240; 4680
lambda-fibres, 1728 with two or more d, none split; every divisor of xi blind at every
class; 9 and 513 read 56 and 56 after 57, 1064 and 56 after 3.
D 8770 primes in [11, 10^6) in the class 24, the von Staudt-Clausen
product 6q at all of them, xi(5) = 48, xi(7) = 72; 137 has
denominator 30q and reads 480 against W(4) = 240. delta_T exact
against the primes in (T, 10^7]: 0.25000/0.25011, 0.18750/0.18755,
0.16875/0.16871, 0.16108/0.16100 at T = 7, 11, 23, 47. Harris
exactly: 0.161080 >= 0.111581. The decreasing-event reading at
127251 primes, the three q = lambda + 1 read as the exception.
kappa(W(lcm(1..n))) > n + 1 at every n <= 30, and two class
members at every even lcm through n = 8, the largest pair 437641
and 16545481 at W(840). d1 = 0.0630, eta = 0.0132, eps(T) <<
(log T)^(-0.0066).
Tiers: (1) a property; (2), (3), (4), (5), (6) theorems, verified in
the ranges printed, the resolution criterion a criterion, and the
least resolver meeting kappa at 90 of 96 classes an observation; (7)
a theorem whose proof rests on three outside results, written above,
and whose constant is not derived: the run reads delta_T, not its
limit; its corollaries are theorems.
RUN RECORD. python headroom.py: 33/33 checks, 7.5 to 8.7 s, peak 123 MB
under a 512 MB ceiling. After a code read: S2 and R4 held by
construction and are printed, not checked; C1 and C2 stop the run
(a C1 broken in a scratch copy printed CONTROL FAILED); the least
share off the class is printed. 31/31 checks in 7.6 s, peak commit
123.6 MB. After a second code read, C3 also checks delta_7 = 1/4: 31/31,
7.7 s, 123.2 MB. It replaces fifteen scripts for these
subjects, among them the two sieves that peaked at 454 and 452 MB: their
counts of decade ratios and loose shares were measurements and were
not carried.
"""
import os
import sys
import time
from array import array
from fractions import Fraction
from functools import lru_cache
from math import gcd, log
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import growth # noqa: E402
from growth import wall, value, lam # noqa: E402
CHECKS = []
def check(name, ok, detail=""):
CHECKS.append(bool(ok))
print(f" [{'PASS' if ok else 'FAIL'}] {name}"
+ (f" -- {detail}" if detail else ""))
def section(title):
print()
print("=" * 72)
print(title)
print("=" * 72)
# ------------------------------------------------------------ arithmetic
SPF_N = 10 ** 7
def spf_sieve(n):
"""Smallest prime factor below n + 1, 0 at the primes: the primes up
to sqrt(n) stamped from the largest down, so the least one wins."""
r = int(n ** 0.5) + 1
small = bytearray([1]) * (r + 1)
for i in range(2, int(r ** 0.5) + 1):
if small[i]:
small[i * i::i] = bytearray(len(small[i * i::i]))
s = array("i", [0]) * (n + 1)
for p in range(r, 1, -1):
if small[p] and p * p <= n:
k = len(range(p * p, n + 1, p))
s[p * p::p] = array("i", [p]) * k
return s
SPF = None
def fac(n):
"""Factor n by the sieve below SPF_N, by trial division above."""
if SPF is None or n > SPF_N:
return factor_big(n)
f = {}
while n > 1:
p = SPF[n] or n
f[p] = f.get(p, 0) + 1
n //= p
return f
def factor_big(n):
f = {}
p = 2
while p * p <= n:
while n % p == 0:
f[p] = f.get(p, 0) + 1
n //= p
p += 1 if p == 2 else 2
if n > 1:
f[n] = f.get(n, 0) + 1
return f
def is_prime(n):
if n < 2:
return False
if SPF is not None and n <= SPF_N:
return SPF[n] == 0
return growth.is_prime_mr(n)
def divisors_f(f):
ds = [1]
for p, e in f.items():
ds = [d * p ** k for d in ds for k in range(e + 1)]
return ds
@lru_cache(maxsize=None)
def lam_n(M):
return value(lam(fac(M))) if M > 1 else 1
def wall_f(lf):
"""W(L) from L's factorization, doors found among L's divisors."""
L = value(lf)
if L % 2:
return 2
w = 2 ** (lf[2] + 2)
for d in divisors_f(lf):
p = d + 1
if p > 2 and is_prime(p):
w *= p ** (lf.get(p, 0) + 1)
return w
@lru_cache(maxsize=None)
def W(L):
return wall_f(fac(L)) if L > 1 else 2
@lru_cache(maxsize=None)
def xi(M):
return W(lam_n(M)) // M
def gain(M, m):
return W(lam_n(M * m)) // W(lam_n(M))
def unpaid(M, m):
return m // gcd(m, xi(M))
def premium(M, m):
g, u = gain(M, m), unpaid(M, m)
assert g % u == 0
return g // u
def vp(n, p):
k = 0
while n % p == 0:
n //= p
k += 1
return k
def kappa(x):
k = 2
while x % k == 0:
k += 1
return k
def is_prime_power(n):
return len(factor_big(n)) == 1
def unit_exponent(M):
units = [a for a in range(1, M) if gcd(a, M) == 1] if M > 1 else [0]
e = 1
for a in units:
o, x = 1, a % M
while x != 1 % M:
x = x * a % M
o += 1
e = e * o // gcd(e, o)
return e
# ------------------------------------------------------------- controls
def section_c():
section("C POSITIVE CONTROLS")
bad = [M for M in range(1, 301) if lam_n(M) != unit_exponent(M)]
check("C1 lambda is the unit group's exponent, M <= 300", not bad,
f"{len(bad)} mismatches")
bad = []
for L in range(2, 25, 2):
top = 2 * W(L)
brute = max(M for M in range(1, top + 1) if L % lam_n(M) == 0)
if brute != W(L) or brute != wall(L):
bad.append(L)
check("C2 the wall formula against brute below twice it, even "
"L <= 24", not bad,
f"bad at {bad}")
# ------------------------------------------------------------ headroom
def section_h():
section("H THE HEADROOM")
bad = 0
for M in range(1, 400):
x, L = xi(M), lam_n(M)
for m in range(2, 200):
if (lam_n(M * m) == L) != (x % m == 0):
bad += 1
check("H1 m is transparent iff m | xi(M), M < 400, m < 200", bad == 0,
f"{bad} violations")
bad = 0
for M in range(1, 2000):
L, x = lam_n(M), xi(M)
mf, lf = fac(M), (fac(L) if L > 1 else {})
drs = {d + 1 for d in divisors_f(lf) if d > 1 and is_prime(d + 1)}
for p in set(mf) | set(fac(x)) | drs | {2}:
if p == 2:
want = (lf.get(2, 0) + 2 if L % 2 == 0 else 1) - mf.get(2, 0)
elif L % (p - 1) == 0:
want = lf.get(p, 0) + 1 - mf.get(p, 0)
else:
want = 0
bad += mf.get(p, 0) != 0
if vp(x, p) != want:
bad += 1
check("H2 the exponent formula for xi at 2, every door and every "
"prime of M or xi, M < 2000",
bad == 0, f"{bad} violations")
w = (set(fac(855)) == set(fac(2565)), xi(855), xi(2565), xi(10),
xi(11))
print(f" 855, 2565: one support {sorted(fac(855))}, xi {w[1]} and "
f"{w[2]}; 10, 11: xi {w[3]} and {w[4]}")
check("H3 neither support nor reading determines the other "
"(855/2565, 10/11)",
w == (True, 161616, 53872, 24, 24))
# -------------------------------------------------------------- ledger
def section_l():
section("L THE LEDGER")
bad = moves = 0
for M in range(1, 400):
x = xi(M)
for m in range(2, 60):
moves += 1
G = gain(M, m)
u = unpaid(M, m)
if G % u or xi(M * m) != x // gcd(m, x) * (G // u):
bad += 1
check(f"L1 G is an integer, so xi(Mm) = (xi/gcd(m, xi)) G, {moves} "
f"moves",
bad == 0, f"{bad} violations")
bad = splits = exact = cond_bad = 0
for M in range(1, 400):
x = xi(M)
for m in range(4, 60):
for a in range(2, m):
if m % a:
continue
b = m // a
splits += 1
lhs = premium(M, a) * premium(M * a, b)
whole = premium(M, m)
if lhs % whole:
bad += 1
continue
eq = lhs == whole
exact += eq
ga = premium(M, a)
cond = all(vp(ga, l) == 0 or vp(b, l) <= vp(x, l) - vp(a, l)
for l in fac(b))
cond_bad += cond != eq
print(f" {splits} splits, {exact} exact ({exact / splits:.3f})")
tw = (unpaid(1, 12), unpaid(1, 3), unpaid(3, 4), premium(1, 3),
premium(3, 4), premium(1, 12))
print(f" from 1, 12 = 3 4: unpaid {tw[0]} against {tw[1]} then {tw[2]};"
f" premiums {tw[3]} {tw[4]} against {tw[5]}")
bad += tw != (6, 3, 1, 4, 1, 2)
check("L2 a split never undercounts: G(M,a) G(Ma,b) = k G(M,ab), k "
"an integer; the unpaid part does not telescope (12 from 1)",
bad == 0, f"{bad} violations")
check("L2 equality iff at every l | b, v_l(G(M,a)) = 0 or v_l(b) <= "
"v_l(xi) - v_l(a)", cond_bad == 0, f"{cond_bad} violations")
# ------------------------------------------------------------- premium
def premium_closed(L, x, m):
"""G from lambda(M) = L, m and v_l(xi) at the primes l of m alone."""
lf = fac(L) if L > 1 else {}
WL = W(L)
newf = dict(lf)
u = 1
for l, e in fac(m).items():
c = vp(WL, l) - vp(x, l)
for p, a in (growth.lam_pp(l, c + e)).items():
if a > newf.get(p, 0):
newf[p] = a
u *= l ** (e - min(e, vp(x, l)))
return wall_f(newf) // (WL * u) if newf else 2 // (WL * u)
def section_p():
section("P THE PREMIUM")
bad = 0
for M in range(1, 400):
L, x = lam_n(M), xi(M)
for m in range(2, 60):
if premium_closed(L, x, m) != premium(M, m):
bad += 1
check("P1 G from (lambda(M), m, v_l(xi) at l | m) alone, M < 400, "
"m < 60", bad == 0, f"{bad} violations")
fib = {}
for M in range(1, 1500):
fib.setdefault(lam_n(M), []).append(M)
bad = cells = 0
for L, Ms in fib.items():
if len(Ms) < 2:
continue
for m in range(2, 60):
vals = {premium(M, m) for M in Ms if gcd(M, m) == 1}
if len({M for M in Ms if gcd(M, m) == 1}) >= 2:
cells += 1
bad += len(vals) > 1
check(f"P2 on moves prime to the state G is a function of lambda and "
f"m, {cells} cells", bad == 0, f"{bad} violations")
w = (lam_n(3), lam_n(8), xi(3), xi(8), premium(3, 3), premium(8, 3))
print(f" lambda(3), lambda(8) = {w[0]}, {w[1]}; xi {w[2]}, {w[3]}; "
f"premium of 3: {w[4]} and {w[5]}")
check("P3 the exponents are needed: m = 3 pays 7 at 3 and 1 at 8",
w == (2, 2, 8, 3, 7, 1))
def doors(L):
return {p for p in fac(W(L)) if p > 2}
ok4 = [premium(1, 3), premium(1, 5), premium(1, 15)] == [4, 24, 8]
print(f" from 1: 3, 5 and 15 pay {premium(1, 3)}, {premium(1, 5)} "
f"and {premium(1, 15)}")
for M in (1, 2):
L = lam_n(M)
d5 = doors(lam_n(M * 5)) - doors(L)
d7 = doors(lam_n(M * 7)) - doors(L)
d35 = doors(lam_n(M * 35)) - doors(L)
print(f" at M = {M}: 5 opens {sorted(d5)}, 7 opens {sorted(d7)}, "
f"35 opens {sorted(d35)}")
ok4 &= (d5, d7, d35) == ({3, 5}, {3, 7}, {3, 5, 7, 13})
check("P4 the primes of a move interact: from 1, 3, 5, 15 pay 4, 24, "
"8; from 1 and 2, 5 opens {3, 5}, 7 {3, 7}, 35 {3, 5, 7, 13}",
ok4)
bad = 0
for M in range(1, 400):
L = lam_n(M)
lf = fac(L) if L > 1 else {}
for q in growth.PRIMES[:46]:
if M % q == 0:
continue
L2 = lam_n(M * q)
l2 = fac(L2) if L2 > 1 else {}
want = 1
for p in divisors_f(l2):
p += 1
if p > 2 and is_prime(p):
if L % (p - 1):
want *= p ** (l2.get(p, 0) + 1)
else:
want *= p ** (l2.get(p, 0) - lf.get(p, 0))
g = gain(M, q)
while g % 2 == 0:
g //= 2
bad += g != want
check("P5 a prime move's odd wall gain is the cohort times the bumps, "
"M < 400, q < 200", bad == 0, f"{bad} violations")
# ------------------------------------------------------------- silence
def silent(L, q):
"""q silent at a state of lambda L (q not dividing it): the door of
q shut and the wall grows by exactly q."""
if L % (q - 1) == 0:
return False
merged = growth.merge_max(fac(L) if L > 1 else {}, fac(q - 1))
return wall_f(merged) == q * W(L)
def section_s(primes):
section("S SILENCE")
lams = [2, 4, 6, 8, 10, 12, 16, 18, 20, 24, 28, 30, 36, 40, 42, 48,
54, 60, 66, 72, 84, 90, 96, 120, 180]
bad = tot = 0
census = {}
for L in lams:
sil = []
for q in primes:
if q >= 10 ** 5:
break
if q > 2 and silent(L, q):
sil.append(q)
bad += xi(q) != W(gcd(q - 1, L))
tot += len(sil)
census[L] = sil
check(f"S1 every silent q < 10^5 at 25 even lambda lies in the class "
f"W(gcd(q - 1, lambda)), {tot} silent", bad == 0,
f"{bad} violations")
print(" off the class xi = W(lambda), q < 10^5: lambda silent off "
"least off")
stray = 0
for L, sil in census.items():
off = [q for q in sil if (q - 1) % L]
stray += sum(xi(q) == W(L) for q in off)
print(f" {L:4d} {len(sil):5d} {len(off):5d} "
f"{off[0] if off else '-'}")
print(f" silent q with lambda not dividing q - 1 yet xi(q) = "
f"W(lambda): {stray}")
maj = [L for L, sil in census.items() if L > 2 and
2 * sum((q - 1) % L > 0 for q in sil) <= len(sil)]
carm = [L for L in census if lam_n(W(L)) != L]
shares = [(sum((q - 1) % L > 0 for q in sil) / len(sil), L,
sum((q - 1) % L > 0 for q in sil), len(sil))
for L, sil in census.items() if L > 2]
_, Lm, om, sm = min(shares)
print(f" the least share off the class: {om} of {sm} at lambda = {Lm}")
check("S5 off the class: the majority at every swept lambda > 2, none "
"reading W(lambda); every swept lambda a Carmichael value",
not maj and not stray and not carm,
f"not the majority at {maj}, {stray} strays, non-values {carm}")
sil = {q for q in primes if 2 < q < 10 ** 5 and silent(2, q)}
cls = {q for q in primes if 2 < q < 10 ** 5 and xi(q) == 24}
print(f" lambda = 2: {len(sil)} silent, {len(cls)} in the class 24, "
f"equal by the definitions: {sil == cls}")
odd = [q for q in primes if 2 < q < 10 ** 4 and silent(1, q)]
check("S3 nothing is silent at odd lambda (q < 10^4)", not odd,
f"{odd[:5]}")
bad = cnt = 0
for L in (4, 6, 8, 12):
for q in primes:
if q >= 10 ** 5:
break
if (q - 1) % L == 0 and xi(q) == W(L):
cnt += 1
M = next(M for M in range(2, 10 ** 5)
if lam_n(M) == L and M % q)
bad += premium(M, q) != 1 or xi(M * q) != xi(M)
check(f"S4 the converse: {cnt} class members q = 1 (mod lambda) are "
f"silent, lambda = 4, 6, 8, 12", bad == 0, f"{bad} violations")
# ------------------------------------------------------------- closure
def section_w():
section("W THE CLOSURE")
star = {M: W(lam_n(M)) for M in range(1, 3001)}
infl = all(star[M] % M == 0 for M in star)
idem = all(W(lam_n(star[M])) == star[M] for M in star)
mono = all(star[Mp] % star[M] == 0 for M in star
for Mp in range(2 * M, 3001, M))
check("W1 M -> W(lambda(M)) is inflationary, idempotent and monotone, "
"M <= 3000", infl and idem and mono)
tombs = sorted({W(lam_n(M)) for M in range(1, 10 ** 5)})
ok = all(xi(t) == 1 for t in tombs)
ok &= all(t % 24 == 0 for t in tombs if t > 2)
odd = [t for t in tombs if lam_n(t) % 2]
print(f" {len(tombs)} tombstones reached from M < 10^5, the largest "
f"{tombs[-1]}; odd lambda at {odd}")
check("W2 each is a fixed point, divisible by 24 above 2; 2 alone has "
"odd lambda", ok and odd == [2])
check("W3 W(2^k) is a tombstone at least 2^(k+2), 1 <= k <= 40",
all(xi(W(2 ** k)) == 1 and W(2 ** k) >= 2 ** (k + 2)
for k in range(1, 41)))
# ---------------------------------------------------------- resolution
def section_r():
section("R BLINDNESS AND ITS CURE")
classes = {}
for M in range(2, 1500):
classes.setdefault(xi(M), []).append(M)
blind = {x: Ms for x, Ms in classes.items() if len(Ms) > 1}
pairs = [(a, b) for Ms in blind.values() for i, a in enumerate(Ms)
for b in Ms[i + 1:]]
print(f" {len(blind)} blind classes, {len(pairs)} blind pairs among "
f"the states 2..1499")
reps = [(Ms[0], Ms[1]) for Ms in blind.values()]
below = attain = 0
nonpp = []
for a, b in reps:
x = xi(a)
k = kappa(x)
if not is_prime_power(k):
nonpp.append(x)
d = next((d for d in range(2, 2000) if xi(a * d) != xi(b * d)),
None)
below += d is None or d < k
attain += d == k
print(f" {len(reps)} representative pairs; least resolver = kappa at "
f"{attain} ({attain / len(reps):.3f})")
check("R3 least resolver >= kappa(xi), a prime power", below == 0 and
not nonpp, f"{below} below, non-prime-power kappa at {nonpp}")
qmax = 0
for a, b in reps:
L = lam_n(a) * lam_n(b) // gcd(lam_n(a), lam_n(b))
q = L + 1
while not (is_prime(q) and (a * b) % q):
q += L
qmax = max(qmax, q)
print(f" the Dirichlet prime reaches {qmax}")
w = (xi(2), xi(24), xi(10), xi(120))
check("R5 2 and 24 read 1; the move 5 sends them to 24 and 2",
w == (1, 1, 24, 2), f"{w}")
d = next(d for d in range(2, 100) if xi(10 * d) != xi(11 * d))
print(f" 10, 11 (reading 24, kappa {kappa(24)}): least resolver {d}, "
f"into {xi(10 * d)} and {xi(11 * d)}")
bad = cells = multi = 0
for a, b in reps:
fibres = {}
for d in range(2, 200):
if gcd(d, a * b) == 1:
fibres.setdefault(lam_n(d), []).append(
xi(a * d) != xi(b * d))
cells += len(fibres)
multi += sum(len(v) > 1 for v in fibres.values())
bad += sum(len(set(v)) > 1 for v in fibres.values())
check(f"R6 on d prime to both, R is a union of lambda-fibres, {cells} "
f"fibres, {multi} with two or more d", bad == 0,
f"{bad} split fibres")
bad = 0
for a, b in reps:
for e in divisors_f(fac(xi(a))):
bad += xi(a * e) != xi(b * e)
w = (xi(9), xi(513), xi(9 * 57), xi(513 * 57), xi(27), xi(1539))
print(f" 9, 513 read {w[0]}, {w[1]}; after 57 {w[2]}, {w[3]}; after 3 "
f"{w[4]}, {w[5]}")
check("R7 every divisor of xi keeps a pair blind at every internal "
"reading; 57 is blind at its end, split at 3",
bad == 0 and w == (56, 56, 56, 56, 1064, 56))
# ------------------------------------------------------------- density
def door_primes(n, cap):
"""The primes p <= cap, p != n + 1, with (p - 1) | n."""
return [d + 1 for d in divisors_f(fac(n))
if 2 <= d + 1 <= cap and d + 1 != n + 1 and is_prime(d + 1)]
def measure_p(l, a):
"""P(v_l(q - 1) >= a) over the prime measure."""
if a == 0:
return Fraction(1)
return Fraction(1, (l - 1) * l ** (a - 1))
def delta_exact(ps):
"""The exact density of primes q with (p - 1) not dividing q - 1 for
every p in ps, by enumerating the valuation vectors at the primes
of the p - 1, truncated at the largest exponent any p - 1 needs."""
need = [fac(p - 1) for p in ps]
ls = sorted({l for f in need for l in f})
top = {l: max(f.get(l, 0) for f in need) for l in ls}
vecs = [({}, Fraction(1))]
for l in ls:
out = []
for v, pr in vecs:
for a in range(top[l] + 1):
if a == top[l]:
pa = measure_p(l, a)
else:
pa = measure_p(l, a) - measure_p(l, a + 1)
if l == 2 and a == 0:
continue
nv = dict(v)
nv[l] = a
out.append((nv, pr * pa))
vecs = out
tot = Fraction(0)
for v, pr in vecs:
if not any(all(v.get(l, 0) >= e for l, e in f.items())
for f in need):
tot += pr
return tot
def section_d(primes):
section("D THE DENSITY")
B = growth.bernoulli(40)
bern = all(B[2 * k].denominator == value(
{p: 1 for p in [d + 1 for d in divisors_f(fac(2 * k))]
if is_prime(p)}) for k in range(1, 21))
bad = members = 0
for q in primes:
if q < 11 or q >= 10 ** 6:
continue
vsc = 1
for d in divisors_f(fac(q - 1)):
if is_prime(d + 1):
vsc *= d + 1
c = xi(q) == 24
members += c
bad += c != (vsc == 6 * q)
e57 = (xi(5), xi(7))
v137 = value({d + 1: 1 for d in divisors_f(fac(136))
if is_prime(d + 1)})
print(f" {members} class members in [11, 10^6); xi(5), xi(7) = {e57}; "
f"q = 137: denominator {v137 // 137}q, xi {xi(137)} against "
f"W(4) = {W(4)}")
check("D1 the Bernoulli class: xi(q) = 24 iff the von Staudt-Clausen "
"product of q - 1 is 6q, 11 <= q < 10^6; B_2..B_40 exact; 137 "
"reads 480 at denominator 30q",
bern and bad == 0 and e57 == (48, 72)
and (v137, xi(137)) == (30 * 137, 480), f"{bad} violations")
wdoors = [p for p in primes if 5 <= p <= 47]
ok2 = True
ok3 = None
for T in (7, 11, 23, 47):
ps = [p for p in wdoors if p <= T]
ex = delta_exact(ps)
cnt = tot = 0
for q in primes:
if q <= T:
continue
tot += 1
cnt += all((q - 1) % (p - 1) for p in ps)
emp = cnt / tot
print(f" T = {T:2d}: delta_T exact {float(ex):.5f}, empirical "
f"{emp:.5f} over {tot} primes in (T, 10^7]")
if ok3 is None:
ok3 = abs(float(ex) - emp) < 2e-3
ok3 &= ex == Fraction(1, 4)
check("C3 the control: delta_7 exact is 1/4 and within "
"2 10^-3 of the prime count", ok3)
else:
ok2 &= abs(float(ex) - emp) < 2e-3
check("D2 exact product-measure densities match the prime counts "
"within 2 10^-3, T = 11, 23, 47", ok2)
A = [p for p in wdoors if p <= 23]
B = [p for p in wdoors if 29 <= p <= 47]
dA, dB, dAB = delta_exact(A), delta_exact(B), delta_exact(A + B)
print(f" Harris: delta(A u B) = {float(dAB):.6f} >= delta(A) delta(B) "
f"= {float(dA * dB):.6f}")
check("D3 Harris's inequality holds exactly at the primes 5 .. 47",
dAB >= dA * dB)
bad = cnt = 0
edge = []
for L in (4, 6, 8, 12, 24):
lf = fac(L)
cohort = [p for p in fac(W(L))]
for q in primes:
if q >= 10 ** 6:
break
if (q - 1) % L:
continue
ev = all(vp(q - 1, p) <= lf.get(p, 0) for p in cohort)
ev &= all(p in cohort for p in door_primes(q - 1, q))
if q == L + 1:
edge.append((q, ev, xi(q) == W(L)))
continue
cnt += 1
bad += ev != (xi(q) == W(L))
print(f" q = lambda + 1, a door of lambda itself: {edge}")
check(f"D4 the class of W(lambda) within q = 1 mod lambda, q != lambda "
f"+ 1, is the decreasing-event reading, {cnt} primes", bad == 0
and all(ev and not c for _, ev, c in edge),
f"{bad} violations")
ok5 = True
L = 1
for n in range(1, 31):
L = L * n // gcd(L, n)
ok5 &= kappa(W(L)) > n + 1
check("D5 kappa(W(lcm(1..n))) > n + 1, n <= 30", ok5)
L = 1
found = []
for n in range(1, 9):
L = L * n // gcd(L, n)
if L % 2:
continue
WL, hits, t = W(L), [], 1
while len(hits) < 2 and L * t < 10 ** 9:
q = L * t + 1
if is_prime(q) and xi(q) == WL:
hits.append(q)
t += 1
found.append((n, hits))
print(" class members at W(lcm(1..n)): "
+ "; ".join(f"n={n}: {h}" for n, h in found))
check("D5 two primes read W(lcm(1..n)) at every even lcm, n <= 8",
all(len(h) == 2 for _, h in found))
d1 = 1 / 3 - 2 / 3 * log(1.5)
eta = 7 / 6 * log(7 / 6) - 1 / 6
print(f" d1 = 1/3 - (2/3) log(3/2) = {d1:.4f}; eta = (7/6) log(7/6) - "
f"1/6 = {eta:.4f}; eps(T) << (log T)^(-{eta / 2:.4f})")
def main():
global SPF
t0 = time.time()
SPF = spf_sieve(SPF_N)
primes = [q for q in range(2, SPF_N + 1) if SPF[q] == 0]
section_c()
if not all(CHECKS):
print("\nCONTROL FAILED: nothing below is read.")
raise SystemExit(1)
section_h()
section_l()
section_p()
section_s(primes)
section_w()
section_r()
section_d(primes)
print()
print(f"{sum(CHECKS)}/{len(CHECKS)} checks passed, "
f"{time.time() - t0:.1f} s")
raise SystemExit(0 if all(CHECKS) else 1)
if __name__ == "__main__":
main()