bridges.py
Checks: BRIDGES: The seating law theorem; observation; BRIDGES: The phoenix theorem; observation; BRIDGES: The atom criterion criterion; BRIDGES: The least unrealizable odd number rule; BRIDGES: Transparent rungs are transparent moves property; GROWTH: The lock-prime law theorem; rule.
To run it: save bridges.py, with growth.py beside it; standard library only.
"""bridges.py -- where growth meets open number theory: the primes a
world grown along a fixed alphabet ever opens, the phoenix that lives
on the least move, the atoms of the odd part of lambda and the least
odd number that is never one, and the rudder that steers the lock.
QUESTION. growth.py grows Z/M by the cheapest move a demand admits.
Several of its reachable configurations turn out to exist iff a prime
p exists whose p - 1 has a prescribed multiplicative shape, so a
question about a growth world IS a question about primes. Which of
these bridges are exact equivalences, which run only one way, and
which land on a proved theorem rather than an open one?
THE OBJECT. lambda is the Carmichael function, W(L) the wall, the
largest M with lambda(M) | L (growth.py). For a set S of primes, S' is
its complement and n_(S') the part of n prime to S. An ALPHABET WORLD
(s, S) starts at the seed s and repeats two phases forever: FILL, the
greedy transparent walk (least m with lambda(Mm) = lambda(M)), which
dies at exactly W(lambda(M)) (growth.py, the three fates); then PUSH,
the least move (the least power of q raising lambda) at one q in S, under
any schedule that pushes every q in S infinitely often. The PHOENIX
is the alphabet world S = {2}. A world's SEATS are the primes it
ever seats. The ODD PART of lambda(M) is written odd(lambda(M)); an
ATOM is A(q, a) = q^(a-1) odd(q - 1), q an odd prime, a >= 1. An odd h is
REALIZABLE when h = odd(lambda(M)) for some M. An odd h is SIERPINSKI
when h 2^b + 1 is composite for every b >= 1.
THE ARGUMENT (written before the engine).
(1) THE SEATING LAW. Let L_t be lambda after t pushes; fills do not
move lambda, and lambda(W(L)) = L whenever L = lambda(M) with
M | W(L). At the wall an odd prime r is seated iff (r - 1) | L,
at depth v_r(L) + 1. A push of an unseated q opens it at cost q
and multiplies L's S'-part by at most (q - 1)_(S'); a push of a
seated q deepens it by one and adds exactly one factor q, with
no S'-part, since (q - 1) | L already; a push of 2 adds one
factor 2. So once every q in S has been pushed, L_t's S'-part
is F = (lcm(lambda(s), q - 1 : q in S))_(S') forever, and its
S-part diverges at every q in S. The seats are the union of
the supports of W(L_t):
Seats(s, S) = {p prime : (p - 1)_(S') divides F},
schedule-free. An odd seat outside S ends at depth
v_p(F) + 1. S is SHIFT-CLOSED when every q - 1, q in S, is
S-smooth; then F = lambda(s)_(S'), and at s = 1 the seats are
exactly the primes p with p - 1 S-smooth, so the world opens
infinitely many seats iff there are infinitely many such
primes: an equivalence per alphabet, Fermat's question at
{2}, Pierpont's at {2, 3}.
(2) THE PHOENIX. At a wall every m >= 2 raises lambda, so the
dynamics demand's own least move is 2: the phoenix is the one
greedy law "the least transparent move, else the least move",
with no free choice. Its F is h = odd(lambda(s)), frozen at
birth, and its seats are spectrum(h) = {p : odd(p - 1) | h}.
spectrum is monotone in h under divisibility, so every
phoenix contains spectrum(1) = {2} with the Fermat primes: the
seed-1 phoenix opens infinitely many seats iff there are
infinitely many Fermat primes. The Fermat primes open at
v_2(lambda) = 1, 2, 4, 8, 16, their own exponents.
(3) THE ATOMS. lambda(M) is the lcm of lambda(q^a) over q^a || M,
and the odd part of an lcm is the lcm of the odd parts, so
odd(lambda(M)) = lcm of A(q, a) over the odd q^a || M, the
2-column contributing nothing. REALIZABILITY CRITERION: odd h is
realizable iff every prime power l^j || h is served by an atom
A | h with v_l(A) = j. (Only if: the lcm attains v_l = j at some
atom, and every atom divides h. If: take each serving atom's
q^a, the largest a per q; each A(q, a) grows with a and the one
kept is itself a serving atom, so the product M has
odd(lambda(M)) = h.) An atom equals h iff h 2^b + 1 is prime for
some b >= 1 (a = 1), or h = q^(a-1) odd(q - 1) with a >= 2 and
q | h, a finite check: the atoms are the h with some h 2^b + 1
prime, plus a finite correction.
(4) THE LEAST UNREALIZABLE ODD NUMBER. If l^j || h is unserved then
l^j itself is no atom. l^j is an atom iff l^j 2^b + 1 is prime
for some b >= 1, or l is a Fermat prime (then A(l, j + 1) = l^j).
So an unrealizable h has a unitary prime-power divisor l^j,
l not a Fermat prime, that is Sierpinski; and such an l^j is
itself unrealizable, since the only divisor of l^j with
v_l = j is l^j. The least unrealizable odd number is therefore
the least Sierpinski prime power of non-Fermat base. 271129 is
prime and Sierpinski (a covering set {3, 5, 7, 13, 17, 241} of
period 24), and 271129 - 1 = 2^3 33891, so it bounds that least
number: no M has odd(lambda(M)) = 271129. 78557, the Sierpinski
number with covering set {3, 5, 7, 13, 19, 37, 73} of period 36,
is 17 * 4621, no prime power: no ATOM, yet realizable, by two
primes 137 and 18927617, where 137 = 17 2^3 + 1 and 18927617 =
4621 2^12 + 1. The old record called the 78557 obstruction an
impossible edit l^e; 78557 is not a prime power, and the
obstruction it certifies is to one prime power, not to
realizability.
(5) TRANSPARENT RUNGS ARE TRANSPARENT MOVES. lambda(Mp) =
lcm(lambda(M), p - 1) for a prime p not dividing M, so rung k of
the primorial tower is transparent (lambda(p_k#) =
lambda(p_(k-1)#)) iff p_k is a move the transparency demand
admits at p_(k-1)#, and the tower is the greedy independence
walk from 1. The density theorem is the statement that along
independence's walk the transparency demand admits almost every
move: one walk, two demands, agreeing on a set of density 1.
(6) THE RUDDER. From any state one multiplication locks the
dynamics demand's greedy walk (the least lambda-raising move)
onto any prime q. At q = 2: raise 2 to depth
max(3, v_2(lambda) + 2); 2's door is then 1, price 2, the least
possible move, forever. At odd q: raise q to depth
v_q(lambda') + 1, lambda' the lambda after the multiplication,
so its door is 1, price q, times a prime P = 1 (mod B),
P != 1 (mod q), P not dividing the state, where B is the lcm
over the primes l < q of l - 1 and of l^(a_l + c_l + 2), a_l the
depth of l and c_l least with l^(c_l + 2) > q. Then every least move
at l < q costs more than q: an unseated l has (l - 1) | lambda and
pays l^(v_l + 2) > q; a seated l pays l^(v_l - a_l + 2) > q; at
l = 2 the same with the two-adic scan. q is prime to B, so
Dirichlet supplies P; P - 1 carries no q, so q's door stays 1;
P's own least move costs at least P > q. Deepening q adds only powers of
q to lambda, which moves no rival's price down (every least
move only grows, growth.py), so the lock holds forever.
DESIGN. Standard library; one process. growth.py supplies factor,
lambda, the wall and the least moves; lambda is carried as a factorization,
with the factorization of P - 1 supplied where P exceeds the trial
bound.
C POSITIVE CONTROLS, before any verdict; a failed control stops
the run. C1 lambda against the unit group's exponent at every
M <= 300 [ruled: from M = 2, lambda(1) = 1 trivially]. C2 the
wall formula against the largest M below 131100 with
lambda(M) | L, L = 2..24 even, 131100 past W(24) = 131040.
C3 the primality test: below 3 10^24, by Miller-Rabin, it
certifies 7 = 3 2 + 1 and refuses 78557 2 + 1 and 2^32 + 1; past
it, by Proth's theorem, it certifies 47 2^583 + 1 and
383 2^6393 + 1, refuses 3 2^82 + 1 by its factor 7 before the
theorem runs, and refuses 3 2^90 + 1 (no factor below 2000)
[ruled: that premise now checked in the control]. C4 the
covering checker accepts 78557's set over one period and
rejects a planted non-cover ({3, 5} for k = 1).
W the seating law. W1 the pushes run in lambda-space, L -> lambda
of the wall times the least move, at nine alphabets {2}, {2, 3},
{2, 5}, {2, 3, 5}, {2, 3, 5, 7}, {3}, {5}, {3, 5}, {2, 11} from
s = 1 and at {2, 3} and {2} from s = 7, 11, 65, 105, under a
round-robin and a seeded random schedule, 25 pushes per letter.
At every step with L <= 10^6 the wall is built from its primes,
held to growth.py's wall, lambda(W(L)) = L read and the step held
to lambda of that wall times its least move (the step shares
least_move and the depth rule with the world's run, so it tests
only that the two depth formulas agree). The final S'-part of L
and the seats below 10^6 are checked against F and the predicate:
a lambda-space push adds (q - 1)'s S'-part by construction, so
they read only that 25 pushes per letter carry every seat below
10^6. W2 the count of seats below each power of 10, and the
predicate's {2} seat set against 2 and the Fermat primes.
P the phoenix. P1 the greedy law "least transparent move, else the
least move" run by brute force from s = 1, 7, 11 through the
first walls with M <= 2 10^7, a state with no transparent
m <= 1000 read as a wall, held to W(lambda) and pushed by 2.
P2 2^j + 1 prime for j <= 40 only at j = 1, 2, 4, 8, 16, the
seed-1 phoenix's seats (each opens at v_2(lambda) = j by the
seating predicate, argued, not computed). P3, a print: the
spectra along the chain 1 | 3 | 9 | 45 | 315 below 10^6, their
nesting read, and spectrum(3)'s first primes past spectrum(1).
A the atoms. A1 odd(lambda(M)) against the lcm of the
atoms, every M <= 20000, (3)'s identity read through growth.py's
lambda. A2 every odd h <= 999 served by atoms, Proth witnesses
searched to b <= 1200, 383's witness b = 6393 the one C3
certifies; the M built from the serving atoms has odd(lambda) =
h by the criterion's if-half, recomputed.
A3, a print: the odd h < 1000 the set odd(lambda(M)) over
M <= 10^6 already holds, each read as the lcm of its atoms by
(3)'s identity. A4 78557: the covering over its period, no
atom by the finite correction either (q^(a-1) | 78557 forces
a = 2 at q = 17 and 4621, so a in {2, 3} covers it), and the two-prime
realization, its lambda computed. A5 271129: prime, not 2^n + 1,
the covering, hence unrealizable; that no M <= 10^6 realizes it
prints, vacuous there, no prime q <= 10^6 having 271129 | q - 1.
S the search below 271129: every odd prime power l^j < 271129 of
non-Fermat base, the least b <= 1000 with l^j 2^b + 1 prime,
certified; the survivors counted, the first ten printed.
T the transparency reading, a print: the transparent share at
k = 50, 500, 2000; rung k transparent iff p_k is a transparent
move at p_(k-1)# is (5), one predicate.
R the rudder. R1 the 2-lock from 200 states (ten specials and 190
seeded random M <= 10^6), 30 greedy picks after the
multiplication. R2 the odd targets 3, 5, 7, 13, 17 from the states
30, 3^15, 2^20, 510510, 17^6, 30 greedy picks after the
multiplication, the menu scanned at every prime up to q that
could undercut the running least. Each P is certified prime by
Pocklington's test on P - 1, factored. The code
builds B with each l to the power a_l + c_l + 4, a multiple of
the B of (6), which the argument allows, since it needs only that
B carry those powers and q not divide it.
PREDICTIONS, fixed before the run.
C C1, C2 agreement everywhere; C3 and C4 as stated.
W W1 zero disagreements; F = 1 at the five alphabets holding 2 and
shift-closed, 2 at {3}, 4 at {5}, 4 at {3, 5}, 5 at {2, 11}. The
counts below 10^6 reproduce the replaced record's: 6, 42, 20,
141, 324, 8, 7, 46, 21. W2 {2} stalls at 6 past 65537; {2, 3}
reads 4, 10, 18, 25, 32, 42 across the decades 10..10^6.
P P1 zero disagreements, no transparent m at any wall. P2 the
five Fermat primes at v_2(lambda) = 1, 2, 4, 8, 16. P3 the
sizes nondecreasing, 6, 12, 18, 30, 56 as in the replaced
record.
A A1 zero mismatches. A2 every odd h <= 999 realizable, 47 at
b = 583 and 383 the only one past the b bound.
A4, A5 as argued in (4).
S the survivors are primes, a few dozen at most; no prime power
l^j with j >= 2 survives. TRANSPLANT: from memory of the prime
Sierpinski problem, unresolved primes below 271129 include
22699 and 67607; this is a recollection, not a source, and
the search, not it, is what may be quoted.
Added after the outside read (W. Keller, The Sierpinski Problem:
Definition and Status, prothsearch.com/sierp.html, updated
2026-07-29): every odd k < 271129 carries a known prime
k 2^n + 1 but 78557, proved Sierpinski, and 20 still open, whose
prime powers are nine
primes, 22699, 67607, 79309, 79817, 152267, 156511, 222113,
225931, 237019. S2: the one proper-power survivor, 143641 = 379^2,
resolves at b = 1212, Proth-certified and least (a scratch sieve
found it; the run re-derives it from b = 1). S3: all nine listed
primes are search survivors; one with a prime at b <= 1000 would
put the search and the list at odds, and is a kill.
T the share 0.47, 0.72, 0.77 as tower_growth.py's density theorem
prints (one predicate, so nothing to disagree with).
R R1 200/200; R2 25/25.
A KILL is any disagreement in W1, P1 or A1; a seat set
unequal to its predicate; a covering that fails in A4 or A5, which
kills the bound 271129 and the 78557 reading with it; an odd h <= 999
not realized; a rudder pair that does not lock. A control out of its
band voids the verdicts that lean on it. A replaced record's figure
not reproduced, with the identities green, is a definition to read,
not a kill. P3 and T are prints: P3's nesting holds by construction and
T is one predicate. R1 scans the menu at 2 alone, so its q != 2 clause
cannot fire and R1 reads the cost 2.
FINDINGS. 19/19 checks PASS and no kill (A3 is a print: an lcm of odd
atoms is odd, so as a check it could not fail). Two predictions missed and one
control was built too small, recorded below.
C lambda is the unit exponent at every M <= 300. C2 FAILED on its
first run: the brute search stopped at 70000 while W(24) =
131040, so the control's range, not the formula, was out of band;
widened to 131100 it agrees at every even L <= 24. The Proth
certificate and the covering checker behave as stated, 78557's
period 36, and both refusals past 3 10^24 hold.
W lambda(W(L)) = L and the step agree at all 489 steps with
L <= 10^6; F and the seats agree in 17 (seed, alphabet) cases
under both schedules; F = 1 at {2}, {2, 3}, {2, 5}, {2, 3, 5},
{2, 3, 5, 7}, 2 at {3}, 4 at {5} and {3, 5}, 5 at {2, 11};
seats below 10^6: 6, 42, 20, 141, 324, 8, 7, 46, 21, the
replaced record's. By
decade 10..10^6: {2} 3, 4, 5, 5, 6, 6; {2, 3} 4, 10, 18, 25, 32,
42; {2, 3, 5} 4, 14, 34, 59, 95, 141; {2, 3, 5, 7} 4, 17, 52, 101,
194, 324; {2, 5} 3, 6, 11, 13, 18, 20.
P the greedy law "least transparent move, else the least move"
stopped at 15 walls from seeds 1, 7, 11 below 2 10^7, every one
equal to W(lambda). 2^j + 1 is prime for j <= 40 only at j = 1, 2,
4, 8, 16. The spectra along 1 | 3 | 9 | 45 | 315 below 10^6 are
nested with sizes 6, 13, 20, 35, 65; MISSED against the replaced
record's 6, 12, 18, 30, 56, which counted to a different bound
(its spectrum(3) omits 786433 = 3 2^18 + 1): a definition, not a
kill.
A odd(lambda(M)) is the lcm of its atoms at every M <= 20000. Every
odd h <= 999 is realized by a built M; the atoms needing b > 64
are 47 (b = 583, and every h <= 999 whose serving atom the search
took at 47), 587 (227), 631 (144), 881 (1027) and 383 (none at b
<= 1000, S; 6393 the certified witness). M <= 10^6 already
realizes 471 of the 500 odd h < 1000. 78557 is covered with
period 36, is no atom by the finite correction either, and
odd(lambda(137 18927617)) = 78557. 271129 is prime, 271128 = 2^3
3 11 13 79, its covering holds with period 24, and no M <= 10^6
realizes it (vacuously).
S 23844 prime powers of non-Fermat base lie below 271129; 513 resolve
only at 200 < b <= 1000; 278 SURVIVE to b <= 1000, the first 383,
881, 2897, 3061, 4861, 5297, 5897, 6379, 7013, 8269, and among them
one proper power, 143641 = 379^2. MISSED: the slate predicted a few
dozen survivors and no proper power. The survivors below 1000 are
exactly 383 and 881, the two A2 resolved past b = 1000. S2: 143641
resolves at least b = 1212, so no proper power survives. S3: all
nine primes the literature leaves open are survivors. With that
list, every prime power of non-Fermat base below 271129 outside the
nine carries a known prime l^j 2^b + 1, so the least unrealizable
odd number is the least prime Sierpinski number, one of the nine or
271129.
T the transparent share 23 of 49 (0.469) at k = 50, 358 of 499
(0.717) at 500, 1531 of 1999 (0.766) at 2000, tower_growth.py's
share over the k - 1 rungs that can move.
R 200/200 states lock onto 2 after one multiplication; 25/25
(state, odd target) pairs lock after one multiplication, the
primes P from 17 to about 7.7 10^28, each Pocklington-certified,
larger than the replaced record's because B here is built from
every prime below q and not only from the rival moves that needed
raising.
Tiers: (1), (2) and (6) are theorems, verified in the ranges printed;
(3) is a criterion, proved both ways, verified in the ranges printed;
(4) is a rule, proved, with the bound 271129 proved and the search an
observation, and the reading of the least unrealizable number as the
least prime Sierpinski number rests on the literature's list of known
primes; (5) is a property.
RUN RECORD. python bridges.py: 19/19 checks, 9.1 s, peak commit
57.8 MB (read under a commit ceiling), with W1's wall against growth.py's wall, W1's
seat match and A1 now checks and C1 reading lamf beside lam_int; a
scratch copy dropping 13 from the built wall fails the wall check
alone (286 off), one inflating 31's atom fails A1, one striking 41
from the predicate fails the seat match. Among its prints: S = {3} from seed 5 has F = 4 and seats 13;
S = {2, 11} seats 41 and not 101; the spectra nest, spectrum(3) adding
7, 13, 97, 193, 769 first; no prime q <= 10^6 has 271129 | q - 1; the
200 rudder states are distinct.
"""
import os
import random
import sys
import time
from math import gcd
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import growth # noqa: E402
from growth import (factor, lam_int, value, merge_add, lcm, # noqa: E402
v2, is_prime_mr, least_move, wall)
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 sieve(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 s
X = 10 ** 6
ISP = sieve(X)
PRIMES_X = [i for i in range(X + 1) if ISP[i]]
def odd(n):
while n % 2 == 0:
n //= 2
return n
def part_off(n, S):
"""The part of n prime to every prime in S."""
for q in S:
while n % q == 0:
n //= q
return n
def jacobi(a, n):
a %= n
t = 1
while a:
while a % 2 == 0:
a //= 2
if n % 8 in (3, 5):
t = -t
a, n = n, a
if a % 4 == 3 and n % 4 == 3:
t = -t
a %= n
return t if n == 1 else 0
SMALL = [p for p in PRIMES_X if p < 2000]
SMALL_PROD = 1
for _p in SMALL:
SMALL_PROD *= _p
def proth_prime(k, b):
"""Is k 2^b + 1 prime, with a proof. Below 3 10^24 deterministic
Miller-Rabin (thirteen prime bases); above, k < 2^b holds and
Proth's theorem is applied with a base of Jacobi symbol -1, which
exists for every prime n; the first 59 odd primes are tried, and
none qualifying raises."""
n = k * (1 << b) + 1
if n < 3 * 10 ** 24:
return is_prime_mr(n)
assert k < (1 << b)
if gcd(n, SMALL_PROD) != 1:
return False
for a in SMALL[1:60]:
if jacobi(a, n) == -1:
return pow(a, (n - 1) // 2, n) == n - 1
raise AssertionError("no non-residue base found")
LEAST = {}
def least_proth(k, bmax):
if (k, bmax) not in LEAST:
LEAST[(k, bmax)] = next((b for b in range(1, bmax + 1)
if proth_prime(k, b)), None)
return LEAST[(k, bmax)]
def covers(k, cover):
"""Does the set `cover` divide k 2^b + 1 for every b >= 1? Checked
over one period, the lcm of the orders of 2 modulo the cover."""
per = 1
for p in cover:
o, x = 1, 2 % p
while x != 1:
x = x * 2 % p
o += 1
per = lcm(per, o)
ok = all(any((k * pow(2, b, p) + 1) % p == 0 for p in cover)
for b in range(1, per + 1))
return ok, per
def fermat(p):
return p > 2 and (p - 1) & (p - 2) == 0
def atom(q, a):
return q ** (a - 1) * odd(q - 1)
# lambda as a factorization, with factorizations of large p - 1 supplied
KNOWN = {}
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 = dict(KNOWN[p]) if p in KNOWN else factor(p - 1)
if a > 1:
out[p] = out.get(p, 0) + a - 1
return out
def pocklington(n, nf):
"""n prime, proved: nf is the complete factorization of n - 1."""
assert value(nf) == n - 1
for r in nf:
for a in range(2, 1000):
if pow(a, n - 1, n) != 1:
return False
if gcd(pow(a, (n - 1) // r, n) - 1, n) == 1:
break
else:
return False
return True
def lamf(mf):
out = {}
for p, e in mf.items():
for r, c in lam_pp(p, e).items():
if c > out.get(r, 0):
out[r] = c
return out
# ------------------------------------------------------------ section C
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 section_c():
section("C POSITIVE CONTROLS, before any verdict")
bad = sum(unit_exponent(M) != lam_int(M)
or value(lamf(factor(M))) != lam_int(M)
for M in range(2, 301))
control("C1 lambda is the unit group's exponent, M <= 300, by "
"growth.py's lam_int and by this script's lamf", bad == 0,
f"{bad} off")
top = 131100
lam_small = [0] + [lam_int(M) if M > 1 else 1 for M in range(1, top)]
bad = []
for L in range(2, 25, 2):
brute = max(M for M in range(1, top) if L % lam_small[M] == 0)
if brute != wall(L):
bad.append(L)
control("C2 the wall formula against the largest M < 131100, even "
"L <= 24", not bad, f"W(12) = {wall(12)}, W(24) = {wall(24)}")
ok = (proth_prime(3, 1) and proth_prime(47, 583)
and proth_prime(383, 6393) and not proth_prime(78557, 1)
and not proth_prime(1, 32) and not proth_prime(3, 82)
and not proth_prime(3, 90)
and all((3 * 2 ** 90 + 1) % p for p in PRIMES_X if p < 2000))
control("C3 the primality test: 7, 47 2^583+1, 383 2^6393+1 prime; "
"78557 2+1, 2^32+1, 3 2^82+1, 3 2^90+1 (no factor below "
"2000) refused", ok)
good, per = covers(78557, (3, 5, 7, 13, 19, 37, 73))
planted, _ = covers(1, (3, 5))
control("C4 the covering checker: 78557's set accepted, a planted "
"non-cover rejected", good and not planted, f"period {per}")
# ------------------------------------------------------------ section W
def run_world(s, S, schedule, pushes, rnd=None):
"""Pushes in lambda-space: L -> lambda(W(L) * least move). Returns the
final L as a factorization, the seats below X, L before each push
and after the last, and the pushes in order."""
L = lamf(factor(s)) if s > 1 else {}
seq = []
for _ in range(pushes):
seq.extend(S)
if schedule == "random":
rnd.shuffle(seq)
seen = set()
Ls = [dict(L)]
for q in seq:
Lv = value(L)
if q == 2:
a = v2(Lv) + 2 if Lv % 2 == 0 else 1
elif Lv % (q - 1) == 0:
a = L.get(q, 0) + 1
else:
a = 0
d = least_move(q, a, L)
r = 0
while d > 1:
d //= q
r += 1
L2 = dict(L)
for p, c in lam_pp(q, a + r).items():
if c > L2.get(p, 0):
L2[p] = c
L = L2
Ls.append(dict(L))
Lfinal = value(L)
for p in PRIMES_X:
if Lfinal % (p - 1) == 0:
seen.add(p)
return L, seen, Ls, seq
def wall_f(L):
"""W(L) as a factorization, built from its primes: 2 to v_2(L) + 2
and each odd prime p with (p - 1) | L to v_p(L) + 1; 2 alone at odd
L. Its odd primes are read from PRIMES_X, so L <= 10^6."""
Lv = value(L)
if Lv % 2:
return {2: 1}
out = {2: L.get(2, 0) + 2}
for p in PRIMES_X[1:]:
if p - 1 > Lv:
break
if Lv % (p - 1) == 0:
out[p] = L.get(p, 0) + 1
return out
def seating_law(s, S):
base = lam_int(s) if s > 1 else 1
for q in S:
base = lcm(base, q - 1)
F = part_off(base, S)
return F, {p for p in PRIMES_X if F % part_off(p - 1, S) == 0}
ALPHABETS = [(2,), (2, 3), (2, 5), (2, 3, 5), (2, 3, 5, 7), (3,), (5,),
(3, 5), (2, 11)]
def section_w():
section("W THE SEATING LAW")
rnd = random.Random(1400)
cases = [(1, S) for S in ALPHABETS]
cases += [(s, S) for s in (7, 11, 65, 105) for S in ((2,), (2, 3))]
bad, rows, steps, off, woff = 0, [], 0, 0, 0
for s, S in cases:
F, law = seating_law(s, S)
for sched in ("round", "random"):
L, seen, Ls, seq = run_world(s, S, sched, 25, rnd)
for i, q in enumerate(seq):
if value(Ls[i]) > X:
break
steps += 1
Wf = wall_f(Ls[i])
woff += value(Wf) != wall(value(Ls[i]))
d = least_move(q, Wf.get(q, 0), Ls[i])
if (lamf(Wf) != Ls[i]
or lamf(merge_add(Wf, factor(d))) != Ls[i + 1]):
off += 1
if part_off(value(L), S) != F or seen != law:
bad += 1
if s == 1:
rows.append((S, F, len(law)))
for S, F, n in rows:
print(f" S={str(S):16} F={F:<3} seats below 10^6: {n}")
check("W1 lambda(W(L)) = L and the lambda-space step, the wall built "
"from its primes, every step with L <= 10^6", off == 0,
f"{steps} steps, {off} off")
check("W1 the wall built from its primes is growth.py's wall, every "
"step with L <= 10^6", woff == 0, f"{woff} off")
check("W1 F and the seats below 10^6 after 25 pushes per letter "
"match the predicate", bad == 0, f"{bad} disagreements in "
f"{len(cases)} (seed, alphabet) cases x 2 schedules")
F5, law5 = seating_law(5, (3,))
_, law211 = seating_law(1, (2, 11))
print(f" S={{3}} from seed 5: F={F5}, 13 seated: {13 in law5}; "
f"S={{2, 11}} from seed 1: 41 seated: {41 in law211}, "
f"101 seated: {101 in law211}")
print(" seats below 10^j, j = 1..6:")
for S in ((2,), (2, 3), (2, 3, 5), (2, 3, 5, 7), (2, 5)):
_, law = seating_law(1, S)
counts = [sum(1 for p in law if p < 10 ** j) for j in range(1, 7)]
print(f" S={str(S):14} {counts}")
_, w2 = seating_law(1, (2,))
check("W2 the predicate's seats for S = {2} from seed 1 are 2 and the"
" Fermat primes below 10^6",
sorted(w2) == [2, 3, 5, 17, 257, 65537])
# ------------------------------------------------------------ section P
def section_p():
section("P THE PHOENIX")
fm = [None, None] + [factor(m) for m in range(2, 1001)]
bad = 0
walls_seen = 0
for s in (1, 7, 11):
# the one greedy law: least transparent move, else the least move
Mf = factor(s) if s > 1 else {}
while value(Mf) <= 2 * 10 ** 7:
L = lamf(Mf)
m = 2
while m <= 1000 and lamf(merge_add(Mf, fm[m])) != L:
m += 1
if m <= 1000:
Mf = merge_add(Mf, fm[m])
continue
# no transparent m <= 1000: the state must be the wall
walls_seen += 1
if value(Mf) != wall(value(L)):
bad += 1
Mf = merge_add(Mf, {2: 1})
check("P1 the greedy law's walls are W(lambda), 3 seeds, M <= 2 10^7",
bad == 0 and walls_seen > 0, f"{walls_seen} walls, {bad} off")
opened = []
for j in range(1, 41):
if proth_prime(1, j):
opened.append(j)
check("P2 2^j + 1 prime for j <= 40 only at 1, 2, 4, 8, 16",
opened == [1, 2, 4, 8, 16], f"{opened}")
spectra = [{p for p in PRIMES_X if h % odd(p - 1) == 0}
for h in (1, 3, 9, 45, 315)]
nested = all(a <= b for a, b in zip(spectra, spectra[1:]))
print(f" P3 spectrum sizes along 1 | 3 | 9 | 45 | 315 below 10^6: "
f"{[len(x) for x in spectra]}, nested: {nested}; spectrum(3) "
f"adds {sorted(spectra[1] - spectra[0])[:5]} first")
# ------------------------------------------------------------ section A
def covering_atoms(h, bmax, witness):
"""For each l^j || h a prime power q^a whose atom divides h with
v_l = j, or None. Atoms by the finite correction first, then by
primes m 2^b + 1 over the divisors m of h."""
hf = factor(h)
divs = [1]
for p, e in hf.items():
divs = [d * p ** k for d in divs for k in range(e + 1)]
chosen = {}
for l, j in hf.items():
found = None
# a >= 2: q | h, q^(a-1) odd(q - 1) | h with v_l = j
for q in hf:
for a in range(2, hf[q] + 2):
A = atom(q, a)
if h % A == 0 and factor(A).get(l, 0) == j:
found = (q, a, None)
break
if found:
break
if not found:
for m in sorted(divs):
if factor(m).get(l, 0) != j:
continue
b = witness.get(m) or least_proth(m, bmax)
if b is not None:
q = m * (1 << b) + 1
KNOWN[q] = merge_add(factor(m), {2: b})
found = (q, 1, b)
break
if not found:
return None
chosen[l] = found
return chosen
def section_a():
section("A THE ATOMS OF odd(lambda)")
bad = 0
for M in range(1, 20001):
g = 1
for q, a in factor(M).items() if M > 1 else []:
if q != 2:
g = lcm(g, atom(q, a))
if odd(lam_int(M) if M > 1 else 1) != g:
bad += 1
check("A1 odd(lambda(M)) is the lcm of its atoms, M <= 20000",
bad == 0, f"{bad} off")
witness = {383: 6393}
missing, big = [], []
for h in range(1, 1000, 2):
ch = covering_atoms(h, 1200, witness)
if ch is None:
missing.append(h)
continue
Mf = {}
for q, a, b in ch.values():
Mf[q] = max(Mf.get(q, 0), a)
if b is not None and b > 64:
big.append((h, b))
if odd(value(lamf(Mf))) != h:
missing.append(h)
check("A2 every odd h <= 999 realized by a built M", not missing,
f"missing {missing}; past b = 64: {sorted(set(big))}")
spf = list(range(X + 1))
for p in PRIMES_X:
if p * p > X:
break
if spf[p] == p:
for k in range(p * p, X + 1, p):
if spf[k] == k:
spf[k] = p
lam_odd = set()
hit271 = False
for M in range(2, X + 1):
n, g = M, 1
while n > 1:
q, a = spf[n], 0
while n % q == 0:
n //= q
a += 1
if q != 2:
g = lcm(g, atom(q, a))
lam_odd.add(g)
if g == 271129:
hit271 = True
small = {g for g in lam_odd if g < 1000}
print(f" A3 {len(small)} of 500 odd h < 1000 seen by M <= 10^6")
ok78, per78 = covers(78557, (3, 5, 7, 13, 19, 37, 73))
corr = any(h == 78557 for h in [atom(q, a) for q in (17, 4621)
for a in (2, 3)])
two = (is_prime_mr(137) and is_prime_mr(18927617)
and 137 == 17 * 8 + 1 and 18927617 == 4621 * 4096 + 1)
g78 = odd(value(lamf({137: 1, 18927617: 1})))
check("A4 78557 = 17 * 4621: covered (no Proth atom), no finite "
"correction, realized by 137 * 18927617",
ok78 and not corr and two and g78 == 78557,
f"period {per78}; odd(lambda) of the product = {g78}")
ok27, per27 = covers(271129, (3, 5, 7, 13, 17, 241))
check("A5 271129: prime, not 2^n + 1, covered, hence unrealizable",
is_prime_mr(271129) and not fermat(271129) and ok27,
f"period {per27}; 271128 = {factor(271128)}")
q271 = [q for q in PRIMES_X if q % 271129 == 1]
print(f" A5 an M <= 10^6 realizing it: {hit271}; primes q <= 10^6 "
f"with 271129 | q - 1: {q271}")
# ------------------------------------------------------------ section S
def section_s():
section("S THE SEARCH BELOW 271129")
bound = 271129
pps = []
for l in PRIMES_X:
if l < 3 or l >= bound:
continue
if fermat(l):
continue
x = l
while x < bound:
pps.append(x)
x *= l
survivors, hard = [], []
for k in sorted(pps):
b = least_proth(k, 1000)
if b is None:
survivors.append(k)
elif b > 200:
hard.append((k, b))
powers = [k for k in survivors if not is_prime_mr(k)]
print(f" {len(pps)} prime powers of non-Fermat base below {bound}")
print(f" least b past 200: {len(hard)} of them, the largest "
f"{max(hard, key=lambda x: x[1])}")
print(f" survivors to b <= 1000: {len(survivors)}, the first ten "
f"{survivors[:10]}")
print(f" proper powers among them: {[(k, factor(k)) for k in powers]}")
check("S1 the survivors below 1000 are exactly 383 and 881",
[k for k in survivors if k < 1000] == [383, 881],
f"{len(survivors)} survivors")
b379 = least_proth(143641, 1212)
check("S2 143641 = 379^2 resolves at least b = 1212, Proth-certified",
b379 == 1212, f"least b {b379}")
listed = [22699, 67607, 79309, 79817, 152267, 156511, 222113, 225931,
237019]
check("S3 the nine primes still open in the literature are search "
"survivors", all(k in survivors for k in listed),
f"not survivors: {[k for k in listed if k not in survivors]}")
# ------------------------------------------------------------ section T
def section_t():
section("T TRANSPARENT RUNGS ARE TRANSPARENT MOVES")
ps = PRIMES_X[:2000]
Lf = {}
trans, shares = 0, {}
for k, p in enumerate(ps, start=1):
if k > 1:
# rung k transparent: lambda(p_k#) == lambda(p_(k-1)#)
new = dict(Lf)
for r, c in factor(p - 1).items():
if c > new.get(r, 0):
new[r] = c
trans += new == Lf
Lf = new
if k in (50, 500, 2000):
shares[k] = (trans, k - 1, round(trans / (k - 1), 3))
print(f" T1 transparent share (rungs, of k - 1, share) at k = 50, "
f"500, 2000: {shares}")
# ------------------------------------------------------------ section R
def menu_pick(mf, L, qmax):
"""The least lambda-raising move over the primes up to qmax, the
scan stopping once q reaches the least price found, since every
move at q costs at least q."""
best, bq = None, None
for q in growth.PRIMES:
if q > qmax or (best is not None and q >= best):
break
d = least_move(q, mf.get(q, 0), L)
if best is None or d < best:
best, bq = d, q
return bq, best
def deepen(mf, q, cost):
mf = dict(mf)
while cost > 1:
cost //= q
mf[q] = mf.get(q, 0) + 1
return mf
def rudder(mf, q):
L = lamf(mf)
if q == 2:
push = {2: max(3, L.get(2, 0) + 2) - mf.get(2, 0)}
return {k: v for k, v in push.items() if v > 0}, None
# q to depth v_q(lambda') + 1: lambda' has v_q = max(v_q(L), depth - 1)
depth = L.get(q, 0) + 1
push = {q: depth - mf.get(q, 0)} if depth > mf.get(q, 0) else {}
B = 1
for r in growth.PRIMES:
if r >= q:
break
t = 1
while r ** t <= q:
t += 1
B = lcm(B, (r - 1) * r ** (mf.get(r, 0) + t + 2))
g = 2
inv = pow(B, -1, q)
x = (1 + B * ((g - 1) * inv % q)) % (B * q)
Mv = value(mf)
while True:
if x > q and Mv % x and is_prime_mr(x):
KNOWN[x] = merge_add(factor(B), factor((x - 1) // B))
assert (x - 1) // B < 4 * 10 ** 8 and pocklington(x, KNOWN[x])
return push, x
x += B * q
def section_r():
section("R THE RUDDER")
rnd = random.Random(1400)
specials = [3 ** 15, 17 ** 6, 5 ** 10, 510510, 24, 240, 504, 30030,
2 ** 20, 1]
states = specials + [rnd.randrange(2, 10 ** 6) for _ in range(190)]
ok2 = 0
for M in states:
mf = factor(M) if M > 1 else {}
push, _ = rudder(mf, 2)
cur = merge_add(mf, push)
good = True
for _ in range(30):
L = lamf(cur)
q, cost = menu_pick(cur, L, 2)
if q != 2 or cost != 2:
good = False
break
cur = deepen(cur, 2, cost)
ok2 += good
check("R1 one push locks 200 states onto 2", ok2 == 200,
f"{ok2}/200, {len(set(states))} distinct")
okq, total = 0, 0
for M in (30, 3 ** 15, 2 ** 20, 510510, 17 ** 6):
mf = factor(M)
for q in (3, 5, 7, 13, 17):
total += 1
push, P = rudder(mf, q)
cur = merge_add(mf, push)
cur = merge_add(cur, {P: 1})
good = True
for _ in range(30):
L = lamf(cur)
qq, cost = menu_pick(cur, L, q)
if qq != q or cost != q:
good = False
break
cur = deepen(cur, q, cost)
okq += good
print(f" {M:>9} -> {q:>2}: push {push} * P = {P}"
f"{'' if good else ' MISSED'}")
check("R2 one push locks every (state, odd target) pair", okq == total,
f"{okq}/{total}")
def main():
t0 = time.time()
section_c()
section_w()
section_p()
section_a()
section_s()
section_t()
section_r()
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()