# reverse3.py 
# Fig. 16.3 
#input: 1234567 or 85 or 123456789

def g(n,i,j):
  while n > 0:
    if n/2 != int(n/2):
      n, i, j = (n-1)/2, i, i+j
    else:
      n, i, j = n/2, i+j, j
  return j

n = int(input("n=? "))
gn = g(n,1,0)
print(f"n: {n}; g({n},1,0): {gn}")

u = 0
while n > 0:
  u = u*2 + n%2
  n = n//2

gu = g(u,1,0)
print(f"u: {u}; g({u},1,0): {gu}")
print("Equal?", gn == gu)