"""converse.py -- the doubling rung's converse: past k = 3, must a rung
of the tower with no totient collision bring a new prime into lambda?

QUESTION. At the rung k, p = p_k, n = p - 1 and Q the odd primes below
p, a totient collision is a pair of disjoint subsets A, B of Q with
prod_A (q - 1) = n * prod_B (q - 1) (a prime in both cancels). A prime
of n dividing no q - 1, q in Q (a new prime of lambda) forbids one.
Does a rung past k = 3 with no new prime always have one?

DESIGN.
(1) THE CAPACITY (proved). A collision forces, at every prime l,
v_l(n) <= cap_l(p), the sum over q in Q of v_l(q - 1): v_l(prod_A) =
v_l(n) + v_l(prod_B) >= v_l(n). A new prime is cap 0. So the converse
fails by a CAPACITY BREAK at an old l (v_l(n) > cap_l > 0), or with
capacity held at every l and no collision.
(2) AT l = 2 the break is p = 5 alone: with e = v_2(n), Bertrand puts
an odd prime in (2^j, 2^(j+1)] for j = 1..e-1, all below p, so cap_2
>= e - 1, and 5 adds one more at e >= 3; at e = 2 and p >= 13, 3 and 5
give 3; at e = 1, 3 gives 1.
(3) AT ODD l a break with l old needs v_l(n) >= 2: p is the m-th prime
= 1 mod l with v_l(p - 1) above the sum over the earlier ones, m >= 2,
each at least 1, so v_l(p - 1) >= m, p > 2l^m, and fewer than m primes
= 1 mod l lie below 2l^m + 1. At m = 2, p = 1 mod l^2 is the second
prime = 1 mod l, with at most one prime among the l - 1 candidates
2lj + 1 below 2l^2. A TRANSPLANT (independent candidates, prime with chance
about 1/ln l): about (l/ln l) e^(-l/ln l) / l, so an m = 2 break, if
any, comes at a small l.
(4) THE WITNESS SEARCH. Below 100 the exact listing: U, the set of
prod (q - 1) over subsets of Q, against n U. Past it, a depth-first
search on the residual exponent vector r (r = v(n) at the start, a
prime put in A subtracts v(q - 1), in B adds it): take the largest
prime l with r_l != 0, put an unused q = 1 mod l on the side that
lowers |r_l|, the candidates ordered by the largest prime of (q - 1)
other than l, four tried, deepening to 12 moves. TABLE, the eleven
odd primes 3..41 whose q - 1 is 7-smooth, is kept out of the search;
once r lives on {2, 3, 5, 7}, a table of all 3^11 signed choices
among them, the fewest primes kept per vector, closes it. Every
witness is verified exactly: A, B disjoint, inside Q, no repeat, the
products equal.

PREDICTIONS (frozen before the code).
C1 (proved) cap_2 >= v_2(n) at every odd p but 3 (2 new) and 5 (the
   break); printed to 10^6.
C2 (pattern, 85%) no capacity break at an odd old l, p < 10^6.
C3 (pattern, 85%) at every rung 7 <= p_k < X1 with capacity held at
   every l, the search finds a witness.
C4 (a guess, 60%) |A| + |B| <= 6 at every witnessed rung.

THE KILL, frozen. The script prints CAPACITY BREAKS at odd l with l
and every prime of n old, p < 10^6: past 5, "CONVERSE FALSE AT p =
..." (proved, the capacity being necessary). Over 7 <= p < X1 with
capacity held, UNWITNESSED [...]: nonempty, "UNDECIDED AT ...". Both
empty: "THE CONVERSE HOLDS AT EVERY RUNG p_k < X1".

CONTROLS, read first. K1 17's witness found and verified. K2 the exact
listing below 100: its collision rungs are exactly the rungs with
capacity held, the search (run with the exact listing off) witnesses
every one at 43 <= p < 100 (the table's primes below p), and its
non-collision rungs are 3, 5, 7, 11, 23, 29, 47, 53, 59, 83, the
doubling rung's list to k = 24. K3 the verifier rejects planted
witnesses: A = {17} at 17, a repeated prime, a product off by 2. K4
the capacity flags 5 at l = 2 and no other p < 10^6 there.

FINDINGS (from the printed run; the controls passed first). K1 prints
17's witness A = {3, 5, 13}, B = {7}; K2 (narrowed after the freeze
from k <= 20 to 43..97, the table's primes lying below p) the listing's
non-collision
rungs below 100 are 3, 5, 7, 11, 23, 29, 47, 53, 59, 83, the rest
exactly the capacity-held rungs, and the search witnesses all 8
collision rungs in 43..97; K3 and K4 hold, the capacity at 2 breaking
at 5 alone below 10^6 (C1). Below 10^6, 13143 of the 78497 odd p bring
a new prime, the first 3, 7, 11, 23, 29, 47, 53, 59, 83, 103, 107,
149; CAPACITY BREAKS at an odd l: none, with every prime old or with a
new one beside (C2 holds). Every one of the 65353 rungs 7 <= p_k <
10^6 with capacity held is witnessed, 14 by the listing, verified
exactly: UNWITNESSED none (C3 holds). THE PRINT: THE CONVERSE HOLDS AT
EVERY RUNG p_k < 1000000. The search's |A| + |B|, not minimal (a
depth-first find, the table minimal over its own primes), runs 2 to 14
(C4 FAILS): 4875,
17711, 16421, 10367, 6616, 3866, 2392, 1029, 959, 795, 293, 27 and 2
rungs at 2..14, the largest at p = 958931. At X1 = 10^3, 10^4, 10^5
the same verdict, 116, 946 and 7726 rungs witnessed. A witness read
by hand: 9311, n = 2 * 5 * 7^2 * 19, A = {1217, 113, 11, 19, 29, 31},
B = {3, 5, 13, 17, 37, 41}: 2^15 3^3 5^2 7^2 19 over 2^14 3^3 5.
So the converse holds to 10^6, and with it the sharper statement:
there, a rung has a collision exactly when the capacity holds at every
l, the capacity failing only at a new prime and at 5.
RUN RECORD. Rehearsal --x1 1000: 6/6, 0.8 s, peak 119.8 MB; --x1
10^4 0.8 s, 120.7 MB; --x1 10^5 1.3 s, 127.7 MB; the full run (X1 =
10^6) 6/6, 52.0 s, peak 188.4 MB under a memory guard.

    python converse.py [--x1 X1]     (X1 default 10^6)
"""

