"""Verification script for "Colossally Abundant Numbers and Nicolas' Second
Criterion" (F. Vega).

Written with the help of Claude Opus 5.5 (Anthropic); run by the author.

Parts 1-4 check every numerical inequality between explicit constants used in
the paper, with mpmath at 60 significant digits (or exactly, with fractions);
the computed left-hand side is printed.
  Part 1  Lemma Pboot, Lemma LlogL, Lemma corekernel, Theorem nicSA
          (counterexamples and superabundant counterexamples).
  Part 2  Lemmas theta, S2, T1, IN and the proof of Theorem 3.1
          (colossally abundant numbers with log xi >= 31).
  Part 3  Corollaries of Section 5 and Proposition NicRH.
  Part 4  Section "Nicolas' Second Criterion" (Lemmas Gmono, Elow and
          Theorems 1.1, 1.2, 1.3).
Parts 1-4 need only mpmath:  python verify_second_criterion.py --constants-only

Part 5 verifies inequality (2) at the primorials: for every prime q = p_k with
3 <= q <= X it checks c(q) < E(q), where
    c(q) = sum_{p <= q} log(p/(p-1)) - gamma - log log theta(q),
    E(q) = log(1 + (2 + tau)/(sqrt(theta(q)) log theta(q))),
    tau  = 2 + gamma - log(4 pi).
By Lemma 5.4 of the paper, c(p_k) < E(p_k) is inequality (2) for N_k, and by
Lemma 5.2 it then holds for every n with N_k <= n < N_{k+1}.  By Theorem 1.3,
if it holds for every p_k with e^31 <= p_k <= X, then Robin's inequality holds
for every n > 5040 with log n <= X(1 - log^-3 X) - log X.

Requirements of Part 5:  numpy, numba, mpmath; optionally primesieve, which is
        used when installed (conda install -c conda-forge python-primesieve)
Usage:  python verify_second_criterion.py --limit 1e14
        (runs Parts 1-4 first; --skip-constants skips them; --threads sets
        the number of threads, by default all cores)

Method of Part 5.  With primesieve installed, worker processes generate the
primes of each sub-block of 2^24 integers once, store them in a shared buffer,
compute the sums (pass 1), and check the inequality from the exact prefix sums
(pass 2).  Without primesieve, the integers up to X are processed in consecutive chunks;
each chunk is split into sub-blocks of 2^24 integers that are handled in
parallel.  A sub-block is sieved once (segmented sieve of Eratosthenes on the
odd numbers, after a wheel that removes the multiples of 3, 5, 7, 11, 13, 17;
the primes below 2^17 mark the sub-block in windows of 2^17 flags that fit in
the processor cache), and its prime flags are kept in memory.  A first parallel loop computes, for
each sub-block, the number of primes, sum log(p/(p-1)) and sum log p; the
prefix sums over all earlier sub-blocks are accumulated in mpmath with 40
significant digits.  A second parallel loop runs through the primes of each
sub-block in increasing order and checks the inequality in batches of 64
consecutive primes q_a < ... < q_b: since sum log(p/(p-1)) and theta increase
and E decreases with q, every prime of the batch satisfies c(q) < E(q) if
    S(q_b) - gamma - log log theta(q_a) + 10^-13 < E(q_b),
and otherwise each prime of the batch is checked individually.

Precision.  log(p/(p-1)) is computed as -log1p(-1/p) for p < 10^5 and by its
Taylor series to order p^-4 for p >= 10^5 (truncation error < p^-5).  For
p >= 10^11, log p is computed as log B + log(1 + (p - B)/B), where B is the
first odd number of the sub-block, with the Taylor series of log(1 + r) to
order r^5 (r < 1.7e-4, truncation error < 4e-24).  Inside a
sub-block the sums are accumulated in float64; across sub-blocks and chunks in
mpmath.  The margin E(q) - c(q) is evaluated with an absolute error of a few
units of 10^-15; margins below 10^-13 are reported as unresolved and are not
counted as verified.  The script reports a lower bound for the minimum of the
normalized margin (E(q) - c(q)) sqrt(q) log^2 q.

An interrupted run is resumed from the checkpoint file with the same command.
"""

import argparse
import json
import math
import os
import sys
import time

try:
    import numpy as np
    from numba import njit, prange, set_num_threads, get_num_threads
except ImportError:          # Parts 1-4 do not need numpy or numba
    np = None
    njit = None
try:
    import primesieve.numpy as psnp      # optional: faster prime generation
except ImportError:
    psnp = None

SUB = 1 << 24                # integers per sub-block
NSUB = 32                    # sub-blocks per chunk
BATCH = 64                   # primes per batch in the check
WIN = 1 << 17                # sieve window: 2^17 flags (2^18 integers, 128 KB)
SAFE = 1e-13                 # margins below this are not counted as verified
K_BROUGHAN = 120569          # Broughan, Corollary 5.35: n >= N_120569
WHEEL = (3, 5, 7, 11, 13, 17)


