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

def g(n,i,j):
  if n == 0:
    return j
  elif n/2 != int(n/2):
    return g((n-1)/2, i, i+j)
  else:
    return g(n/2, i+j, 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)