import sys
import time
from array import array
from itertools import product

N6 = 10 ** 6
TABLE = (3, 5, 7, 11, 13, 17, 19, 29, 31, 37, 41)
SMALL = (2, 3, 5, 7)
CHECKS = []


def check(name, ok, detail=""):
    CHECKS.append((name, bool(ok)))
    print(f"  [{'PASS' if ok else 'FAIL'}] {name}"
          + (f" -- {detail}" if detail else ""))


def spf_to(n):
    s = array("i", [0]) * (n + 1)
    for i in range(2, int(n ** 0.5) + 1):
        if s[i] == 0:
            for j in range(i * i, n + 1, i):
                if s[j] == 0:
                    s[j] = i
    return s


def factor(m, spf):
    out = {}
    while m > 1:
        r = spf[m] or m
        while m % r == 0:
            m //= r
            out[r] = out.get(r, 0) + 1
    return out


def capacity(primes, spf):
    """{p: (new primes of n, breaks [(l, v_l(n), cap_l)])} over the odd
    primes p, cap read before p joins Q."""
    cap, out = {}, {}
    for p in primes:
        if p == 2:
            continue
        f = factor(p - 1, spf)
        new = [l for l in f if cap.get(l, 0) == 0]
        brk = [(l, v, cap[l]) for l, v in f.items()
               if 0 < cap.get(l, 0) < v]
        out[p] = (new, brk)
        for l, v in f.items():
            cap[l] = cap.get(l, 0) + v
    return out


def verify(p, A, B, primes_set):
    if len(set(A)) != len(A) or len(set(B)) != len(B) or set(A) & set(B):
        return False
    if any(q == 2 or q >= p or q not in primes_set for q in A + B):
        return False
    a = b = 1
    for q in A:
        a *= q - 1
    for q in B:
        b *= q - 1
    return a == (p - 1) * b