if njit is not None:

    @njit(cache=True)
    def _term(x):
        """log(x/(x-1))."""
        if x < 100000.0:
            return -math.log1p(-1.0 / x)
        r = 1.0 / x
        return r + r * r * (0.5 + r * (1.0 / 3.0 + r * 0.25))

    @njit(cache=True)
    def _log(x, B, lB):
        """log x.  For B >= 10^11 and B <= x < B + SUB, r = (x - B)/B < 1.7e-4
        and the Taylor series of log(1 + r) to order r^5 has truncation error
        below r^6/6 < 4e-24; otherwise math.log is used."""
        if B < 1e11:
            return math.log(x)
        r = (x - B) / B
        return lB + r * (1.0 - r * (0.5 - r * (1.0 / 3.0 - r * (0.25 - r * 0.2))))

    @njit(parallel=True, cache=True)
    def sieve_chunk(lo, nsub, base, nsmall, pat, flags, cnt, ssum, tsum):
        """Sieve the sub-blocks [lo + i SUB, lo + (i+1) SUB), i < nsub, keep the
        flags of the odd numbers, and return count, sum log(p/(p-1)), theta."""
        n = SUB // 2
        P = pat.shape[0]
        # 1. wheel pattern, small primes (p < WIN) window by window so that the
        #    marked part stays in the cache, and large primes, sub-block by
        #    sub-block
        for i in prange(nsub):
            b = lo + i * SUB
            s = b + 1
            hi = b + SUB
            f = flags[i * n:(i + 1) * n]
            j = ((s - 1) // 2) % P
            t = 0
            while t < n:
                take = min(P - j, n - t)
                f[t:t + take] = pat[j:j + take]
                t += take
                j = 0
            if s <= 17:
                for w in (3, 5, 7, 11, 13, 17):
                    if w >= s:
                        f[(w - s) // 2] = 1
                if s == 1:
                    f[0] = 0                # 1 is not prime
            nxt = np.empty(nsmall, dtype=np.int64)
            for j in range(nsmall):
                p = base[j]
                if p * p >= hi:
                    nxt[j] = n
                    continue
                m = ((s + p - 1) // p) * p
                if m < p * p:
                    m = p * p
                if m % 2 == 0:
                    m += p
                nxt[j] = (m - s) // 2
            w0 = 0
            while w0 < n:
                w1 = min(w0 + WIN, n)
                for j in range(nsmall):
                    p = base[j]
                    q = nxt[j]
                    while q < w1:
                        f[q] = 0
                        q += p
                    nxt[j] = q
                w0 = w1
            # large primes (p >= WIN): few marks per sub-block, marked directly
            for j in range(nsmall, base.shape[0]):
                p = base[j]
                if p * p >= hi:
                    break
                m = ((s + p - 1) // p) * p
                if m < p * p:
                    m = p * p
                if m % 2 == 0:
                    m += p
                for q in range((m - s) // 2, n, p):
                    f[q] = 0
        # 2. count, sum log(p/(p-1)) and theta per sub-block, reading the flags
        #    8 bytes at a time
        for i in prange(nsub):
            s = lo + i * SUB + 1
            B = float(s)
            lB = math.log(B)
            fw = flags[i * n:(i + 1) * n].view(np.uint64)
            c = 0
            S = 0.0
            T = 0.0
            for w in range(fw.shape[0]):
                if fw[w] != 0:
                    for q in range(8 * w, 8 * w + 8):
                        if flags[i * n + q]:
                            x = float(s + 2 * q)
                            c += 1
                            S += _term(x)
                            T += _log(x, B, lB)
            cnt[i] = c
            ssum[i] = S
            tsum[i] = T

    @njit(cache=True)
    def _margin(S, T, gamma, two_tau):
        return math.log1p(two_tau / (math.sqrt(T) * math.log(T))) - (S - gamma - math.log(math.log(T)))

    @njit(parallel=True, cache=True)
    def check_chunk(lo, nsub, flags, S0, T0, k0, gamma, two_tau, kb, e31,
                    min_kb, min_e31, nfail, maxfailk, firstfail_k, firstfail_p, nunres):
        """Check c(q) < E(q) at every odd prime q of the chunk."""
        n = SUB // 2
        for i in prange(nsub):
            s = lo + i * SUB + 1
            B = float(s)
            lB = math.log(B)
            fw = flags[i * n:(i + 1) * n].view(np.uint64)
            S = S0[i]
            T = T0[i]
            k = k0[i]
            bq = np.empty(BATCH, dtype=np.float64)
            bS = np.empty(BATCH, dtype=np.float64)
            bT = np.empty(BATCH, dtype=np.float64)
            bk = np.empty(BATCH, dtype=np.int64)
            nb = 0
            mkb = np.inf
            m31 = np.inf
            nf = 0
            mfk = -1
            ffk = -1
            ffp = -1.0
            nu = 0
            nw = fw.shape[0]
            for w in range(nw + 1):
                last = w == nw
                if not last and fw[w] != 0:
                    for q in range(8 * w, 8 * w + 8):
                        if flags[i * n + q]:
                            x = float(s + 2 * q)
                            k += 1
                            S += _term(x)
                            T += _log(x, B, lB)
                            bq[nb] = x
                            bS[nb] = S
                            bT[nb] = T
                            bk[nb] = k
                            nb += 1
                            if nb == BATCH:
                                # process a full batch (same code as below)
                                lb = math.log1p(two_tau / (math.sqrt(bT[nb - 1]) * math.log(bT[nb - 1]))) - (bS[nb - 1] - gamma - math.log(math.log(bT[0])))
                                if lb > SAFE:
                                    v = lb * math.sqrt(bq[0]) * math.log(bq[0]) ** 2
                                    if bk[nb - 1] >= kb and v < mkb:
                                        mkb = v
                                    if bq[nb - 1] >= e31 and v < m31:
                                        m31 = v
                                else:
                                    for jj in range(nb):
                                        m = _margin(bS[jj], bT[jj], gamma, two_tau)
                                        if m <= 0.0:
                                            if bk[jj] > mfk:
                                                mfk = bk[jj]
                                            if bk[jj] >= kb:
                                                nf += 1
                                                if ffk < 0:
                                                    ffk = bk[jj]
                                                    ffp = bq[jj]
                                        elif m < SAFE:
                                            if bk[jj] >= kb:
                                                nu += 1
                                        else:
                                            v = m * math.sqrt(bq[jj]) * math.log(bq[jj]) ** 2
                                            if bk[jj] >= kb and v < mkb:
                                                mkb = v
                                            if bq[jj] >= e31 and v < m31:
                                                m31 = v
                                nb = 0
                if last and nb > 0:
                    lb = math.log1p(two_tau / (math.sqrt(bT[nb - 1]) * math.log(bT[nb - 1]))) - (bS[nb - 1] - gamma - math.log(math.log(bT[0])))
                    if lb > SAFE:
                        v = lb * math.sqrt(bq[0]) * math.log(bq[0]) ** 2
                        if bk[nb - 1] >= kb and v < mkb:
                            mkb = v
                        if bq[nb - 1] >= e31 and v < m31:
                            m31 = v
                    else:
                        for jj in range(nb):
                            m = _margin(bS[jj], bT[jj], gamma, two_tau)
                            if m <= 0.0:
                                if bk[jj] > mfk:
                                    mfk = bk[jj]
                                if bk[jj] >= kb:
                                    nf += 1
                                    if ffk < 0:
                                        ffk = bk[jj]
                                        ffp = bq[jj]
                            elif m < SAFE:
                                if bk[jj] >= kb:
                                    nu += 1
                            else:
                                v = m * math.sqrt(bq[jj]) * math.log(bq[jj]) ** 2
                                if bk[jj] >= kb and v < mkb:
                                    mkb = v
                                if bq[jj] >= e31 and v < m31:
                                    m31 = v
                    nb = 0
            min_kb[i] = mkb
            min_e31[i] = m31
            nfail[i] = nf
            maxfailk[i] = mfk
            firstfail_k[i] = ffk
            firstfail_p[i] = ffp
            nunres[i] = nu



if njit is not None:

    @njit(cache=True)
    def sums_arr(p, B, lB):
        """count, sum log(q/(q-1)) and sum log q over the primes in p."""
        S = 0.0
        T = 0.0
        for j in range(p.shape[0]):
            x = p[j]
            S += _term(x)
            T += _log(x, B, lB)
        return p.shape[0], S, T

    @njit(cache=True)
    def check_arr(p, S, T, k, B, lB, gamma, two_tau, kb, e31):
        """Check c(q) < E(q) at the primes in p (increasing), starting from the
        prefix sums S, T and the index k of the prime before p[0]."""
        bq = np.empty(BATCH, dtype=np.float64)
        bS = np.empty(BATCH, dtype=np.float64)
        bT = np.empty(BATCH, dtype=np.float64)
        bk = np.empty(BATCH, dtype=np.int64)
        nb = 0
        mkb = np.inf
        m31 = np.inf
        nf = 0
        mfk = -1
        ffk = -1
        ffp = -1.0
        nu = 0
        npr = p.shape[0]
        for j in range(npr + 1):
            if j < npr:
                x = p[j]
                k += 1
                S += _term(x)
                T += _log(x, B, lB)
                bq[nb] = x
                bS[nb] = S
                bT[nb] = T
                bk[nb] = k
                nb += 1
            if nb == BATCH or (j == npr and nb > 0):
                lb = math.log1p(two_tau / (math.sqrt(bT[nb - 1]) * math.log(bT[nb - 1]))) - (bS[nb - 1] - gamma - math.log(math.log(bT[0])))
                if lb > SAFE:
                    v = lb * math.sqrt(bq[0]) * math.log(bq[0]) ** 2
                    if bk[nb - 1] >= kb and v < mkb:
                        mkb = v
                    if bq[nb - 1] >= e31 and v < m31:
                        m31 = v
                else:
                    for jj in range(nb):
                        m = _margin(bS[jj], bT[jj], gamma, two_tau)
                        if m <= 0.0:
                            if bk[jj] > mfk:
                                mfk = bk[jj]
                            if bk[jj] >= kb:
                                nf += 1
                                if ffk < 0:
                                    ffk = bk[jj]
                                    ffp = bq[jj]
                        elif m < SAFE:
                            if bk[jj] >= kb:
                                nu += 1
                        else:
                            v = m * math.sqrt(bq[jj]) * math.log(bq[jj]) ** 2
                            if bk[jj] >= kb and v < mkb:
                                mkb = v
                            if bq[jj] >= e31 and v < m31:
                                m31 = v
                nb = 0
        return mkb, m31, nf, mfk, ffk, ffp, nu


def _block_primes(b):
    """The odd primes of sub-block b, i.e. in [b SUB, (b+1) SUB), as float64."""
    lo = b * SUB
    q = psnp.primes(lo, lo + SUB - 1)
    if lo == 0:
        q = q[q > 2]                     # the prime 2 is in the initial state
    return q.astype(np.float64), float(lo + 1)


# Shared buffer for the primes of one round: pass 1 stores the primes of each
# sub-block in its slot, and pass 2 reads them instead of sieving again.  A
# slot holds MAXP primes; by the Brun-Titchmarsh inequality of Montgomery and
# Vaughan, an interval of length y = 2^24 contains fewer than 2y/log y < 2.02e6
# primes, and [0, 2^24) contains 1077871 primes.
MAXP = 2_100_000
_SHM = {}


def _slot(name, slot):
    from multiprocessing import shared_memory
    if name not in _SHM:
        shm = shared_memory.SharedMemory(name=name)
        _SHM.clear()
        _SHM[name] = (shm, np.ndarray((shm.size // 8,), dtype=np.float64, buffer=shm.buf))
    return _SHM[name][1][slot * MAXP:(slot + 1) * MAXP]


def _ps_pass1(job):
    b, name, slot = job
    q, B = _block_primes(b)
    n = q.shape[0]
    stored = n <= MAXP
    if stored:
        _slot(name, slot)[:n] = q
    c, S, T = sums_arr(q, B, math.log(B))
    return c, S, T, stored


def _ps_pass2(job):
    b, name, slot, n, stored, S0, T0, k0, gamma, two_tau, e31 = job
    if stored:
        q = _slot(name, slot)[:n]
        B = float(b * SUB + 1)
    else:
        q, B = _block_primes(b)
    return check_arr(q, S0, T0, k0, B, math.log(B), gamma, two_tau, K_BROUGHAN, e31)


def wheel_pattern():
    """pat[j] = 1 iff 1 + 2j is divisible by none of 3, 5, 7, 11, 13, 17."""
    P = 1
    for w in WHEEL:
        P *= w
    x = 1 + 2 * np.arange(P, dtype=np.int64)
    pat = np.ones(P, dtype=np.uint8)
    for w in WHEEL:
        pat[x % w == 0] = 0
    return pat


def base_primes(limit):
    """Odd primes p with 19 <= p <= limit (limit is about sqrt(X))."""
    flags = np.ones(limit + 1, dtype=bool)
    flags[:2] = False
    for i in range(2, int(limit ** 0.5) + 1):
        if flags[i]:
            flags[i * i::i] = False
    p = np.nonzero(flags)[0].astype(np.int64)
    return p[p >= 19]


def constant_checks():
    """Parts 1-4: every numerical inequality between explicit constants of the
    paper, checked with mpmath at 60 digits or exactly with fractions."""
    from fractions import Fraction as D
    from math import gcd
    from mpmath import mp, mpf, euler, exp, log, pi, sqrt
    saved = mp.dps
    mp.dps = 60
    results = []

    def check(label, ok, value=None):
        results.append(bool(ok))
        detail = f"   ({mp.nstr(value, 15)})" if value is not None else ""
        print(f"[{'PASS' if ok else 'FAIL'}] {label}{detail}")

    def eps(P):
        """Axler's epsilon(P) = 1/(20 P^3) + 3/(16 P^4)."""
        return 1 / (20 * P ** 3) + mpf(3) / (16 * P ** 4)

    eg = exp(euler)
    L31 = mpf(31)

    # ---------------------------------------------------------------------------
    print("=== Part 1: counterexamples and superabundant counterexamples ===")
    LMP = mpf("13.11485") * log(10) + log(log(10))
    check("loglog(10^(10^13.11485)) > 31.032", LMP > mpf("31.032"), LMP)
    x0 = mpf(46909038)
    check("log(46909038) < 17.6638", log(x0) < mpf("17.6638"), log(x0))
    v = 1 / (1 - eps(log(x0)))
    check("(1 - eps(log 46909038))^{-1} < 1.000011", v < mpf("1.000011"), v)
    check("17.6638 * 1.000011 < 31.032", D("17.6638") * D("1.000011") < D("31.032"))
    v = mpf("31.032") / mpf("1.000011")
    check("31.032/1.000011 > 31.0316", v > mpf("31.0316"), v)
    v = 1 / (1 - eps(mpf("31.0316")))
    check("(1 - eps(31.0316))^{-1} < 1.000002", v < mpf("1.000002"), v)
    v = mpf("31.032") / mpf("1.000002")
    check("31.032/1.000002 > 31.0319", v > mpf("31.0319"), v)
    P1 = mpf("31.0319")
    v = (mpf("0.05") + mpf(3) / (16 * P1)) / (1 - eps(P1))
    check("(1/20 + 3/(16*31.0319))/(1 - eps(31.0319)) < 0.0562", v < mpf("0.0562"), v)
    Q0 = mpf("31.03")
    v = exp(mpf("0.0562") / Q0 ** 2) * (1 + mpf("0.0562") / Q0 ** 3)
    check("e^(0.0562/31.03^2) (1 + 0.0562/31.03^3) < 1.0000603", v < mpf("1.0000603"), v)
    v = exp(mpf("15.515"))
    check("e^15.515 > 5.47e6", v > mpf("5.47e6"), v)
    v = 1 - mpf("1.94") / sqrt(mpf("5.47e6"))
    check("1 - 1.94/sqrt(5.47e6) > 0.99917", v > mpf("0.99917"), v)
    v = mpf("0.99917") / mpf("1.0000603")
    check("0.99917/1.0000603 > 0.9991", v > mpf("0.9991"), v)
    v = eg * mpf("31.032")
    check("e^gamma * 31.032 > 55", v > 55, v)
    phi = lambda m: sum(1 for j in range(1, m + 1) if gcd(j, m) == 1)
    v = max(mpf(m) / phi(m) for m in range(1, 16))
    check("max m/phi(m) over 1 <= m <= 15 equals 3", v == 3, v)

    # ---------------------------------------------------------------------------
    print("\n=== Part 2: colossally abundant numbers with log xi >= 31 ===")
    h = log(2) / 2
    check("e^31 > 10^9 + 7 and e^31 > 89967803", exp(L31) > 10 ** 9 + 7 and exp(L31) > 89967803, exp(L31))
    v = 1 - log(2) / (2 * L31)
    check("1 - log 2/(2*31) > 0.98882", v > mpf("0.98882"), v)
    v = sqrt(2) * mpf("0.98882")
    check("sqrt(2) * 0.98882 > 1.39838", v > mpf("1.39838"), v)
    v = sqrt(mpf("1.39838"))
    check("sqrt(1.39838) > 1.18253", v > mpf("1.18253"), v)
    v = mpf("1.94") * L31 * exp(-L31 / 4) / mpf("1.18253")
    check("1.94 * 31 * e^(-31/4) / 1.18253 < 0.022", v < mpf("0.022"), v)
    v = 1 / log(mpf(10) ** 19) ** 3
    check("1/log^3(10^19) < 0.000012", v < mpf("0.000012"), v)
    v = 2 / log(mpf(10) ** 19) ** 2
    check("2 log(10^19)/log^3(10^19) < 0.022", v < mpf("0.022"), v)
    v = mpf(8) / L31 ** 2
    check("8/31^2 < 0.022", v < mpf("0.022"), v)
    v = -log(1 - log(2) / (2 * L31))
    check("-log(1 - log 2/62) < 0.011306", v < mpf("0.011306"), v)
    v = 2 * (h - mpf("0.011306"))
    check("2*(log 2/2 - 0.011306) >= 0.670535", v >= mpf("0.670535"), v)
    v = log(2) - mpf("0.323")
    check("log 2 - 0.323 < 0.370148", v < mpf("0.370148"), v)
    v = mpf("0.670535") - h - h * mpf("0.670535") / L31
    check("0.670535 - log2/2 - (log2/2)(0.670535)/31 > 0.316464", v > mpf("0.316464"), v)
    v = mpf("0.316464") - mpf("0.316464") ** 2 / L31
    check("0.316464 - 0.316464^2/31 > 0.313233", v > mpf("0.313233"), v)
    v = 2 * (1 - (mpf("0.370148") + log(2)) / L31)
    check("2*(1 - (0.370148 + log 2)/31) > 1.9314", v > mpf("1.9314"), v)
    v = D("0.066") + D("0.370148") + 2
    check("0.066 + 0.370148 + 2 <= 2.436148", v <= D("2.436148"), mpf(v.numerator) / v.denominator)
    v = mpf("1.0022") * L31 * exp(-L31 / 2) / sqrt(2)
    check("1.0022 * 31 * e^(-31/2)/sqrt(2) < 4.08e-6", v < mpf("4.08e-6"), v)
    check("1 + 3*0.022/31 < 1.0022", 1 + 3 * mpf("0.022") / L31 < mpf("1.0022"))
    check("2.436148 + 4.08e-6 < 2.43616", D("2.436148") + D("4.08e-6") < D("2.43616"))
    v = 8 * (1 + mpf("0.022") / L31)
    check("8*(1 + 0.022/31) < 8.006", v < mpf("8.006"), v)
    v = mpf("8.006") / L31
    check("8.006/31 < 0.258259", v < mpf("0.258259"), v)
    v = D("0.313233") - D("0.066") + D("1.9314") - D("0.258259")
    check("0.313233 - 0.066 + 1.9314 - 0.258259 >= 1.920374", v >= D("1.920374"), mpf(v.numerator) / v.denominator)
    check("0.022 + log 2/2 <= 0.368574", mpf("0.022") + h <= mpf("0.368574"), mpf("0.022") + h)
    check("0.323 - 0.022 >= 0.301", D("0.323") - D("0.022") >= D("0.301"))
    check("e^(31/3) > 853 and > 1418", exp(L31 / 3) > 1418, exp(L31 / 3))
    check("0.945 * e^(31/3) > 31", mpf("0.945") * exp(L31 / 3) > L31, mpf("0.945") * exp(L31 / 3))
    v = mpf("1.000012") * mpf("1.9769") / sqrt(2)
    check("1.000012 * 1.9769/sqrt(2) < 1.397905", v < mpf("1.397905"), v)
    v = mpf("1.397905") * L31 * exp(-L31 / 6)
    check("1.397905 * 31 * e^(-31/6) < 0.24717", v < mpf("0.24717"), v)
    check("0.301 - 0.24717 >= 0.0538", D("0.301") - D("0.24717") >= D("0.0538"))
    v = 1 / L31 ** 2 + sqrt(2) * L31 * exp(-L31 / 2)
    check("1/31^2 + sqrt(2)*31*e^(-31/2) < 0.0010488", v < mpf("0.0010488"), v)
    v = mpf("0.0010488") / L31
    check("0.0010488/31 < 0.0000339", v < mpf("0.0000339"), v)
    v = mpf("0.0010488") + mpf("0.0000339") + mpf("0.0010488") * mpf("0.0000339") / L31
    check("0.0010488 + 0.0000339 + (0.0010488*0.0000339)/31 < 0.001085", v < mpf("0.001085"), v)
    v = 1 / L31 ** 2 + mpf("1.0001") / L31 ** 3
    check("1/31^2 + 1.0001/31^3 < 0.00108", v < mpf("0.00108"), v)
    v = 1 / (1 - L31 ** -3)
    check("1/(1 - 31^-3) < 1.0001 (so -log(1 - x) <= 1.0001 x)", v < mpf("1.0001"), v)
    check("0.368574 + 0.001085 <= 0.369659", D("0.368574") + D("0.001085") <= D("0.369659"))
    check("0.0538 - 0.00108 >= 0.05272", D("0.0538") - D("0.00108") >= D("0.05272"))
    v = mpf("0.086") / (1 - mpf(1418) ** -3)
    check("0.086/(1 - 1418^-3) < 0.0861", v < mpf("0.0861"), v)
    v = 3 * mpf("1.26") * mpf(3) ** (mpf(1) / 3)
    check("3 * 1.26 * 3^(1/3) < 5.4518", v < mpf("5.4518"), v)
    v = mpf("5.4518") / L31 * (1 + mpf(10) ** -12)
    check("(5.4518/31)(1 + 1e-12) < 0.17587", v < mpf("0.17587"), v)
    v = mpf("0.0861") + mpf("0.17587") + exp(-L31 / 3)
    check("0.0861 + 0.17587 + e^(-31/3) < 0.26201", v < mpf("0.26201"), v)
    v = mpf("0.26201") * L31 ** 2 * exp(-L31 / 6) / sqrt(2)
    check("0.26201 * 31^2 * e^(-31/6)/sqrt(2) < 1.0155", v < mpf("1.0155"), v)
    v = 2 * mpf("1.39838") ** -2 * exp(-L31) * L31
    check("2 xi_2^-2 * 31 < 1e-4 with xi_2 >= 1.39838 e^(31/2)", v < mpf("1e-4"), v)
    check("1.0155 + 1e-4 <= 1.0156", D("1.0155") + D("1e-4") <= D("1.0156"))
    check("0.369659 + 2.43616 <= 2.805819", D("0.369659") + D("2.43616") <= D("2.805819"))
    check("0.05272 + 1.920374 - 1.0156 >= 0.957494",
          D("0.05272") + D("1.920374") - D("1.0156") >= D("0.957494"))
    v = mpf("0.5") / L31 ** 2 + 1 / L31 ** 3
    check("1/(2*31^2) + 1/31^3 < 0.000554", v < mpf("0.000554"), v)
    v = mpf("0.957494") * (1 - L31 ** -4)
    check("0.957494 (1 - 31^-4) > 0.9574", v > mpf("0.9574"), v)
    check("2.805819 + 2*0.000554 < 2.8070", D("2.805819") + 2 * D("0.000554") < D("2.8070"))
    v = mpf("0.9574") * sqrt(2)
    check("0.9574 sqrt(2) > 1.353", v > mpf("1.353"), v)
    v = mpf("2.8070") * sqrt(2)
    check("2.8070 sqrt(2) < 3.970", v < mpf("3.970"), v)
    check("0.9574/2 >= 0.4787 and 2.8070/2 <= 1.4035",
          D("0.9574") / 2 >= D("0.4787") and D("2.8070") / 2 <= D("1.4035"))

    # ---------------------------------------------------------------------------
    print("\n=== Part 3: corollaries ===")
    v = 2 * sqrt(2) * (1 - mpf("1.4035") / mpf("31.0319"))
    check("2 sqrt(2) (1 - 1.4035/31.0319) > 2.70", v > mpf("2.70"), v)
    check("e^31.0319 > 10^9", exp(mpf("31.0319")) > mpf(10) ** 9, exp(mpf("31.0319")))
    tau = 2 + euler - log(4 * pi)
    check("tau = 2 + gamma - log(4 pi) < 0.0462", tau < mpf("0.0462"), tau)
    check("2 + tau < 2.0462 < 2.70", 2 + tau < mpf("2.0462") < mpf("2.70"), 2 + tau)
    v = 2 + tau - 2 * sqrt(2) + 2 * sqrt(2) * mpf("1.4035") / L31
    check("2 + tau - 2 sqrt(2) + 2 sqrt(2) 1.4035/31 < -0.654", v < mpf("-0.654"), v)
    check("1.353 - 2.062 = -0.709", D("1.353") - D("2.062") == D("-0.709"))
    check("3.970 - 0.055 = 3.915", D("3.970") - D("0.055") == D("3.915"))
    v = 2 * sqrt(2) - 2 - tau
    print(f"      2 sqrt(2) - 2 - tau = {mp.nstr(v, 15)}")

    # ---------------------------------------------------------------------------
    print("\n=== Part 4: Nicolas' second criterion ===")
    v = ((2 + tau) / 2) ** 2
    check("((2 + tau)/2)^2 < 1.0468 < log 3", v < mpf("1.0468") < log(3), v)
    v = mpf("2.0462") * (1 / (2 * L31) + 1 / L31 ** 2) + mpf("2.0462") ** 2 / 2 * exp(-L31 / 2)
    check("2.0462 (1/62 + 1/31^2) + (2.0462^2/2) e^(-31/2) < 0.036", v < mpf("0.036"), v)
    check("1.353 - 0.036 >= 1.317", D("1.353") - D("0.036") >= D("1.317"))
    a = L31 ** -3
    b = L31 ** -4 / (1 - L31 ** -3)
    v = (1 + (1 / L31) / (1 - L31 ** -3)) / (1 - a - b)
    check("(1 + 31^-1/(1 - 31^-3))/(1 - 31^-3 - 31^-4/(1 - 31^-3)) < 1.0323", v < mpf("1.0323"), v)
    v = mpf("2.0462") * mpf("1.0323") / L31 ** 2
    check("2.0462 * 1.0323/31^2 < 0.0022", v < mpf("0.0022"), v)
    check("3.970 + 0.0022 <= 3.973", D("3.970") + D("0.0022") <= D("3.973"))
    v = 2 * sqrt(2) - 2 - tau - mpf("3.973") / L31
    check("2 sqrt(2) - 2 - tau - 3.973/31 > 0.654", v > mpf("0.654"), v)
    v = 2 + tau + mpf("0.654")
    check("2 + tau + 0.654 > 2.70", v > mpf("2.70"), v)
    v = mpf(10) ** 8 * (1 - log(mpf(10) ** 8) ** -3) / log(mpf(10) ** 8)
    check("10^8 (1 - log^-3 10^8)/log 10^8 > 5e6", v > 5 * mpf(10) ** 6, v)
    v = mpf(10) ** mpf("13.11485") * log(10)
    check("10^13.11485 * log 10 > 2.9996e13", v > mpf("2.9996e13"), v)
    Xt = mpf("3.01e13")
    v = Xt * (1 - log(Xt) ** -3) - log(Xt)
    check("X (1 - log^-3 X) - log X > 10^13.11485 log 10 for X = 3.01e13", v > mpf(10) ** mpf("13.11485") * log(10), v)

    print(f"\nParts 1-4: {sum(results)}/{len(results)} checks passed")
    mp.dps = saved
    return all(results)


def load(path):
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    return {}


def save(path, data):
    tmp = path + ".tmp"
    with open(tmp, "w") as f:
        json.dump(data, f, indent=1)
    os.replace(tmp, path)


def part5(args):
    from mpmath import mp, mpf, euler, log as mlog, pi as mpi
    mp.dps = 40
    if args.threads:
        set_num_threads(args.threads)
    gamma = float(euler)
    two_tau = float(2 + (2 + euler - mlog(4 * mpi)))
    e31 = math.exp(31.0)
    X = int(args.limit)
    Xeff = -(-(X + 1) // SUB) * SUB - 1          # last integer covered
    nblocks = (Xeff + 1) // SUB
    base = base_primes(math.isqrt(Xeff) + 1)
    nsmall = int(np.searchsorted(base, WIN))     # primes p < WIN
    pat = wheel_pattern()

    st = load(args.checkpoint)
    if st.get("limit") != Xeff or st.get("sub") != SUB:
        st = {"limit": Xeff, "sub": SUB, "next_block": 0, "k": 1,
              "S": str(mlog(2)), "T": str(mlog(2)),   # the prime 2
              "min_kb": None, "min_kb_q_block": None, "min_e31": None,
              "nfail": 0, "maxfailk": None, "firstfail": None, "nunres": 0,
              "elapsed": 0.0}
    k = st["k"]
    S = mpf(st["S"])
    T = mpf(st["T"])
    blk = st["next_block"]
    t_start = time.time() - st["elapsed"]
    print(f"Part 5: X = {X} (sieved up to {Xeff}), {nblocks} sub-blocks of {SUB} integers, "
          f"{get_num_threads()} threads; starting at sub-block {blk}", flush=True)

    blk_start = blk
    t_session = time.time()
    last_save = time.time()

    def record(i_blk, mkb, m31, nf, mfk, ffk, ffp, nu):
        if math.isfinite(mkb) and (st["min_kb"] is None or mkb < st["min_kb"]):
            st["min_kb"] = float(mkb)
            st["min_kb_q_block"] = [i_blk * SUB, (i_blk + 1) * SUB - 1]
        if math.isfinite(m31) and (st["min_e31"] is None or m31 < st["min_e31"]):
            st["min_e31"] = float(m31)
        st["nfail"] += int(nf)
        if mfk >= 0 and (st["maxfailk"] is None or mfk > st["maxfailk"]):
            st["maxfailk"] = int(mfk)
        if ffk >= 0 and st["firstfail"] is None:
            st["firstfail"] = [int(ffk), int(ffp)]
        st["nunres"] += int(nu)

    def progress(force=False):
        nonlocal last_save
        st.update(next_block=blk, k=k, S=str(S), T=str(T), elapsed=time.time() - t_start)
        if force or time.time() - last_save > 60:
            save(args.checkpoint, st)
            last_save = time.time()
            rate = (blk - blk_start) / max(time.time() - t_session, 1e-9)
            eta = (nblocks - blk) / rate if rate > 0 else 0
            print(f"  {100 * blk / nblocks:6.2f}%  up to {blk * SUB:.4e}  primes {k}  "
                  f"rate {rate * SUB * 3600:.3e} integers/h  remaining {eta / 3600:.2f} h", flush=True)

    if psnp is not None and not args.numba_sieve:
        # primesieve engine: worker processes generate the primes of each
        # sub-block; pass 1 sums, pass 2 checks with the exact prefix sums
        from multiprocessing import Pool, shared_memory
        workers = args.workers or os.cpu_count() or 1
        R = workers * 4
        shm = shared_memory.SharedMemory(create=True, size=R * MAXP * 8)
        print(f"  engine: primesieve, {workers} worker processes, "
              f"{R * MAXP * 8 / 2**20:.0f} MB shared prime buffer", flush=True)
        try:
            with Pool(workers) as pool:
                while blk < nblocks:
                    blocks = list(range(blk, min(blk + R, nblocks)))
                    res1 = pool.map(_ps_pass1, [(b_i, shm.name, i) for i, b_i in enumerate(blocks)], chunksize=1)
                    jobs = []
                    for i, (b_i, (c, s1, t1, stored)) in enumerate(zip(blocks, res1)):
                        jobs.append((b_i, shm.name, i, int(c), bool(stored), float(S), float(T), k,
                                     gamma, two_tau, e31))
                        S += mpf(float(s1))
                        T += mpf(float(t1))
                        k += int(c)
                    res2 = pool.map(_ps_pass2, jobs, chunksize=1)
                    for b_i, r in zip(blocks, res2):
                        record(b_i, *r)
                    blk = blocks[-1] + 1
                    progress()
        finally:
            shm.close()
            shm.unlink()
    else:
        # numba engine: sieve in this process with all threads
        print(f"  engine: numba sieve, {get_num_threads()} threads", flush=True)
        flags = np.empty(NSUB * (SUB // 2), dtype=np.uint8)
        cnt = np.empty(NSUB, dtype=np.int64)
        ssum = np.empty(NSUB)
        tsum = np.empty(NSUB)
        S0 = np.empty(NSUB)
        T0 = np.empty(NSUB)
        k0 = np.empty(NSUB, dtype=np.int64)
        out_f = [np.empty(NSUB) for _ in range(2)]
        out_i = [np.empty(NSUB, dtype=np.int64) for _ in range(4)]
        out_p = np.empty(NSUB)
        while blk < nblocks:
            nsub = min(NSUB, nblocks - blk)
            lo = blk * SUB
            sieve_chunk(lo, nsub, base, nsmall, pat, flags, cnt, ssum, tsum)
            for i in range(nsub):
                S0[i] = float(S)
                T0[i] = float(T)
                k0[i] = k
                S += mpf(float(ssum[i]))
                T += mpf(float(tsum[i]))
                k += int(cnt[i])
            check_chunk(lo, nsub, flags, S0, T0, k0, gamma, two_tau, K_BROUGHAN, e31,
                        out_f[0], out_f[1], out_i[0], out_i[1], out_i[2], out_p, out_i[3])
            for i in range(nsub):
                record(blk + i, out_f[0][i], out_f[1][i], out_i[0][i], out_i[1][i],
                       out_i[2][i], out_p[i], out_i[3][i])
            blk += nsub
            progress()
    progress(force=True)

    Xm = mpf(Xeff)
    L = Xm * (1 - mlog(Xm) ** -3) - mlog(Xm)
    ok = st["nfail"] == 0 and st["nunres"] == 0
    lines = [
        f"limit X = {Xeff}",
        f"primes p <= X: {k}",
        f"largest k with c(p_k) >= E(p_k): {st['maxfailk']}",
        f"failures with k >= {K_BROUGHAN}: {st['nfail']}" + (f" (first: k, p = {st['firstfail']})" if st["firstfail"] else ""),
        f"unresolved margins (< {SAFE}) with k >= {K_BROUGHAN}: {st['nunres']}",
        f"lower bound for min (E(q) - c(q)) sqrt(q) log^2 q over k >= {K_BROUGHAN}: {st['min_kb']}"
        + (f" (in the sub-block [{st['min_kb_q_block'][0]}, {st['min_kb_q_block'][1]}])" if st["min_kb_q_block"] else ""),
        f"lower bound for min (E(q) - c(q)) sqrt(q) log^2 q over q >= e^31: {st['min_e31']}",
        f"sum_(p <= X) log(p/(p-1)) = {mp.nstr(S, 25)}",
        f"theta(X) = {mp.nstr(T, 25)}",
        f"Theorem 1.3 (ii) range: log n <= {mp.nstr(L, 12)}  (n <= 10^(10^{mp.nstr(mlog(L / mlog(10), 10), 8)}))",
        "RESULT: " + (f"inequality (2) holds at every N_k with k >= {K_BROUGHAN} and p_k <= {Xeff}" if ok else "NOT VERIFIED (failures or unresolved margins)"),
        f"elapsed: {st['elapsed'] / 3600:.2f} h",
    ]
    out = "\n".join(lines)
    print("\n" + out)
    with open(args.output, "w") as f:
        f.write(out + "\n")
    return ok


def main():
    ap = argparse.ArgumentParser()
    ap.add_argument("--limit", type=float, default=1e14, help="X: check all primes q <= X")
    ap.add_argument("--threads", type=int, default=0, help="numba engine: number of threads (default: all cores)")
    ap.add_argument("--workers", type=int, default=0, help="primesieve engine: worker processes (default: all cores)")
    ap.add_argument("--numba-sieve", action="store_true", help="use the numba sieve even if primesieve is installed")
    ap.add_argument("--checkpoint", default="second_criterion_checkpoint.json")
    ap.add_argument("--output", default="second_criterion_results.txt")
    ap.add_argument("--constants-only", action="store_true", help="run Parts 1-4 only")
    ap.add_argument("--skip-constants", action="store_true", help="skip Parts 1-4")
    args = ap.parse_args()

    if not args.skip_constants:
        ok = constant_checks()
        if args.constants_only:
            sys.exit(0 if ok else 1)
        if not ok:
            sys.exit("Parts 1-4 failed; Part 5 not started.")
    if njit is None:
        sys.exit("Part 5 needs numpy and numba: pip install numpy numba")
    print("\n=== Part 5: inequality (2) at the primorials ===", flush=True)
    sys.exit(0 if part5(args) else 1)


if __name__ == "__main__":
    main()