def exact(p, Q):
    """A witness (A, B) from the listing of U over Q, or None."""
    U = {1: ()}
    for q in Q:
        for v, S in list(U.items()):
            w = v * (q - 1)
            if w not in U:
                U[w] = S + (q,)
    n = p - 1
    for v, S in U.items():
        if v * n in U:
            A, B = set(U[v * n]), set(S)
            c = A & B
            return sorted(A - c), sorted(B - c)
    return None


def vec(f):
    return tuple(f.get(r, 0) for r in SMALL)


def build_table(spf):
    vs = [vec(factor(q - 1, spf)) for q in TABLE]
    best = {}
    for signs in product((0, 1, -1), repeat=len(TABLE)):
        v = [0, 0, 0, 0]
        for s, x in zip(signs, vs):
            if s:
                for i in range(4):
                    v[i] += s * x[i]
        v = tuple(v)
        size = sum(1 for s in signs if s)
        if v not in best or size < best[v][0]:
            best[v] = (size, signs)
    return best


class Search:
    def __init__(self, spf, primes, table):
        self.spf, self.table = spf, table
        self.fac = {q: factor(q - 1, spf) for q in primes if q > 2}
        self.by = {}                      # l -> [q with l | q - 1]
        for q, f in self.fac.items():
            if q in TABLE:
                continue
            for l in f:
                self.by.setdefault(l, []).append(q)
        self.key = {}
        for q, f in self.fac.items():
            for l in f:
                others = [r for r in f if r != l]
                self.key[(q, l)] = (max(others) if others else 1, q)

    def close(self, r):
        """Table primes closing r on {2, 3, 5, 7}, or None."""
        if any(l not in SMALL for l in r):
            return None
        hit = self.table.get(vec(r))
        if hit is None:
            return None
        A = [q for q, s in zip(TABLE, hit[1]) if s == 1]
        B = [q for q, s in zip(TABLE, hit[1]) if s == -1]
        return A, B

    def run(self, p, depth=12, width=4):
        r0 = factor(p - 1, self.spf)
        for d in range(1, depth + 1):
            got = self.dfs(p, dict(r0), [], [], set(), d, width)
            if got:
                return got
        return None

    def dfs(self, p, r, A, B, used, d, width):
        c = self.close(r)
        if c is not None:
            return A + c[0], B + c[1]
        if d == 0:
            return None
        big = [l for l in r if l not in SMALL]
        l = max(big) if big else max(r)
        side = 1 if r[l] > 0 else -1     # 1: into A, -1: into B
        cand = [q for q in self.by.get(l, ()) if q < p and q not in used]
        cand.sort(key=lambda q: self.key[(q, l)])
        for q in cand[:width]:
            r2 = dict(r)
            for x, v in self.fac[q].items():
                r2[x] = r2.get(x, 0) - side * v
                if r2[x] == 0:
                    del r2[x]
            used.add(q)
            got = self.dfs(p, r2, A + [q] * (side == 1), B + [q] * (side == -1),
                           used, d - 1, width)
            used.discard(q)
            if got:
                return got
        return None


def main():
    x1 = 10 ** 6
    if "--x1" in sys.argv:
        x1 = int(float(sys.argv[sys.argv.index("--x1") + 1]))
    t0 = time.time()
    spf = spf_to(N6)
    primes = [p for p in range(2, N6) if spf[p] == 0]
    pset = set(primes)
    print(f"sieve to {N6}: {len(primes)} primes ({time.time() - t0:.1f} s)")
    cap = capacity(primes, spf)
    table = build_table(spf)
    S = Search(spf, [q for q in primes if q < x1], table)
    print(f"table: {len(table)} vectors ({time.time() - t0:.1f} s)")

    print("CONTROLS")
    w = exact(17, [q for q in primes if 2 < q < 17])
    check("K1 17's witness found and verified",
          w is not None and verify(17, w[0], w[1], pset), f"{w}")
    low = [p for p in primes if 2 < p < 100]
    ex, bad = {}, []
    for p in low:
        ex[p] = exact(p, [q for q in primes if 2 < q < p])
        if ex[p] is not None and not verify(p, *ex[p], pset):
            bad.append(p)
    nocol = [p for p in low if ex[p] is None]
    held = [p for p in low if not cap[p][0] and not cap[p][1]]
    srch = [p for p in low if p >= 43 and ex[p] is not None]
    miss = [p for p in srch if not (S.run(p) and verify(p, *S.run(p), pset))]
    check("K2 below 100 the collision rungs are the capacity-held rungs",
          not bad and sorted(set(low) - set(nocol)) == held,
          f"no collision at {nocol}")
    check("K2 the non-collision rungs are 3, 5, 7, 11, 23, 29, 47, 53, 59, 83",
          nocol == [3, 5, 7, 11, 23, 29, 47, 53, 59, 83])
    check("K2 the search witnesses every collision rung 43 <= p < 100",
          not miss, f"{len(srch)} rungs, missed {miss}")
    check("K3 the verifier rejects A = {17} at 17, a repeat, an off-by-2",
          not verify(17, [17], [], pset)
          and not verify(17, [5, 5], [], pset)
          and not verify(17, [3, 5, 13], [5], pset)
          and verify(17, [3, 5, 13], [7], pset))
    two = [p for p, (new, brk) in cap.items() if any(l == 2 for l, _, _ in brk)]
    check("K4 the capacity breaks at l = 2 at 5 alone, p < 10^6 (C1)",
          two == [5], f"{two[:5]}")
    if not all(ok for _, ok in CHECKS):
        print("CONTROL FAILED: nothing below is read.")
        raise SystemExit(1)

    print("THE CAPACITY TO 10^6")
    newr = [p for p, (new, _) in cap.items() if new]
    brk = [(p, b) for p, (new, bs) in cap.items() for b in bs
           if b[0] != 2 and not new]
    print(f"  rungs with a new prime: {len(newr)} of {len(cap)} odd p; "
          f"first {newr[:12]}")
    print(f"  CAPACITY BREAKS at odd l, every prime old: {brk[:10]}"
          f" ({len(brk)})")
    allb = [(p, b) for p, (new, bs) in cap.items() for b in bs if b[0] != 2]
    print(f"  breaks at odd l with a new prime beside: {allb[:6]} "
          f"({len(allb)})")

    print(f"THE WITNESSES, 7 <= p < {x1}")
    t1 = time.time()
    unw, sizes, ex_used = [], {}, 0
    for p in primes:
        if p < 7 or p >= x1:
            continue
        new, bs = cap[p]
        if new or bs:
            continue
        if p < 100:
            w = ex[p]
            ex_used += 1
        else:
            w = S.run(p)
        if w is None or not verify(p, w[0], w[1], pset):
            unw.append(p)
        else:
            sizes[p] = len(w[0]) + len(w[1])
    big = max(sizes, key=lambda p: (sizes[p], p)) if sizes else None
    hist = {}
    for v in sizes.values():
        hist[v] = hist.get(v, 0) + 1
    print(f"  {len(sizes)} witnessed ({ex_used} by the listing), "
          f"{time.time() - t1:.1f} s; |A| + |B| counts {sorted(hist.items())}"
          f", largest at p = {big}")
    print(f"  UNWITNESSED: {unw[:20]} ({len(unw)})")
    print(f"    C4: {'HOLDS' if all(v <= 6 for v in sizes.values()) else 'FAILS'}")

    print("THE PRINT")
    if [b for b in brk if b[0] > 5]:
        print(f"  CONVERSE FALSE AT p = {brk[0][0]}")
    elif unw:
        print(f"  UNDECIDED AT {unw[:10]}")
    else:
        print(f"  THE CONVERSE HOLDS AT EVERY RUNG p_k < {x1}")
    print(f"{sum(ok for _, ok in CHECKS)}/{len(CHECKS)} checks passed, "
          f"{time.time() - t0:.1f} s")
    raise SystemExit(0 if all(ok for _, ok in CHECKS) else 1)


if __name__ == "__main__":
    main()